CH12-1 균형 잡힌 이진탐색 트리:AVL트리의 이해(5)

12-1. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 ⑤

이번시간에는 LR상태와 RL상태에 대해 이론적으로 접근해보자.

LR상태란 무엇인가?

LR상태도 왼쪽으로 노드가 더 달린 불균형한 상태인데, 다 LL처럼 왼쪽으로만 달린게 아니라

이렇게 왼-오 형태의 불균형 상태이다.

이걸 균형잡는건 LL 이나 RR만큼 간단하진 않다. 전처럼 한번의 회전으로 균형이 잡히지 않기 때문..

이걸 균형잡는 좋은 전략은, 우선 LR을 LL상태 또는 RR상태로 바꾸는 것이다. 한번에 균형잡는것보다 이게 훨씬 간단하기 쉽다.

LR상태를 LL상태로 바꾸는게 우선이면, 어떻게 바꾸는가? 어떤 규칙에 의거하는가?

LR상태의 일반화는 다음과 같다.

위의 그림에서 노란색 점선이 LL상태로 만들기 위해 우선 변경되어야 하는 영역이다. 3이 1의 자식으로 가야한다… 이걸 어떻게 바꾸는가?

바로 RR회전이다! 부분에 RR회전을 가하면 LL상태가 된다.

일반적인 RR회전은,

이거지만, 우리가 적용하는 RR회전은 위의 그림에서 노드 9가 NULL로 대체된

이런 상황이다. RR회전은 5와 7의 주소만 필요하기때문에 단말이 NULL인경우에도 적용할 수 있다.