[자료구조] AVL 트리 :: 늦깍이 IT

---

이전 포스팅 [이진탐색트리]를 참고하시기 바랍니다.

이 포스팅은 윤성우 저자의 '자료구조'를 참고했습니다.

---

[ AVL 트리란? ]

AVL트리는 이진탐색트리의 단점인 불균형 트리를 보완하기 위한 방법으로써 데이터가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리이다.

AVL 트리의 핵심 개념중 하나가 균형인수, Balance Factor(BF)이다. 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다. 두 서브트리의 높이가 같다면 BF 값은 0이다.

아래 그림에서 각 노드에 대한 균형인수 값을 확인해보자. 노드 7의 왼쪽 서브트리의 높이는 3이고, 오른쪽 서브트리의 높이는 1이므로 균형인수 값은 2가된다.

각 노드들의 균형인수의 절대값이 1보다 크다면 트리의 균형이 무너진 상태라고 할 수 있으므로 리밸런싱이 필요하다.

[ 리밸런싱 ]

AVL 트리의 균형이 무너진 상태는 4가지로 정리된다. 그리고 각 상태 별 리밸런싱 방법에도 차이가 있다.

1. LL 상태

아래 그림에서 노드5의 균형인수 값이 +2임을 알 수 있다. 이 뜻은 노드 5의 왼쪽 서브트리의 높이가 오른쪽 서브트리의 높이보다 2크다는 것을 의미한다.

이처럼 균형인수 값이 +2가 된 상태를 가리켜 'Left Left 상태'라고하며 이를 줄여서 LL상태라고 한다. 그리고 이 LL상태에서 발생한 불균형을 해소하기 위란 리밸런싱 방법을 가리켜 LL회전이라고 한다.

위 그림에서 노드 5가 노드3의 오른쪽 자식노드가 되었다. 이처럼 LL회전은 균형인수의 값이 2인 노드를 균형인수의 값이 1인 노드의 오른쪽 자식노드로 만드는 것이다.

위의 왼쪽 그림에서 LL회전을 하게되면, 오른쪽 그림처럼 트리의 형태가 변하는 것을 알 수 있다.

여기서 주의해야할 점은 T3이다. 노드5가 노드3의 오른쪽 자식노드가 되야하기 때문에 기존에 있는 T3 서브트리 또한 자리를 이동해야 한다. 즉, T3는 노드5의 왼쪽 자식노드가 된다는 것을 유의하자.

2. RR 상태

RR상태는 LL상태와 방향만 바뀐 상태이다.

위의 왼쪽 그림에서 RR회전을 하게되면, 오른쪽 그림처럼 트리의 형태가 변하는 것을 알 수 있다.

여기서 주의해야할 점은 T3이다. 노드5가 노드3의 왼쪽 자식노드가 되야하기 때문에 기존에 있는 T3 서브트리 또한 자리를 이동해야 한다. 즉, T3는 노드5의 오른쪽 자식노드가 된다는 것을 유의하자.

3. LR 상태

LR상태는 자식 노드가 왼쪽으로 하나, 그리고 이어서 오른쪽으로 하나 달린 상태를 뜻한다. 

위의 그림의 트리는 LR상태임을 확인할 수 있다. 다만, LR상태에서 회전을 어떻게 해야할까? 

LR상태는 LL상태와 RR상태처럼 한 번의 회전으로 균형을 잡을 수 없다. 그렇기 때문에, LR 상태는 우선 한 번의 회전으로 LL 상태나 RR 상태로 먼저 바꿔야한다.

위 그림처럼, LR 상태에 있는 트리의 일부를 떼어 RR회전을 한 뒤, 루트노드에 다시 연결하면 LL상태로 바꿀 수 있다.

4. RL 상태

RL상태는 자식 노드가 오른쪽으로 하나, 그리고 이어서 왼쪽으로 하나 달린 상태를 뜻한다. LR상태와 마찬가지로 한 번의 회전으로 LL상태나 RR상태로 먼저 바꿔야 한다.

위 그림처럼, RL 상태에 있는 트리의 일부를 떼어 LL회전을 한 뒤, 루트노드에 다시 연결하면 RR상태로 바꿀 수 있다.