[자료구조] 4-4. AVL 트리

이전에 이진 탐색 트리 편에서, 균형잡힌 트리와, 그렇지 못한 트리를 보았을 것이다.

그래서 이번에는 불균형한 트리를 균형잡힌 트리로 잡아주는 AVL 트리에 대해 알아볼 것이다.

 

AVL트리는 다음의 특징이 있다:

1. 이진 탐색 트리의 속성을 가진다.
2. 왼쪽, 오른쪽 서브트리의 높이 차가 최대 1이다.
3. 높이 차이가 1보다 커지면, 회전을 통해서 균형을 잡는다.
4. 최대높이를 logN으로 유지시켜서 O(logN)으로 유지시킨다.

 

여기서 회전을 알기 전에, 균형을 아는 수치인 BF값을 알아보자.

 

BF(Balance Factor)

 

BF(k) = height(left(k)) - height(right(k))

값이 1이면 왼쪽이 한 단계 높은 것이고, 

0이면 높이가 같다는 뜻,

-1이면 오른쪽이 한 단계 높은 것이다.

 

 

만약, |BF(k)| 가 1보다 커지면, 회전이 필요해지는 것이다.

 

 

회전

 

Left Rotation

1. x를 y의 왼쪽 서브트리로 한다.
2. x의 오른쪽 서브트리를 T2로 한다.
3. 루트를 y로 바꾼다.

 

Right Rotation

1. x를 y의 오른쪽 서브트리로 한다,
2. x의 왼쪽 서브트리를 T2로 한다.
3. 루트를 y로 바꾼다.

 

회전이 사용되는 케이스

회전이 쓰이는 케이스는 총 4가지가 있다:

1. LL Case(Left Left Case)
2. RR Case(Right Right Case)
3. LR Case(Left Right Case)
4. RL Case(Right Left Case)

LL Case (Left Left Case)

BF값이 범위를 벗어나는 노드를 루트로 했을 때, 왼쪽-왼쪽으로 이어지는 경우를 LL케이스라고 한다.

우회전(Right Rotation)으로 해결해주면 된다.

 

RR Case (Right Right Case)

BF값이 범위를 벗어나는 노드를 루트로 했을 때, 오른쪽-오른쪽으로 이어지는 경우를 RR케이스라고 한다.

좌회전(Left Rotation)으로 해결해주면 된다.

 

 

LR Case (Left Right Case)

BF값이 범위를 벗어나는 노드를 루트로 했을 때, 왼쪽-오른쪽으로 이어지는 경우를 LR케이스라고 한다.

루트 노드의 자식 노드를 기준으로 좌회전해서 LL Case를 만들어준 뒤, 루트 노드에서 우회전을 하면 된다.

 

 

 

RL Case (Right Left Case)

BF값이 범위를 벗어나는 노드를 루트로 했을 때, 오른쪽-왼쪽으로 이어지는 경우를 RL케이스라고 한다.

루트 노드의 자식 노드를 기준으로 우회전해서 RR Case를 만들어준 뒤, 루트 노드에서 좌회전을 하면 된다.

 

 

이 사이트에서 직접 시뮬레이션을 할 수 있다:

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL Tree Visualzation