[열혈자료구조] 12강. 탐색(Search) 2 : AVL 트리

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

앞선 포스팅에서 살펴 본 이진 탐색 트리를 통한 searching은 일반적으로 시간 복잡도가 O(logN)이다. 그러나, 트리가 불균형할 경우, 시간 복잡도가 O(N)까지 상승할 수 있다.

https://cascade.tistory.com/97

[열혈자료구조] 11강. 탐색(Search) 1

 

예를 들어, 아래와 같은 트리가 "불균형한 트리"이다.

이러한 트리의 모양은 5, 4, 3, 2, 1 순으로 데이터를 저장했을 때 생긴다. 반면, 3, 2, 1, 4, 5 순으로 데이터를 저장하면 아래와 같이 균형잡힌 트리의 모습이 된다.

즉, 데이터의 저장 순서에 따라 이진 탐색의 효율이 달라질 수 있는 것이다. 이를 해결하기 위해, 본 포스팅에서는 균형잡힌 이진 트리를 살펴보고자 한다. 균형잡힌 이진 트리는 아래와 같은 종류가 있으며, 특히 AVL 트리를 다룰 것이다.

• AVL 트리
• 2-3 트리
• 2-3-4 트리
• Red-Black 트리
• B 트리

AVL 트리와 Balance Factor

AVL 트리란 Adelson-Velsky, Landis에 의해 개발된 가장 오래된(1960년대) 균형잡힌 트리이다. AVL 트리는 노드가 추가되거나 삭제될 때 스스로 구조를 변경(rebalancing)하여 균형을 잡는 트리이다. 이때 Balance Factor는 아래와 같이 정의한다.

Balance Factor(BF) = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이

 

BF의 절댓값이 커질수록 트리의 균형이 깨진 것이라 할 수 있다. AVL 트리는 BF 값이 2 이상이 되면 rebalancing을 한다.

AVL 트리의 rebalancing 상황

 

AVL 트리는 총 4가지 상황에서 rebalancing이 일어난다.

1. LL 상태: 자식 노드 두 개가 왼쪽으로 연속하여 연결된 경우 - LL 회전으로 rebalancing
2. RR 상태: 자식 노드 두 개가 오른쪽으로 연속하여 연결된 경우 - RR 회전으로 rebalancing
3. LR 상태: 자식 노드가 왼쪽->오른쪽으로 연속하여 연결된 경우 - LR 회전으로 rebalancing
4. RL 상태: 자식 노드가 오른쪽->왼쪽으로 연속하여 연결된 경우 - RL 회전으로 rebalancing

먼저, LL회전은 아래와 같이 LL 상태에서 pNode를 cNode의 오른쪽 자식으로 내리는 방법이다.

이때 cNode에 원래 있던 오른쪽 서브트리는 pNode의 왼쪽 서브트리로 들어간다. 아래는 조금 더 일반화된 예시이다.

출처: javatpoint

 

두 번째로, RR rotation은 LL rotation과 완전히 똑같이, 방향만 반대로 수행해주면 된다.

세 번째로, LR 회전은 위의 LL이나 RR 상태처럼 한 번에 균형을 잡을 수 없다. 따라서, LR 회전은 RR 회전을 통해 LL 상태로 만들고 LL회전을 하여 균형을 잡는다. 아래 그림처럼 A, B, C가 LR 상태로 연결되어 있다고 할 때, B, C만 먼저 따로 떼어 RR 회전을 시킨다. 이때 C의 오른쪽 서브트리(아래 그림의 T3)는 NULL이어도 된다. 이제 C의 왼쪽 서브트리의 루트 노드로 B가 들어오게 되고, 다시 A와 연결하면 LL 상태가 된다. 따라서 마지막으로 LL회전을 해 주면 LR 회전이 종료된다.

네 번째로, RL 회전은 LR 회전과 모든 것을 정반대의 방향으로 하면 된다.