AVL 트리

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

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

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

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

이진 탐색 트리에서의 검색 시간복잡도는 트리의 높이 이므로 AVL 트리의 검색 시간이  임을 알 수 있다.

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

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

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

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

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

가 이진 탐색 트리 의 노드이고 가 부모, 가 할아버지 노드일 때
다음과 같이 재구성한다.
 , , 를 왼쪽-오른쪽 순서 (inorder)로 나열 한 순서대로 , ,  라고 하고, , , 의 4개의 부분 트리들을 왼쪽-오른쪽 순서 (inorder)로 나열한 것을 , , ,  라고 하자.
 가 root인 부분 트리를 를 root로 하는 새로운 부분 트리로 바꾼다.
 가 의 왼쪽 자식이 되고 , 은 각각 의 왼쪽, 오른쪽 자식이 된다.
 가 의 오른쪽 자식이 되고, , 는 각각 의 왼쪽, 오른쪽 자식이 된다.

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

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

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

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

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

각주

참고 문헌 
 Robert Lafore(1998), Data Structures & Algorithms in JAVA, Sams, 
 Michael T.Goodrich, Roberto Tamassia(2006), Data Structures & Algorithms in JAVA(4th edition), John Wiley & Sons, 

이진 트리
소련의 발명품
1962년 컴퓨팅