AVL 트리

같은 트리를 높이 균형을 맞춘 후의 상태; 평균 이동 비용이 3.00 노드 접근(node access)로 감소되었다.

AVL 트리의 시간복잡도
	평균	최악의 경우
공간	$O(n)$	$O(n)$
검색	$O(\log n)$	$O(\log n)$
삽입	$O(\log n)$	$O(\log n)$
삭제	$O(\log n)$	$O(\log n)$

컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 자가 균형 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다. 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)의 시간복잡도가 걸린다. 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다.

정의와 성질

• 높이 균형 성질(height-balance property): 트리 $T$의 모든 내부 노드(internal node) $v$에 대하여 $v$의 자식 노드들의 높이 차이가 최대 1이다.

• 임의의 이진 탐색 트리 $T$가 높이 균형 성질을 만족할 때 AVL 트리라고 한다.

높이 균형 성질(height-balance property)로부터 $n$개의 원소를 갖는 AVL 트리의 높이는 $logn$이라는 사실을 알 수 있다.

이진 탐색 트리에서의 검색 시간복잡도는 트리의 높이 이므로 AVL 트리의 검색 시간이 $O(\log n)$ 임을 알 수 있다.

동작

AVL 트리에서 노드를 일반적인 이진 탐색 트리처럼 삽입, 삭제 시키면 높이 균형 성질을 만족하지 않게 된다. 노드가 삽입, 삭제될 때 회전(rotation)을 통해 트리를 재구성하여 높이 균형 성질을 유지시킨다.

삽입

AVL 트리 T에 새로운 노드 d를 삽입(Insertion)하는 방법은 T에서 d가 단말 노드(leaf node)로 삽입될 수 있도록 하는 노드 w를 찾고 w의 자식으로 d를 삽입한다.

d를 삽입하면 불균형해질 수 있는데 세 노드를 기준으로 회전(rotation)시킴으로써 균형을 맞춘다.

회전

트리 $T$의 재구성 작업을 회전(Rotation)이라 한다.

회전의 기준이 되는 세 노드 $x$, $y$, $z$는 다음과 같다. $z$는 $w$로부터 root로 가는 경로상에 가장 처음으로 위치한 불균형한 노드이다. $y$는 $z$의 자식 중에서 가장 큰 높이를 갖는 노드이다. $x$는 $y$의 자식 중에서 가장 큰 높이를 갖는 노드이다.

$x$가 이진 탐색 트리 $T$의 노드이고 $y$가 부모, $z$가 할아버지 노드일 때 다음과 같이 재구성한다.

1. $x$, $y$, $z$를 왼쪽-오른쪽 순서 (inorder)로 나열 한 순서대로 $a$, $b$, $c$ 라고 하고, $x$, $y$, $z$의 4개의 부분 트리들을 왼쪽-오른쪽 순서 (inorder)로 나열한 것을 $T_{0}$, $T_{1}$, $T_{2}$, $T_{3}$ 라고 하자.
2. $z$가 root인 부분 트리를 $b$를 root로 하는 새로운 부분 트리로 바꾼다.
3. $a$가 $b$의 왼쪽 자식이 되고 $T_{0}$, $T_{1}$은 각각 $a$의 왼쪽, 오른쪽 자식이 된다.
4. $c$가 $b$의 오른쪽 자식이 되고, $T_{2}$, $T_{3}$는 각각 $c$의 왼쪽, 오른쪽 자식이 된다.

이 작업을 구상화하면 $b=y$ 일 때 $y$를 $z$와 회전시키는 것처럼 보인다. 이 작업을 single rotation이라고 한다.

$b=x$ 일 때 $x$를 $y$와 회전시키고 다시 $z$와 회전시키는 것처럼 보인다. 이 작업을 double rotation이라고 한다.

이 재구성 방법은 $T$의 부모-자식 관계만을 바꾸는 것이기 때문에 $O(1)$ 시간이 걸린다.

삭제

AVL 트리 $T$에서 노드 $d$를 삭제(Removal)하는 방법은 root부터 $d$를 검색한다. $d$가 단말 노드가 아니라면 자신의 왼쪽 부분 트리 중에서 최댓값을 갖는 노드나 오른쪽 부분 트리 중에서 최솟값을 갖는 노드를 $d$와 바꾼다. 이 작업을 $d$가 단말 노드가 될 때까지 반복하여 단말 노드 $d$를 삭제한다.

삭제 역시 트리가 불균형해질 수 있는데 삽입과 동일한 방법으로 $d$의 부모를 $w$라고 한 뒤 회전시켜 균형을 맞춘다.

같이 보기

• B 트리

참고 문헌

• Robert Lafore(1998), Data Structures & Algorithms in JAVA, Sams, ISBN 1-57169-095-6
• Michael T.Goodrich, Roberto Tamassia(2006), Data Structures & Algorithms in JAVA(4th edition), John Wiley & Sons, ISBN 0-471-73884-0
• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 458–475 of section 6.2.3: Balanced Trees.
• Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2015), “Rank-balanced trees” (PDF), 《ACM Transactions on Algorithms》 11 (4): Art. 30, 26, doi:10.1145/2689412, MR 3361215, S2CID 1407290 .