Introduction to Algorithms 3rd Edition
Part III - Data Structures
Chapter 13: Red-Black Trees
为了解决二叉排序树在最坏情况下的插入、删除和查找等操作的性能，本质上是尽量将树的高度维持在lg(n)左右，出现了一些二叉排序树的变种，比较著名的有AVL树，红黑树等。一般认为，红黑树的平均性能较AVL树更好，插入、删除所需的旋转操作更少，因而应用更广泛。
红黑树具有以下性质：
1. 每个节点非黑即红
2. 根节点为黑
3. 所有叶子节点（NIL）都为黑
4. 如果一个节点为红，那么它的两个孩子都为黑
5. 对任何一个节点，从它到所有它的叶子节点的路径上黑色节点个数相等
为了方便，定义一个全局空指针NIL，所有叶子节点都是NIL，颜色为黑，根节点的父节点为NIL。
可以证明，一棵有着n个内节点的红黑树的高度至多为2lg(n+1)。
为了保持红黑树的高度在O(lgn)，需要在插入和删除节点时对红黑树进行调整，而调整的主要手段就是对节点进行旋转，以此来维持红黑树的平衡。当然旋转之后可能会导致违背红黑树性质的情况出现，这时就需要对红黑树做进一步的调整。对一个节点左旋，是将它与右孩子旋转；对一个节点右旋，是将它与左孩子旋转。
由于红黑树特性的复杂性，相较二叉排序树，其插入和删除操作也更为复杂，下面详细分析。
对于插入操作，在二叉排序树的插入操作基础上，需要做一点修改。新插入的节点，如果将它的颜色设为黑，那么很显然会影响到红黑树的第5条特性；如果将它的颜色设为红，那么又可能会影响到第4条特性。如果违背第5条特性的话，需要的修正操作会更多更复杂，因而我们首先将新插入的节点的颜色设置为红。不妨记新插入的节点为z，如果z的父节点颜色为黑，那么不需要任何额外修正（除非z是根节点）；如果z的父节点颜色也为红，那么就需要调整操作。由于对称性，我们只考虑z的父节点z.p为左孩子的情况（z.p = z.p.p.left），在这个条件下，根据z是左孩子还是右孩子，以及z的叔叔节点的颜色，又可以分为四种情况：
a. z为左孩子，叔节点为红
b. z为右孩子，叔节点为红
c. z为右孩子，叔节点为黑
d. z为左孩子，叔节点为黑
首先来看a和b，如下图所示。在这种情况下，只需将z的父节点和叔节点都设置成黑，z的爷节点设置成红，之后，z的爷节点可能会违背性质4，因此继续重复，将z设置成z.p.p继续。
再来看c和d，如下图所示。c可以通过对z的父节点左旋来转换成d，而d则只需对z的爷节点右旋，并改变z的父节点和爷节点的颜色来完成调整。可以看出，每次调整前后，所有叶子节点的路径长度（黑色节点个数）都没有改变。因此是正确的。
具体的调整代码如下所示。注意到第17行需要把T的根节点设置为黑，这是因为当跳出循环时，z可能恰好是T的根节点并且为红，因此需要将它设置为黑。可以看出，每次插入一个节点至多会进行两次旋转操作，而一旦执行了右旋操作，必然退出循环，调整结束。时间复杂度是树的高度O(lgn)。
RB-INSERT-FIXUP(T, z)
1 while z.p.color == RED
2 if z.p == z.p.p.left
3 y = z.p.p.right
4 if y.color == RED
5 z.p.color = BLACK // case 1
6 y.color = BLACK // case 1
7 z.p.p.color = RED // case 1
8 z = z.p.p // case 1
9 else
10 if z == z.p.right
11 z = z.p // case 2
12 LEFT-ROTATE(T, z) // case 2
13 z.p.color = BLACK // case 3
14 z.p.p.color = RED // case 3
15 RIGHT-ROTATE(T, z.p.p) // case 3
16 else (same as then clause with 'right' and 'left' exchanged)
17 T.root.color = BLACK至于节点的删除，仍然是在二叉排序树节点删除的基础上修改。最重要的是要记录删除之后真正缺少的颜色是什么，如果是红色那无所谓，如果是黑色，那就会影响到它的子树。
先看删除操作的代码，之后再分析删除之后调整红黑树的代码。
RB-DELETE(T, z)
1 y = z
2 y-original-color = y.color
3 if z.left == T.nil
4 x = z.right
5 RB-TRANSPLANT(T, z, z.right)
6 else if z.right == T.nil
7 x = z.left
8 RB-TRANSPLANT(T, z, z.left)
9 else
10 y = TREE-MINIMUM(z.right)
11 y-original-color = y.color
12 x = y.right
13 if y.p == z
14 x.p = y
15 else
16 RB-TRANSPLANT(T, y, y.right)
17 y.right = z.right
18 y.right.p = y
19 RB-TRANSPLANT(T, z, y)
20 y.left = z.left
21 y.left.p = y
22 y.color = z.color
23 if y-original-color == BLACK
24 RB-DELETE-FIXUP(T, x)代码中需要特别注意的地方是：x取代了y原来的位置，y的颜色被设置成z的颜色，因此y的颜色缺失了。如果y的颜色是红，那么不影响红黑树性质；如果y的颜色是黑，那么就可能会影响，需要进行调整。
由于x取代了y的位置，而y为黑。如果x为红，那么直接将x设为黑即可；如果x为黑，需要将x对黑的贡献改为2。具体调整代码如下：
RB-DELETE-FIXUP(T, x)
1 while x != T.root and x.color == BLACK
2 if x == x.p.left
3 w = x.p.right
4 if w.color == RED
5 w.color = BLACK // case 1
6 x.p.color = RED // case 1
7 LEFT-ROTATE(T, x.p) // case 1
8 w = x.p.right // case 1
9 if w.left.color == BLACK and w.right.color == BLACK
10 w.color = RED // case 2
11 x = x.p // case 2
12 else
13 if w.right.color == BLACK
14 w.left.color = BLACK // case 3
15 w.color = RED // case 3
16 RIGHT-ROTATE(T, w) // case 3
17 w = x.p.right // case 3
18 w.color = x.p.color // case 4
19 x.p.color = BLACK // case 4
20 x.right.color = BLACK // case 4
21 LEFT-ROTATE(T, x.p) // case 4
22 x = T.root // case 4
23 else (same as then clause with 'right' and 'left' exchanged)
24 x.color = BLACK
只考虑x是左孩子的情况，又可以分为四种情况：
1. x的兄弟节点w是红色。如下图所示，由于w是红色，因此x的父节点、w的孩子节点都是黑色，对x的父节点左旋，并修改x父节点和w的颜色，这时x的兄弟节点颜色为黑，转换为其它情况。
2. x的兄弟节点w为黑，并且w的孩子都为黑。如下图所示，不管x的父节点是什么颜色，可以将w改成红色，并将x修改为父节点，这样x就往上移了一个节点，继续循环。
3. x的兄弟节点w为黑，w的左孩子为红，右孩子为黑。如下图所示，将w右旋，并修改新的w及其右孩子颜色，可以将新的w右孩子改成红，转换成case 4
4. x的兄弟节点w为黑，w的右孩子为红。如下图所示，将x的父节点左旋，并修改几个节点的颜色，可以结束调整（通过将x设置为T.root）。
Exercises
13.1-3
很显然仍然是
13.1-5
最短的情况是x到叶子节点都是黑色节点，最长的情况是x到叶子节点的路径红黑相间。后者至多是前者的两倍
13.1-6
如果所有节点都是黑色，那么内节点个数为2^k-1；如果是红黑相间，那么内节点个数为2^2k -1
13.1-7
最大的比例是2，所有黑色节点的孩子都是红节点，每个黑色节点都对应两个红色节点，因此比例为2；最小的比例为0，没有红色节点
13.2-1
将LEFT-ROTATE中的x与y对换，left与right对换即可
13.2-2
因为旋转是基于两个节点的，而两个节点必然确定一条边，n个节点的树有n-1条边，因此恰好有n-1种旋转
13.2-3
如果y为黑，那么α高度加1；如果x为黑，那么γ高度减1；β高度不变
13.2-4
任何一个树至多通过n-1次右旋可以转换成right-going chain
13.2-5
1(#, 2)不能通过右旋转换成2(1, #)
如果T1能通过右旋转换成T2，那么可以这样操作：首先通过右旋操作将T1中与T2的根节点对应的那个节点旋转成根节点，之后再递归地对左右子树操作，复杂度是：
T(n) = O(n) + T(k) + T(n-1-k)，也即T(n) = O(n) + T(n-1)，因此T(n) = O(n^2)
P.S. 我也不知道这样证明对不对……
13.3-4
设置成红色节点只有在case 1和case 3才出现：将z.p.p设置成红，如果z.p.p是T.nil，那么z.p就是根节点，为黑，根本就不会进入循环；再来看case 2，我们在将z.p.p设置为红之前将z和z.p交换了，但是交换之后进行了旋转操作，z.p.p仍然不变，因此case 2也没有问题。所以这种情况不会发生
13.4-7
直接看答案吧，哈哈
