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

균형 이진 탐색 트리란?

 

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

이러한 높이 차이를 균형인수(Balance Factor) 라고 합니다. (BF)

AVL 트리는 삽입 또는 삭제로 트리가 균형을 잃었을 때 스스로 노드를 재배치하여 위의 조건을 다시 맞춥니다. 

( BF가 1 이하:   1, 0, 1 중에서 값을 가집니다. )

 

 

[장점]

BF가 1 이하이므로(높이 차이가 거의 비슷하기 때문에) 탐색, 삽입, 삭제 모두 O(log2n) 시간 안에 가능합니다. 

균형 없는 트리라면, 한쪽으로만 자라날 수 있기 때문에, 최악의 경우 시간 복잡도가 O(n)이 됩니다. 

 

[취약점]

자료가 많아지면 트리의 높이가 커지는 문제가 있습니다.

자료 삽입삭제가 자주 일어나면 균형을 유지하느라 재배치에 쏟는 시간이 많아질 수 있습니다. 

 

AVL TREE 라는 이름은 만든 사람 2명의 앞글자를 딴 것입니다. 아델슨 벨스키(Abelson-Velskii)와 라딘스(Landis)

 

 

균형을 잃은 4가지  경우

 

(전제)

root 노드를 기준으로 왼쪽, 오른쪽을 구분한다. 

root : 초기 부모

pivot : root의 자리를 대신할 자식 

 

LL과 RR은 한 번만 회전하는 단순회전이고, LR, RL은 두 번 회전하는 이중회전 입니다.

어떤 방향에 따라 부모와 자식 원소의 위치를 바꾸면 됩니다. 

 

 

 

1. LL (Left-Left) : 오른쪽으로 회전

 

노드 '3'을 오른쪽으로 회전한다. 노드 '3'이 노드 '2'의 자식이 된다. 

균형이 왼쪽 서브 트리의 왼쪽 서브 트리에 의해 깨진 경우. 오른쪽 방향으로 회전한다.

다시 말하면, 루트 노드의 왼쪽 자식노드의 왼쪽 서브트리에 의해 균형이 깨진 경우를 말한다. 

 

 

 

2. RR (Right-Right) : 왼쪽으로 회전

 

'1' 노드가 '2'노드의 자식이 된다.

루트노드 1을 기준으로 생각한다.

1의 오른쪽 서브 트리(2)의 오른쪽 서브 트리(3)에 의해 균형이 깨진 경우. 왼쪽 방향으로 회전한다. 

루트 노드의 오른쪽 자식노드의 오른쪽 서브 트리에 의해 균형이 깨진 경우를 말한다. 

 

 

 

3. LR ( Left-Right): LL회전 후에 RR회전

 

루트 노드 3을 기준으로 보자.  

왼쪽 서브 트리의 오른쪽 노드인 1과 2를 먼저 왼쪽으로 회전한다.

왼쪽 서브트리를 오른쪽으로 회전하여 3이 2의 자식이 되도록 한다. 

루트 노드 3을 기준으로, 루트의 왼쪽 서브트리(1)의 오른쪽 서브 트리(2)가 균형을 잃은 경우.

왼쪽으로 회전 후 오른쪽으로 회전한다. 

( 루트의 왼쪽 서브트리의 오른쪽 서브 트리를 왼쪽으로 회전하고, 루트와 루트의 왼쪽 서브트리를 오른쪽으로 회전한다. )

 

 

 

4. RL (Right-Left) : RR 회전 후에 LL회전

 

루트 노드 1을 기준으로 보자. 

오른쪽 서브트리가 균형을 잃었다. 

오른쪽 서브트리의 왼쪽 자식을 오른쪽으로 회전한다. 2와 3을 오른쪽으로 회전.

그리고 루트노드의 오른쪽 자식 '2'를 기준으로 왼쪽으로 회전한다. 

 

 

 루트 노드의 오른쪽 서브트리의 왼쪽 서브트리가 균형을  잃은 경우.

오른쪽으로 회전 후, 왼쪽으로 회전한다. 

( 왼쪽 서브 트리를 오른쪽으로 회전 후. 루트 노드와 오른쪽 서브 트리를 왼쪽으로 회전한다. )

 

 

---

탐색

 

이진 탐색 트리의 연산과 같습니다. 

 

 

삽입 

 

회전을 이해해야 한다. 

오른쪽 회전, 왼쪽 회전 두 가지를 기반으로 기본 연산을 한다. 

 

LeftRotate() : 왼쪽방향으로 회전 

 

RightRotate() :오른쪽방향으로 회전 

 

leftRightRotate() : 왼쪽, 오른쪽 방향 회전 

 

rightLeftRotate() : 오른쪽, 왼쪽 방향 회전 

 

 

 

 

---

[ 참고 포스팅 ]

 

https://edu-coding.tistory.com/43

균형 이진 탐색트리

http://egloos.zum.com/printf/v/913998

자료구조 :: 탐색(3) "균형 이진 탐색 트리 - AVL 트리"