数据结构选讲树的旋转（Rotation）

摘要：

本文讨论维护树的平衡的重要手段之一：旋转。掌握旋转是掌握高级树结构的基础。

单旋转：

如图：X, Y为带旋转结点，a, b, c为这两个结点的子树。图中从左到右顺序为左旋转，反之为右旋转。不难得出，旋转的关键在于处理好指针的重定向。

于是我们容易得出旋转的过程：过程看似复杂，其实就是重新链接受旋转影响的结点的指针。以左旋转为例：

 1 void LeftRotate(BST_Node *root, BST_Node *x) {
 2 
 3     BST_Node *y = x->right;
 4     x->right = y->left;
 5     y->left->parent = x;
 6     y->parent = x->parent;
 7     if (x->parent == NULL)
 8         root = y;
 9     else {
10         if (x == x->parent->left)
11             x->parent->left = y;
12         else
13             x->parent->right = y;
14     }
15     y->left = x;
16     x->parent = y;
17 
18     return;
19 }

双旋转：

双旋转事实上就是单旋转的组合，如图：

图中，先对Y结点进行了一次左旋转，使得三结点位于同一方向，然后对X结点右旋转，得到了平衡过后的三个结点。

1 void LeftRightRotate(BST_Node *root, BST_Node *x) {
2     
3     LeftRotate(root, x->right);
4     RightRotate(root, x);
5 }