[ 자료 구조 ] 균형 이진 탐색 트리 : AVL 트리와 회전 연산

AVL 트리 (Adelson-Velskii & Landis Tree) : 대표적인 균형 이진 탐색 트리

각 노드에서 왼쪽 서브 트리의 높이(hL : height of left subtree)와 오른쪽 서브 트리의 높이(hR : height of right subtree)의 차이가 1 이하인 트리

 

특징

- 왼쪽 서브 트리 < 부모 노드 < 오른쪽 서브 트리의 크기 관계를 갖음 *이진 탐색 트리의 특징

- 각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이 (hL - hR)를 노드의 균형 인수(BF, balance factor)라고 함

- 각 노드의 균형 인수로 {-1, 0, +1} 값만 가지게 함으로써 균형을 유지함

 

 

루트 노드 50을 기준으로 왼쪽 서브 트리의 높이는 2, 오른쪽 서브 트리의 높이는 3이므로 BF = hL-hR = -1이 된다.

위와 같은 방식으로 그림 속 노드들의 BF를 구할 수 있다. 단말 노드 9와 같은 경우는 서브 트리가 없으므로 BF는 0이 된다.

 

 

균형 인수가 {-1, 0, +1} 이외의 값을 가지므로 균형이 깨져 한 방향으로 치우친 비AVL 트리이다.

균형 인수가 +이면 왼쪽 서브 트리에 문제가 있는 것이고, -이면 오른쪽 서브 트리에 문제가 있는 것이다.

 

AVL 트리의 회전 연산

불균형 유형별 해결 방법

AVL 트리에서 수행하는 삽입/삭제 작업은 이진 탐색 트리에서의 삽입/삭제 작업과 같고, 이후에 균형을 맞추어주는 재구성 작업이 추가되는데 이 작업은 회전(Rotation)을 통해 이루어짐 

• 단순 회전(Single Rotation) - LL 회전과 RR 회전과 같이 한 번 회전하는 것
• 이중 회전(Double Rotation) - LR 회전과 RL 회전과 같이 두 번 회전하는 것

이진 탐색 트리의 삽입/삭제에 관한 글은 👇🏻

https://tildacoderecorder.tistory.com/105

[ 자료구조 ] 이진 탐색 트리의 탐색/삽입/삭제 연산 - C언어

 

 

LL 회전 연산

1. L2의 오른쪽 자식 노드를 L1의 왼쪽 자식 노드로 옮긴다.
2. L1을 L2의 오른쪽 자식 노드로 옮긴다.

위 그림으로는 LL 회전 연산의 방법을 이해하기 조금 어려우나 아래의 그림을 보면 이해할 수 있다.

왼쪽 트리를 LL 회전 한다면 노드2의 오른쪽 자식 노드를 노드1의 왼쪽 자식 노드로 옮기고, 노드 1을 노드2의 오른쪽 자식 노드로 옮기는 과정에서 크게 시계 방향으로 회전하는 것을 알 수 있다.

 

RR 회전 연산

1. L2의 왼쪽 자식 노드를 L1의 오른쪽 자식 노드로 옮긴다.
2. L1을 L2의 왼쪽 자식 노드로 옮긴다.

반시계 방향으로 회전하는 것을 알 수 있다.

 

LR 회전 연산

LR 회전은 루트 노드의 왼쪽 서브 트리의 오른쪽 서브 트리에 새 노드가 추가 되었을 때 수행한다.

1. L2와 L3 구간에 대해 RR 회전을 수행하고 노드 L3을 L1의 왼쪽 자식 노드로 만든다.
2. L1에 대하여 LL 회전을 수행한다.

아래 그림을 예시로 보자면,

 

먼저 노드 B를 중심으로 한 서브 트리의 균형을 맞춰준다. 오른쪽 자식 노드에 문제가 있으므로 RR 회전을 해준다.

이후 루트 노드 A를 중심으로 LL 회전을 해주면 두 트리의 균형이 맞게 된다.

 

RL 회전 연산

LR 회전 연산과 반대로 LL 회전 후 RR 회전을 해준다. 원리는 위와 같다.

 

 

 

참고 : C언어로 작성하는 컴퓨터 알고리즘 / 이한출판사