자료 구조 및 알고리즘 9 - AVL Tree

0. AVL Tree

 

AVL 트리는 발명자의 이름인 Adelson-Velsky and Landis 에서 따온 이름으로 자가 균형 이진 탐색 트리입니다. 자가 균형 이진 트리는 스스로 균형을 잡는 트리라는 의미로 삽입, 삭제와 같이 데이터 균형이 달라질 것 같은 수행에서 스스로 균형을 맞추도록 트리의 구조를 바꿉니다. 일반적인 이진 탐색 트리와 달리 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(logN) 을 보장합니다.(* BST 의 경우 최악의 경우 O(N) 입니다.)

2024.04.20 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 8 - Binary Search Tree

 

 

---

 

 

1. Definition

 

1.1 Height-balance property

 

높이 균형 성질은 트리 T 에 대해 모든 내부 노드 v 가 있을 때, v 의 자식 노드들의 높이 차이가 최대 1 인 성질입니다. 자식 노드들의 높이 차이를 흔히 blance factor , BF 라고 합니다.(* BF = (height of Left subtree) - (height of Right subtree)) BF 가 가질 수 있는 수는 -1, 0, 1 밖에 없고, 만약 -2 보다 작아지거나 2 보다 커지게 된다면 트리 T 는 자체적으로 균형을 맞춰 BF 가 -1, 0, 1 이 되도록 합니다.

 

임의의 이진 탐색 트리 T 가 높이 균형 성질을 만족한다면 해당 트리 T 를 AVL 트리라고 합니다.

 

1.2 Height bound proof

 

AVL 트리의 탐색, 삽입, 삭제의 시간복잡도는 최악, 평균 모두 O(logN) 을 보장하는데 다시 말하면 AVL 트리의 높이가 logN 이라는 의미입니다. (* 최악의 경우는 트리의 높이 만큼 비교연산이 일어나야 한다는 의미이므로 O(height) 입니다.)

 

이를 증명하기 위해서 높이 균형 성질을 만족하는 트리 T 가 있다고 합니다.

또한 높이 h 에 따른 노드의 최소 개수 n 을 n(h) 라고 한다면, 

 

높이가 1 일 때, 나올 수 있는 노드의 최소 노드 개수는 1 입니다. n(1) = 1

높이가 2 일 때, 나올 수 있는 노드의 최소 노드 개수는 2 입니다. n(2) = 2

 

경향성을 생각해보면 높이가 높을 수록 나올 수 있는 최소 노드의 개수는 점점 커집니다.

즉 임의의 k 에 대해 n(k) < n(l) , l < k 임을 알 수 있습니다.

 

임의의 높이 h 에 대해, n(h) 는 (높이 h 를 갖는 루트노드) + (루트 노드의 서브트리들의 최소 노드 개수) 로 설명할 수 있습니다.

 

이때 서브트리의 높이는 h-1 또는 h-2 입니다.(* 해당 트리 T 는 AVL 이기 때문에 자식 서브트리의 높이 차이가 2 이상 날 수 없기 때문입니다.)

 

즉 n(h) = 1 + n(h-1) + n(h-1) 또는 n(h) = n(h-1) + n(h-2) 입니다. (* n(h-2) 가 두 개 나오는 것은 불가능 합니다. 적어도 하나의 서브트리의 높이가 h-1 이어야 합니다.)

 

하지만 n(h-1) > n(h-2) 이기 때문에 최소 노드의 개수 n(h) = 1 + n(h-1) + n(h-2) 입니다.

 

이는 피보나치 수열과 유사합니다.

 

n(h-1) > n(h-2) 과 n(h) = 1 + n(h-1) + n(h-2) 을 통해 n(h) > 2n(h-2) 임을 알 수 있고, 쭉쭉 해보면

 

n(h) > 4n(h-4)

n(h) > 8n(h-6)

...

n(h) > 2^i * n(h-2i) 임을 알 수 있습니다.

i = h/2 - 1 일 때, n(h - 2i) = n(1) = 1 입니다. 따라서

n(h) > 2^(h/2 - 1)

 

양번에 log를 취하면

h/2 - 1 < log(n(h))

h < 2log(n(h)) + 2

 

높이가 h 일 때 나올 수 있는 임의의 노드 개수 N 은 n(h) 보다 큽니다. N > n(h) 따라서

h < 2log(n(h)) + 2 < 2logN + 2

 

높이는 최대 2logN + 2, 즉 시간 복잡도로 따지면 O(logN) 이 됩니다.

 

---

 

 

2. self-balancing

 

AVL 트리에서 balancing 이 필요한 경우는 BF 가 2 이거나 -2 일 때 입니다. BF 가 2 이거나 -2 가 만들어지는 경우는 크게 4가지 case 입니다. AVL 트리는 삽입이나 삭제가 일어날 때 탐색이 이루어졌던 노드들에 대해서 BF 를 수정하는데 이때 변경한 노드에서 루트 노드로 "올라오면서" 검사합니다. 정말 운 좋게도 올라오면서 밸런싱이 필요한 노드에 대해 리밸런싱을 수행하면 위에 노드에 대해서는 리밸런싱을 할 필요가 없습니다.(* 리밸런싱을 하면 리밸런싱을 하는 노드 위에 노드들에 대해 높이가 변하지 않기 때문입니다.)

 

 

---

 

 

2.1 LL case

리밸런싱을 해야하는 루트 노드를 기준으로 왼왼쪽에 노드에 추가적으로 노드가 삽입되는 경우이기 때문에 LL case 라 불립니다. 이 경우 LL rotation 을 통해 다시 밸런스를 맞춥니다.

 

---

 

 

2.2 LR case

 

루트 노드를 기준으로 왼오른쪽에 추가적으로 노드가 삽입되는 경우이기 때문에 LR case 라고 합니다. 이 경우 LR rotation 을 통해 리밸런싱을 합니다.

 

---

 

 

2.3 RL case and RR case 

 

RL case 와 RR case 의 경우는 LR case 와 LL case 에 대해 방향만 반대이고 나머지는 똑같은 구조로 수행됩니다.