AVL 트리

AVL 트리는 자가 균형 이진 탐색 트리의 하나이다. 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리를 말한다. AVL 트리는 트리가 비균형 상태가 되면 스스로 노드들을 재배치하여 균형 상태로 만든다.

균형 인수

한 노드의 균형 인수(balance factor)는 한쪽 서브 트리의 높이 - 반대편 서브 트리의 높이로 정의된다. 모든 노드의 균형 인수가 ±1 이하면 AVL 트리이다.

재균형

AVL 트리는 삽입이나 삭제 연산으로 인해 균형 상태가 깨질 수 있는데, 삽입 연산의 경우 새로운 노드의 삽입 후에 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다. 불균형 상태로 변한(균형 인수가 ±2가 된) 가장 가까운 조상 노드의 서브 트리들에 대하여 균형을 잡는 일을 재균형(rebalance)이라 한다.

회전

삽입 연산에서의 재균형은 노드가 삽입된 위치에 따라 노드를 회전(rotation)시키는 것으로 새로운 노드의 삽입에는 다음의 경우가 있다. 새로 삽입된 노드 N으로부터 가장 가까우면서 균형 인수가 ±2가 된 조상 노드를 A라고 하자.

LL 타입: N이 A의 왼쪽 서브 트리의 왼쪽 서브트리에 삽입된다.
RR 타입: N이 A의 오른쪽 서브 트리의 오른쪽 서브트리에 삽입된다.
RL 타입: N이 A의 오른쪽 서브 트리의 왼쪽 서브트리에 삽입된다.
LR 타입: N이 A의 왼쪽 서브 트리의 오른쪽 서브트리에 삽입된다.

LL과 RR, RL과 LR은 각각 대칭이다. 재균형시키는 방법은 다음과 같다.

LL 타입: A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킨다.
RR 타입: A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킨다.
RL 타입: A부터 N까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전시킨다.
LR 타입: A부터 N까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전시킨다.

한 번만 회전시키는 것을 단순 회전(single rotation)이라고 하며 LL 회전, RR 회전이 여기에 속한다. 두 번의 회전이 필요한 것을 이중 회전(double rotation)이라고 하며 LR 회전, RL 회전이 여기에 속한다.

LL 회전과 RR 회전

빈 문단 이 문단은 비어 있습니다. 내용을 추가해 주세요.

RL 회전과 LR 회전

빈 문단 이 문단은 비어 있습니다. 내용을 추가해 주세요.

시간복잡도

AVL 트리는 균형 트리임이 항상 보장되기 때문에 탐색이 $O(log_{2}n)$ 시간 안에 끝나고 삽입과 삭제 연산도 $O(log_{2}n)$ 시간 안에 할 수 있다.

역사

Adelson-Velskii와 Landis에 의해 1962년에 제안되었다.