【算法导论】学习笔记——第13章红黑树

浏览数：27 / 时间：2015年06月08日

红黑树（red-black tree）是许多平衡搜索树中的一种，因此基本操作（查询、删除、搜索）等在最坏情况下的时间复杂度均为O(lgn)。
13. 1 红黑树的性质
红黑树时一棵二叉搜索树，并且在每个结点上增加了一个属性表示颜色：红色或黑色。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，
红黑树确保没有一条路径会比其它路径长出2倍。因而是近似于平衡的。
一棵红黑树是满足下面红黑性质的二叉搜索树：
1. 每个结点是红色或黑色；
2. 根结点是黑色的；
3. 每个叶结点（NIL）是黑色的；
4. 如果一个结点是红色的，则它的两个子结点都是黑色的；
5. 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。（黑高相等）
从某个结点x出发到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高（black-height）。

13.1-1
均不是，若结点为红色不满足性质4；若结点为黑色不满足性质5.

13.1-2
仍旧是红黑树，满足性质1-5

13.1-3
这个题目描述的不清楚，其实就是把红色结点和黑结点归并到一起组成一个新的结点。因此，
当黑色父结点的子结点均为黑色时，度为2；
当黑色父结点仅含一个黑色子结点时，度为3；
当黑色父结点的两个子结点均为红色时，度为4.
由于红色结点全部被吸收，即仅余下黑结点。由红黑树性质5可知叶结点深度均相同。

13.1-4
这个题目描述的不清楚，其实就是把红色结点和黑结点归并到一起组成一个新的结点。因此，
当黑色父结点的子结点均为黑色时，度为2；
当黑色父结点仅含一个黑色子结点时，度为3；
当黑色父结点的两个子结点均为红色时，度为4.
由于红色结点全部被吸收，即仅余下黑结点。由红黑树性质5可知叶结点深度均相同。

13.1-5
可以先形式化验证, 考虑结点x的黑高为BH(x), 红高为RH(x), 而RH(x)<=BH(x). 结点x到后代叶结
点的最长路径为BH(x)+RH(x), 最短路径为BH(x). 因此，至多为2倍。再形象地考虑一下路径会是什么样的。
设x的黑高为h，当x的颜色为黑色，则最长路径的着色为黑-红-黑-...-红-黑-红-黑, 长度为(2h-2)，最短路径的着色为黑-黑-...-黑-黑，长度为(h-1), 比值为2 。
当x的颜色为红色，则最长路径的着色为红-黑-红-黑-...-红-黑-红-黑, 长度为(2h-1)，最短路径的着色为红-黑-黑-...-黑-黑，长度为h, 比值趋近于2 。
因此，综上可知比值最多为2.

13.1-6
内部结点最多为2^(2k)-1, 显然为一棵完全数，每层结点颜色为黑-红交替。
内部结点最少为2^k-1，显然为一棵全黑树。

13.1-7
比值最大为2:1, 比值最小为0（全黑树）。

13.2 旋转