[자료구조] AVL Tree(AVL 트리) - CS면접 대비

이번 글에서는 AVL 트리에 관한 내용을 정리해보고자 한다. 이전 글에서 언급했던 것처럼 BST는 공백인 상태에서 이미 정렬된 수를 연속으로 삽입하는 경우 편향(skewed) 문제가 발생한다. 따라서 최악의 경우 자료 탐색에 소요되는 시간이 리스트를 순차 탐색하는 것과 같아진다. 균형 탐색 트리의 일종인 AVL 트리는 이러한 BST의 편향 문제를 해결하기 위해 고안되었으며, 동적 검색을 O(log N) 시간 내에 할 수 있고, 새로운 키를 O(log N) 시간 내에 삽입하거나 삭제할 수 있다.

---

AVL 트리(AVL Tree)

---

[1] AVL 트리의 정의

어떤 이진트리 노드 T의 balance factor(균형인수)를 $BF(t) = h_L - h_R$ 라 할 때, 모든 노드 T에 대해 $BF(t)$= -1, 0, 1 을 만족하는 이진 트리를 AVL 이라 한다.

---

[2] AVL 트리의 삽입

AVL 트리는 삽입 과정에서 회전을 통해 트리의 균형을 유지한다. 이 때, 회전은 새로 삽입된 노드 Y에 가장 가까우면서 Balance factor 가 +2 또는 -2가 되는 조상 노드 A에 의해 결정되며, 각 회전의 성질은 아래와 같다.

• LL : 새로운 노드 Y는 A의 왼쪽 서브트리의 왼쪽 서브트리에 삽입된다.

AVL 트리 LL 회전

• LR : 새 노드 Y는 A의 왼쪽 서브트리의 오른쪽 서브트리에 삽입된다.

AVL 트리 LR 회전

• RR : 새 노드 Y는 A의 오른쪽 서브트리의 오른쪽 서브트리에 삽입된다.

AVL 트리 RR 회전

• RL : 새 노드 Y는 A의 오른쪽 서브트리의 왼쪽 서브트리에 삽입된다.

AVL 트리 RL 회전

추가적으로 AVL 트리는 연속된 수를 삽입하는 경우에도 다음과 같이 트리의 균형을 유지할 수 있으며, 이는 AVL 트리가 BST와 비교했을 때 가지는 장점을 직접 보여준다.

연속된 수를 AVL 트리에 삽입하는 경우 

 

---

[3] AVL 트리 분석

• k를 키로 갖는 요소 탐색 : O(log n)
• j번째 요소 탐색 : O(log n)
• k를 키로 갖는 값 삭제 : O(log n)
• j번째 요소 삭제 : O(log n)
• 삽입 : O(log n)