# 树旋转

## 图示

```        +---+                          +---+
| Q |                          | P |
+---+                          +---+
/     \     right rotation     /     \
+---+   +---+  ------------->  +---+   +---+
| P |   | Z |                  | X |   | Q |
+---+   +---+  <-------------  +---+   +---+
/     \          left rotation         /     \
+---+   +---+                          +---+   +---+
| X |   | Y |                          | Y |   | Z |
+---+   +---+                          +---+   +---+
```

```                                                                  __
/  \
+---+                      /  +---+
| Q |                     /   | Q |
+---+     +---+              +---+ /    +---+
+---+              | P |    /     \      R1     | P |/    /     \              +---+
| Q |     R0       +---+   /     +---+ ----->   +---+    /     +---+   R2      | P |
+---+   ----->    /     \ /      | Z |         /        /      | Z | ----->    +---+
/     \         +---+   +---+     +---+      +---+    +---+     +---+          /     \
+---+   +---+      | X |   | Y |                | X |    | Y |                 +---+   +---+
| P |   | Z |      +---+   +---+                +---+    +---+                 | X |   | Q |
+---+   +---+              __                                                  +---+   +---+
/     \                    /  \                                                        /     \
+---+   +---+     L2       +---+  \                       +---+                L0      +---+   +---+
| X |   | Y |   <-----     | P |   \                      | P |              <-----    | Y |   | Z |
+---+   +---+              +---+    \ +---+      L1       +---+     +---+              +---+   +---+
/     \    \| Q |    <-----    /     \    | Q |
+---+     \    +---+           +---+     \   +---+
| X |      \        \          | X |      \ /     \
+---+     +---+    +---+       +---+     +---+   +---+
| Y |    | Z |                 | Y |   | Z |
+---+    +---+                 +---+   +---+
```

## 实现

```func rotate_right(pivot):
let parent = pivot.parent
let root = parent.parent
// R0
parent.left = pivot.right
if pivot.right != nil: pivot.right.parent = parent
// R1
pivot.parent = root
if parent == root.left:
root.left = pivot
else:
root.right = pivot
pivot.right = parent
parent.parent = pivot
```

```func rotate_left(pivot):
let parent = pivot.parent
let root = parent.parent
// L0
parent.right = pivot.left
if pivot.left != nil: pivot.left.parent = parent
// L1
pivot.parent = root
if parent == root.left:
root.left = pivot
else:
root.right = pivot
pivot.left = parent
parent.parent = pivot
```

```func rotate_right(root, parent):
assert root.left == parent || root.right == parent
let pivot = parent.left
// R0
parent.left = pivot.right
// R1
if parent == root.left:
root.left = pivot
else:
root.right = pivot
pivot.right = parent
```
```func rotate_left(root, parent):
assert root.left == parent || root.right == parent
let pivot = parent.right
// L0
parent.right = pivot.left
// L1
if parent == root.left:
root.left = pivot
else:
root.right = pivot
pivot.left = parent
```