AVL 트리

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

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

정의와 성질

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

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

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

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

동작

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

삽입

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

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

회전

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

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

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

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

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

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

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

삭제

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

삭제 역시 트리가 불균형해질 수 있는데 삽입과 동일한 방법으로 ${\displaystyle d}$의 부모를 ${\displaystyle 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