리밸런싱이 필요한 세 번째 상태와 LR회전
이제 LR을보고..아!
"LR회전이란 LR상태에서의 리밸런싱을 위한 회전방법이겠군!?"이라고 짐작하여
"LR상태는 자식 노드가 왼쪽 하나! 그리고 이어서 오른쪽 하나 달린 상태를 뜻하겠군!!"
이라고 웬만한 눈치가 있다면 생각할것이다!
정답이다!!
이제 이 상태를 그림으로 보자.
간단한 예시와 일반화한 모습이다.
LR상태는 LL,RR상태보다 균형을 잡기 까다로운데
그 이유는 한 번의 회전으로는 균형을 잡을 수 없기 때문이다.
따라서
"LR상태를 한 번의 회전으로 균형이 잡히는 LL상태나 RR상태로 일단 바꾼다."
그렇다! 이미 배운것을 응용하는것이다!
그렇다면 위의 생각대로 바꿀수 있을까!?
그렇다!!
바로 이 방법을 이용하는것이다.
이 RR회전의 부수적인 효과를 이용할 수 있는데
- 부모 노드와 자식 노드의 관계가 바뀌었다.
- 오른쪽으로 형성되었던 부모와 자식의 관계가 왼쪽으로 바뀌었다.
이다!
그렇다면 어떻게 이용할까?
위 그림은 앞서 RR의 부수적인 효과를 이용하여 LR상태를 LL상태로 바꾸는 과정을 보여준다!
물론 이것도 이진 탐색 트리의 기본 조건을 만족한다.
이제 이 트리를 LL회전을 시키면 리밸런싱이 완료된다.
정리하자면 위와 같다!!
어떤가!
루트 노드에서 왼쪽 서브트리를 때고 RR회전을 시킨후 다시 붙이고 LL회전을 하는것이 끝이다!!!
리밸런싱이 필요한 네 번째 상태와 RL회전
당연빠따로!
LR상태와 반대인것이 RL상태이다.
그렇기에
LR회전 : 부분적 RR회전에 이어서 LL회전
RL회전 : 부분적 LL회전에 이어서 RR회전
이라고 생각할것이다!
정답이다!!
그럼 바로 회전을 해보자!
어떤가!
이 또한 부분적LL회전후 RR회전을 하면 LR회전이 완료된다.
이렇게 말이다!
이제 기본적인 개념들을 이해 했으니 구현해보자!!!
