자료구조 avl tree

1. AVL 트리 개요

AVL 트리는 이진 검색 트리의 일종으로서 1962년 러시아의 대학생 G.M. Adelson-Velskii와 E.M. Landis에 의해 개발되었다. 이 구조는 검색, 삽입, 삭제 연산의 효율성을 높이기 위해 균형을 유지하는 데 초점을 맞춘다. 일반적인 이진 검색 트리의 경우 최악의 경우 높이가 전체 노드 수에 비례하게 되어 검색 시간이 매우 길어질 수 있는데, AVL 트리는 이러한 문제를 방지하기 위해 높이 균형 속성을 갖는다. 구체적으로, AVL 트리의 모든 노드에 대해 왼쪽 서브트리 높이와 오른쪽 서브트리 높이의 차이인 균형 인수(balance factor)가 -1, 0, 1 이내로 유지되도록 한다. 이러한 규칙을 지키면 트리의 높이는 대략 log₂ n에 비례하게 되며, n이 10만인 경우 트리의 높이는 최대 약 16 정도로 유지된다. 통계적으로 보면, 일반 이진 검색 트리의 최악 높이인 n이 10만일 때는 높이가 10만에 거의 육박할 수 있지만, AVL 트리에서는 높이가 약 17로 제한되어 검색 수행 시간을 평균적으로 O(log n)으로 보장한다. 이때 균형을 유지하기 위해 삽입이나 삭제가 발생할 때마다 트리의 일부 노드에서 회전 연산이 수행되며, 이러한 회전법에는 LL, RR, LR,…