[자료구조]탐색 2 (12-1-2) RR회전

이제 어느정도 눈치가 있다면!
RR회전은 Right Right 상태의 이진 탐색 트리를 회전시킨다는것임을 알것이다!
그리고 이것은

"RR상태와 LL상태의 차이점,회전의 유일한 차이점은 방향아닌가요?" 라는것에!

맞다!!
유일한 차이점은 방향이다!!!
참고로 LL회전을 가리켜 "오른쪽 회전"이라 한다.
5가 저장된 노드가 오른쪽 방향으로 회전한 모습을 보이기 때문이다.
진짜루 방향만 다르다 뿐이지 완전 같은 형식이다.
우리가 주목해야할 두 가지는 다음과 같다.

• 5가 저장된 노드가 7이 저장된 노드의 왼쪽 자식 노드가 되었다.
• T3는 5가 저장된 노드의 오른쪽 서브 트리가 되었다.

이를 pNode와cNode로 표현하면 다음과 같다.
(편의를 위해 pNode =PN, cNode = CN이라고 하겠다.)

• PN을 CN의 왼쪽 자식 노드가 되게했다 - 연산 1
• CN의 왼쪽 서브 트리를 PN의 오른쪽 서브트리가 되게했다 - 연산 2

이는 즉 !

ChangeRightSubTree(pNode,GetLeftSubTree(cNode)); - 연산 2
ChangeLeftSubTree(cNode,pNode); - 연산 1

이다.

CN의 왼쪽 서브 트리의 이동이 우선이기에 연산2가 선행 되어야한다!
그렇지 않다면 연산1에 의해서 CN의 왼쪽 서브트리의 주소 값을 잃게된다!!