[Data Structure] 균형 이진 탐색 트리(balanced binary search tree)와 AVL 트리

---

균형 이진 탐색 트리

 

 

이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조를 가지는데, 이진 탐색의 대상은 배열이므로 삽입과 삭제가 비효율적이지만 이진 탐색 트리에서 삽입과 삭제는 효율적이다. 단 이진 탐색 트리는 불균형인 경우 탐색의 시간복잡도가 $ \mathcal{O}(n) $ 이 되는 단점이 있다.

이를 이진 탐색과 마찬가지로 효율적으로 탐색하기 위해서는 트리가 균형 트리여야 한다. 즉 이진 트리이면서 이진 탐색과 마찬가지로 왼쪽 서브트리 값이 노드 값보다 작게, 오른쪽 서브트리 값이 노드 값보다 크게 오도록 하며, 균형잡혀 있다면균형 이진 탐색 트리이다.

간선의 수, 높이 등은 이진 트리(링크)의 속성을 일부 따른다. 노드가 $ n $ 개일 때 간선은 $ n -1 $ 개이고, 높이는 $ \lceil \lg (n + 1) \rceil $ 이다.

 

---

AVL 트리

 

아델슨 벨스키(Adelson-Velskii)와 랜디스(Landis)에 의해 제안된 트리로 둘의 이름을 따서 AVL 트리라 한다. 모든 노드의 왼쪽과 오른쪽 서브트리의 높이차가 $1$ 이하인 이진 탐색 트리이고, 트리가 불균형 상태가 된다면 스스로 노드들을 재배치하여 균형 상태를 유지한다. 언제나 균형 상태를 유지하기 때문에 탐색에서 평균, 최선, 최악의 경우 모두 $ \mathcal{O} (\log_2 n) $ 의 시간복잡도를 가진다.

균형 인수(balance factor)는 왼쪽 서브 트리의 높이에서 오른쪽 서브 트리의 높이를 뺀 값이고, 모든 노드의 균형 인수가 $ \pm 1 $ 이하라면 AVL 트리이다. 단말 노드의 높이는 $ 0 $으로 간주하고, 비단말 노드의 높이는 좌측 자식 노드와 우측 자식 노드의 높이 중 높은 높이 더하기 $1$ 이다.

AVL 트리의 탐색은 이진 탐색 트리의 탐색(링크)과 같다.

 

---

삽입

 

삽입은 삽입 위치에서 루트 노드까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 준다. 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형 인수가 $ \pm 2 $ 가 된 가장 가까운 조상 노드의 서브 트리들에 대하여 다시 재균형 상태를 만들어야 한다. 삽입 노드부터 균형 인수가 $ \pm 2 $가 된 가장 가까운 조상 노드까지 회전시킨다.

• LL 타입

• LR 타입

• RR 타입

• RL 타입