left rotate를 수행하는 간단한 수도코드를 작성해보세요 {red black tree}
노드 u를 기준으로 왼쪽 회전하는 경우부터 설명하겠습니다. u의 오른쪽 자식을 r, 부모를 p라고 하겠습니다.
- u가 루트노드인 경우, 루트노드를 r로 할당합니다.
- u의 오른쪽 자식을 r.left로 수정합니다.
- 마찬가지로 r.left.parent를 u로 수정합니다. 이로써 r의 왼쪽 자식의 서브트리가 u의 오른쪽 자식으로 편입됐습니다.
- 만약 u가 p의 왼쪽 자식이었다면,
- u.p.left = r 으로 수정합니다.
- 오른쪽 자식이었다면,
- u.p.right = r로 수정합니다. 원래 u 자리였던 노드를 r이 채웠기 때문입니다.
- r.parent = p
- u.parent = r
- r.left = u
