算法导论笔记之红黑树

13、红黑树
13.1红黑树的性质
红黑树是一颗二叉搜索树，通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，
因而是近似平衡的。树中的节点包括5个属性：color、key、left、right、p。
一颗红黑树满足下面5条性质：
1、每个节点或是红色的、或是黑色的。
2、根节点是黑色的
3、每个叶子节点(NIL)是黑色的
4、如果一个节点是红色的，则它的两个子节点都是黑色的
5、对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
从某个节点x出发到达一个叶节点的任意一条简单路径上的黑色节点数成为该节点的黑高，记为bh(x).红黑树的黑高为其根节点的黑高。
引理13.1：
一颗有n个内部节点的红黑树的高度至多为2*lg(n+1).

练习:
13.1-2 ：
36将成为35的右孩子。不管将插入的节点标记为红色还是黑色，所得到的树都不再是红黑树。插入黑色节点，将不满足性质5；插入红色节点，不满足性质4。
13.1-3
是。因为将根节点由红色变为黑色后，其各个子节点的颜色没有改变，所以仍然能够满足性质1、3、4、5.
13.1-4
可能的度为2,3,4。
2：根节点有两个黑色的子节点；3：根节点有一个红色节点和一个黑色节点，红色节点下面有两个黑色子节点。4：根节点有两个红色子节点，每个红色节点下包含两个黑色子节点。
最终所得树的高度等于红黑树的黑高。
13.1-5：
显然，最短路径Path_Shortest>=bh(x).根据性质4，在x到其后代的任意一条简单路径height(x)上，如果出现一个红色节点，则它的孩子为黑色节点，
并且叶子节点为黑色，因此，在x到其后代的任意一条路径上，黑色节点至少占一半。也就是说，bh(x) >= height(x)/2.
即height(x) <= 2*bh(x)<= 2*Path_Shortest.由于height(x)是任意的，所以，最长路径至多是最短路径的2倍。
13.1-6
每个黑色节点下包含两个红色子节点时，内部节点最多，为2^2k - 1.所有节点均为黑色时，内部节点最少，为2^k - 1.
13.1-7
和13.1-6类似，红黑比最大为2:1，最小为0.

13.2旋转
由于二叉搜索树的插入和删除操作对树进行了修改，结果可能违反红黑树的性质。为了维护这些性质，必须对二叉搜索树中的节点进行旋转。旋转是能够保持二叉搜索树性质的局部操作，分为左旋和右旋两种。

左旋的伪代码为：
LeftRotate(T,x)
y = x.right;
x.right = y.left;
if(y.left != T.nil)
y.left.p = x;
y.p = x.p;
if(x.p == T.nil)
T.root = y;
else if(x == x.p.left)
x.p.left = y;
else
x.p.right = y;
y.left = x;
x.p = y;

右旋的伪代码为：
RightRotate(T,y)
x = y.left;
y.left = x.right;
if(x.right != T.nil)
x.right.p = y;
x.p = y.p;
if(y.p == T.nil)
T.root = x;
else if(y == y.p.left)
y.p.left = x;
else
y.p.right = x;
x.right = y;
y.p = x;

练习：
13.2-1：见右旋的伪代码
13.2-2：每个节点都可以和它的父节点构成一种旋转(左孩子右旋，右孩子左旋)，根节点没有父节点。因此，n个节点的二叉搜索树中，恰有n-1中旋转。
13.3-3：显然，a，b，c的深度变化和α，β，γ的深度变化是相同的，因此，左旋后，a的深度加以，b的深度不变，c的深度减一
13.3-4： 根据13.2-2可知，最多需要n-1次右旋，即可将任意一颗二叉搜索树变为一条右侧伸展的链；反之可得，最多需要n-1次左旋，即可将一条右侧伸展的链转换成任意一颗二叉搜索树。由此可知，任意两棵二叉搜索树之间的转换最多需要2*(n-1)次旋转，即任意两棵二叉搜索树之间的相互转变所需旋转的上界为O(n)。

13.3 插入