AVL Tree

Goal

• 자가 균형 트리에 대한 이해
• AVL 트리에 대한 이해
• AVL 트리를 직접 구현해본다.

---

AVL Tree란?

자가 균형 이진탐색 트리(self-balancing binary search tree) 일종으로,

왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1이하인 이진 탐색 트리를 말한다.

 

AVL 트리는, 트리가 비균형 상태가 되면 스스로 노드들을 재배치(self-balancing)하여 균형 상태로 만든다.

따라서, 항상 균형 트리를 보장하기 때문에 O(logn)의 탐색 시간을 보장한다.

 

*이진 탐색 트리에서 균형을 유지하는 것이 중요한 이유

이진 탐색 트리 연산(삽입, 삭제, 탐색)의 시간 복잡도는 탐색 시간에 지배된다.

그렇기 때문에 이진 탐색 트리에서 균형을 유지하는 것은 굉장히 중요하다.

이진 탐색 트리의 균형이 유지될 경우 탐색 시간은 O(logn)의 탐색 시간을 보장한다.

 

AVL-Tree의 시간 복잡도

 

AVL의 성질

• Balanced Factor = {-1, 0 , 1}

*Balanced Factor(BF) := Height(left subtree) - Height(right subtree)

즉, Balanced Factor는 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차로 정의된다. (BF 차가 클수록 불균형 이진 트리)

 

AVL트리에서는 높이 차가 항상 1이하의 값만 유지되기 때문에 Balanced Factor는 -1, 0, 1 값 중 하나이다.

• left-heavy : Height(left subtree) > Height(right subtree)
• right-heavy : Height(left subtree) < Height(right subtree)
• balanced : Height(left subtree) = Height(right subtree)

위와 같은 성질 때문에 AVL 트리는 O(logn)의 연산 시간을 갖게 된다. (높이 h = logn)

 

AVL 트리가 균형을 유지하는 방법

AVL 트리는 삽입, 삭제 연산시 균형이 깨질 수 있는데, 이때 회전(rotation) 연산을 통해 트리를 재구성하여 AVL 트리의 균형 성질을 유지시킨다.

 

삽입, 삭제 연산시 불균형 상태(BF가 2 혹은 -2)로 바뀐 노드를 기준으로 그 서브트리들의 위치를 rotation하는 방식을 취한다. rotation에는 두 가지 방식이 있는데 삽입 연산을 중심으로 살펴 보도록 하자.

 

AVL 트리에서 균형이 깨지는 경우

• 삽입 연산 : 항상 단말 노드의 왼쪽 자식, 오른쪽 자식에서 이루어 진다. 이때, 삽입 노드로부터 가장 가까우면서 BF가 +2 또는 -2인 조상 노드의 서브 트리를 회전시켜 트리의 균형을 맞춘다.
• 삭제 연산 : 삭제 연산 이후, 노드가 불균형 상태가 되면 마찬가지로 회전 연산을 통해 트리의 균형을 맞춘다.

삽입 연산

가장 가까운 조상 노드를 A, 새로 삽입된 노드를 N이라 할 때,

A의 BF가 불균형 상태가 되는 경우는 다음과 같이 4가지 경우로 나뉜다.

(조상 노드가 있을 경우에만 불균형 상태 발생)

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

이떄, LL, RR은 서로 대칭, LR, RL 여깃 서로 대칭이다. 

 

다음은 균형을 맞추기 위한 회전 연산을 나타낸다.

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

한번만 회전 시키는 경우를 single rotation, 두번의 회전을 하는 경우 double rotation이라고 하는데,

LL, RR 회전은 single rotation에 해당하고

LR, RL 회전은 double rotation에 해당한다.

 

• single right rotation : 오른쪽으로 한번 회전 (= LL회전)
• single left rotation : 왼쪽으로 한번 회전 (= RR 회전)
• double rotation(left-right) : 왼쪽 회전을 한 후 오른쪽 회전 (= LR 회전)
• double rotation(right-left) : 오른쪽 회전을 한 후 왼쪽 회전 (= RL 회전)

참고)

삽입하는 노드의 조상 노드를 A, 부모 노드를 P라 할 때, 다음과 같은 특징을 갖는다.

• single right rotation : P는 A의 왼쪽 자식 노드이며, P는 right-heavy가 아니다. (0<= BF(P))
• single left rotation : P는 A의 오른쪽 자식 노드이며, P는 left-heavy가 아니다. (BF(P) <= 0)
• double rotation : P는 A의 왼쪽  ( (BF(P) = -1)

 

single rotation

• Z를 잡아 당겨 V를 새로운 루트 노드로 만든다.
• U의 왼쪽 서브 트리를 V의 오른쪽 서브 트리로 변경
• V의 오른쪽 서브 트리를 U로 변경
• U, V의 Balanced Factor 값 변경 (0, 0)

위 과정을 거치면 다음과 같은 형태가 된다.

 

single rotation연산을 일반화 하면 다음과 같은 형태로 나타낼 수 있다.

 

U : BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드

V : U의 자식노드, BF 절대값이 1이하

 

single rotation은 다음 두 가지 경우에 V를 중심으로 실시한다.

 

• V가 U의 왼쪽 자식노드, V의 왼쪽 서브트리에 새 노드 삽입 : V를 기준으로 right rotation
• V가 U의 오른쪽 자식노드, V의 오른쪽 서브트리에 새 노드 삽입 : V를 기준으로 left rotation

 

Left/Right rotation을 직관적으로 나타낸 경우

 

AVL 트리 삽입 연산 동작 과정

 

double rotation

U : BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드

V : U의 자식노드, BF 절대값이 1이하

W : V의 자식 노드, 회전의 중심이 BF 절대값이 1이하 

 

double rotation은 다음 두 가지 경우에 실행된다.

• V가 U의 왼쪽 자식노드, V의 오른쪽 서브트리에 새 노드 삽입
• V가 U의 오른쪽 자식노드, V의 왼쪽 서브트리에 새 노드 삽입

다음 그림은 double rotation을 일반화 한 그림이다.

(left-right rotation 형태의 그림이지만 right-left도 동일)

1. W를 중심으로 first rotation 진행 (위 그림에서는 left rotation. A를 잡아 당김)
2. 다시 W를 중심으로 second rotation 진행 (위 그림에서는 right rotation. D를 잡아 당김)

 

삭제 연산

삭제 연산도 삽입 연산과 마찬가지로, Balanced Factor가 불균형 상태가 된 것이 있다면, rebalance과정을 거쳐 트리를 균형상태로 변경하면 된다.

 

구현 코드

 

References

https://gist.github.com/Harish-R/097688ac7f48bcbadfa5#file-avl-tree-cpp-L85

https://ratsgo.github.io/data%20structure&algorithm/2017/10/27/avltree/

https://doublesprogramming.tistory.com/237