자가균형이진탐색트리 (AVL트리)

자가균형이진탐색트리(AVL트리)란?

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

- 이진 탐색 트리의 속성을 가짐
- 왼쪽, 오른쪽 서브 트리의 높이 차이는 최대 1
- 높이 차이가 1보다 커지면 회전을 통해 균형을 맞춰 높이 차이를 줄임
- 삽입/검색/삭제의 시간 복잡도는 $O(log n)$
- Balance Factor (BF, 균형 인수) : AVL 트리가 균형이 무너졌는지를 판단할 때 사용
- BF(k) = k의 왼쪽 서브트리의 높이 - k의 오른쪽 서브트리의 높이
- AVL트리는 모든 노드의 BF가 -1,0,1 중 하나여야 한다.
 

AVL트리의 삽입연산에서 균형이 깨지는 경우

1️⃣ LL (Left left) case

• BF가 -1~1을 벗어난 노드를 기준으로 왼쪽, 왼쪽 노드가 존재한다면 LL 케이스이다
• 이때 해당 노드를 기준으로 우회전을 적용하면 불균형이 해소된다.

2️⃣ RR (Right right) case

• BF가 -1~1을 벗어난 노드를 기준으로 오른쪽, 오른쪽 노드가 존재한다면 RR 케이스이다.
• 이때 해당 노드를 기준으로 좌회전을 적용하면 불균형이 해소된다.

3️⃣ LR (Left right) case

• BF가 -1~1을 벗어난 노드를 기준으로 왼쪽, 오른쪽 노드가 존재한다면 LR 케이스이다.
• 이때 먼저 BF에 이상이 있는 노드의 왼쪽 자식노드를 기준으로 좌회전을 진행한다.
• 이후 BF에 이상이 있는 노드를 기준으로 우회전을 진행하면 불균형이 해소된다.

4️⃣ RL (Right left) case

• BF가 -1~1을 벗어난 노드를 기준으로 오른쪽, 왼쪽 노드가 존재한다면 RL 케이스이다.
• 이때 먼저 BF에 잇는 노드의 오른쪽 자식노드를 기준으로 우회전을 진행한다.
• 이후 BF에 이상이 있는 노드를 기준으로 좌회전을 진행하면 불균형이 해소된다.

 
 

회전함수

우회전

1. y 노드의 오른쪽 자식 노드를 z노드로 변경한다.
2. z 노드 왼쪽 자식 노드를 y노드의 오른쪽 서브트리(T2)로 변경한다.

좌회전

1. y 노드의 왼쪽 자식 노드를 z노드로 변경한다.
2. z 노드 오른쪽 자식 노드를 y노드의 왼쪽 서브트리로 변경한다.