第13章 红黑树(2)
13.2 旋转
查找树操作TREE-INSERT和TREE-DELETE，运行在n个key的红黑树上，花费时间O(lg n)。由于改动了树，所以结果树可能不符合13.1节列举的红黑树的性质。为了恢复这些性质，我们必须改变树中一些结点的颜色和修改一指针结构。
我们通过旋转来修改指针结构，它是一个局部操作使查找树保持二叉查找树的属性。图13.2展示了两种旋转：左旋和右旋。当我们对结点x进行左旋时，我们假设y是x的右孩子并且不是T.nil； x可以是树中任意右孩子不空的结点。左旋的“轴”是沿着x到y的。它使y成为子树的根，x成为y的左孩子，y左孩子成为x的右孩子。
LEFT-ROTATE伪代码假设x.right≠T.nil和root的双亲为T.nil。
图13.2 二叉查找树的左旋操作。左旋操作LEFT-ROTATE(T,x)通过修改常数个指针来改变两个结点的结构把右边的结点的结构变成左边的结构。相反的右旋操作RIGHT-ROTATE(T,y)将左边的结构变成右边的结构。α、β和γ表示任意形态的子树。旋转操作要保持二叉树的性质：α子树上的所有keys要小x.key,x.key要小于β子树上的所有keys，β子树的keys要小于y.key，y.key要小于γ子树上的所有的keys。
图13.3 展示了LEFT-ROTATE如何修改二叉查找树的实例。代码跟RIGHT-ROTATE是对称的。LEFT-ROTATE和RIGHT-ROTATE的运行时间者是O(1)。一次旋转只修改了指针；结点其它属性都保持不变。
图13.3 方法LEFT-ROTATE(T,x)如何修改一棵二叉查找树的实例。中序遍历输入树和中序遍历修改过后的树产生相同的key序列。
练习
13.2-1 写出RIGHT-ROTATE方法。
13.2-2 证明在任意n结点的二叉查找树上，刚好有n-1种可能的旋转。
13.2-3 设a,b,c分别是α、β和γ的任意结点，在图13.2的左侧。如图在结点x上做一次左旋转a,b,c的深度是如何变化的？
13.2-4 证明任意n结点的二叉查找树经过O(n)次旋转得其它任意形态的n结点二叉查找树。（提示：首先证明最多通过n-1次右旋可以将树的结构变成右链的形态。）
13.2-5 我们说如果通过一系列的调用RIGHT-ROTATE可以从二叉查找树T1转换成T2，那么二叉查找树T1右转（right-convert)成T2 。举出一个例子T1和T2，使得T1不能右转成T2。然后证明如果树T1右转成T2，那么它可以通过调用O(n^2)次RIGHT-ROTATE得到。
全文下载：第13章 红黑树
聂松松现在怎么样了？很是想念你，哈哈。我们悠悠现在快有2000W用户了
@段洪义
嗯，恭喜恭喜哈，再接再厉，做中国好导航。