不懂的东西还有很多，随着不断的学习，不懂的东西更多，无法消灭更多不懂的东西，那就不断的充实自己吧。 欢迎关注微信公众号：菜鸟的机器学习
分类： C/C++
2013-01-22 10:45:11
经过上一篇博文，相信对红黑树已经有了一定的了解。
个人觉得，这个红黑树，还是比较容易懂的（囧，对我感觉好难啊，原作者太强了）。
不论是插入还是删除，不论是左旋还是右旋，最终的目的只有一个：即保持红黑树的5个性质，不得违背。
再次重新阐述红黑树的五个性质：
一般的，二叉排序树，满足以下性质，即只有满足一定性质，才称之为红黑树。
（1）每个结点要么是红色，要么是黑色；
（2）根结点是黑的；
（3）每个叶节点，即空结点是黑的；
（4）如果一个结点是红的，那么的它的两个儿子都是黑的；
（5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点；
抓住了红黑树的五个性质，事情就好办多了。
如：
（1）红黑红黑，要么是红，要么是黑；
（2）根结点是黑；
（3）每个叶结点是黑色的；
（4）一个红结点，它的两个儿子必须都是黑的；
（5）每一条路径上，黑结点的数目等同；
本文所有的文字，都是参照下面十张图与算法导论来写的。
希望，你依照此文一点一点的往下看，看懂此文后，你对红黑树的算法了解程度，一定大增不少。
现在来具体深入剖析红黑树的算法，并教你逐步实现此算法。
此教程分为10个部分，每一个部分作为一个小节。且各个小节与给出的十张图片一一对应。
一、左旋与右旋
先明确一点：为什么要左旋？
因为红黑树插入或删除结点后，树的结构发生了变化，从而可能会破坏红黑树的性质。为了维持插入或删除结点后的树，仍然是一棵红黑树，有必要对树的结构做部分调整，从而恢复红黑树的原本性质。
而为了恢复红黑树性质而作的动作包括：
（1）结点颜色的改变（即重新着色）；
（2）结点的调整——即改变指针结构，即是通过左旋或右旋而达到目的。
经过这两个动作的调整，从而使插入或删除结点的树重新成为一棵新的红黑树。
请看下图：
在此，着重分析左旋算法：
左旋，如上图所示（左—>右），以x->y之间的链为“支轴”进行，使y成为该新子树的根，x成为y的左孩子，而y的左孩子则成为x的右孩子。
算法很简单，还有注意一点，各个结点从左到右，不论是左旋前还是左旋后，结点大小都是从小到大。
左旋代码实现，分为三步，注意看注释。
LEFT-ROTATE(T, x)
y ← right[x] ? Set y.
right[x] ← left[y] ? Turn y's left subtree into x's right subtree.
p[left[y]] ← x
p[y] ← p[x] ? Link x's parent to y.
if p[x] = nil[T]
then root[T] ← y
else if x = left[p[x]]
then left[p[x]] ← y
else right[p[x]] ← y
left[y] ← x ? Put x on y's left.
p[x] ← y
左旋和右旋都是对称的，且都是在O(1)时间内完成。因为旋转时只有指针被改变，而结点中的其他域都保持不变。
最后，贴出关于此左旋算法所画的图：
//此图优点bug。第4行的注释移动到第11行。如上述代码所示。
二、左旋的一个实例
不做过多的介绍，看下面的图，一目了然。
LEFT-ROTATE(T,x)的操作过程：
提醒：看下文之前，请首先务必明确，区别以下两种操作：
（1）红黑树插入、删除结点的操作
//如插入中，红黑树的结点操作：RB-INSERT(T,z)。
（2）红黑树已经插入、删除结点之后
为了保持红黑树原有的红黑性质而做的恢复与保持红黑性质的操作。
//如插入中，为了恢复和保持原有红黑性质所做的工作：RB-INSERT-FIXUP(T,z)。
三、红黑树的插入算法实现
RB-INSERT(T, z)
y ← nil[T] //y始终指向x的父结点
x ← root[T] //x指向当前树的根结点
while x ≠ nil[T]
do y ← x
if key[z] < key[x] //向左或向右
then x ← left[x]
else x ← right[x] //为了找到合适的插入点，x探测跟踪路径，直到x成为NIL为止
p[z] ← y //y置为插入结点z的父结点
if y = nil[T]
then root[T] ← z
else if key[z] < key[y]
then left[y] ← z
else right[y] ← z //上述几行代码，置z的相关指针
left[z] ← nil[T]
right[z] ← nil[T] //设为空
color[z] ← RED //将新插入结点z着为红色
RB-INSERT-FIXUP(T, z) //因为将z着为红色，可能会违反某一红黑性质
//所以，调用该函数来保持红黑性质
还记得，开头说的那句话么？
是的，时刻记住，不论是左旋还是右旋，不论是插入还是删除，都要记得恢复和保持红黑树的5个性质。
四、调用RB-INSERT-FIXUP(T,z)来保持和恢复红黑性质
while color[p[z]] = RED
do if p[z] = left[p[p[z]]]
then y ← right[p[p[z]]]
if color[y] = RED
then color[p[z]] ← BLACK ? Case 1
color[y] ← BLACK ? Case 1
color[p[p[z]]] ← RED ? Case 1
z ← p[p[z]] ? Case 1
else if z = right[p[z]]
then z ← p[z] ? Case 2
LEFT-ROTATE(T, z) ? Case 2
color[p[z]] ← BLACK ? Case 3
color[p[p[z]]] ← RED ? Case 3
RIGHT-ROTATE(T, p[p[z]]) ? Case 3
else (same as then clause
with "right" and "left" exchanged)
color[root[T]] ← BLACK
五、红黑树插入的三种情况，即RB-INSERT-FIXUP(T,z)
//这图有个小小的问题，读者可能会产生误解。图中左侧所表明的情况2、情况3所示的位置都要标上一点。
//请以图中表明的case1、case2、case3为准。
六、红黑树插入的第一种情况
为了保证阐述清晰，重述下RB-INSERT-FIXUP(T,z)的代码：
while color[p[z]] = RED
do if p[z] = left[p[p[z]]]
then y ← right[p[p[z]]]
if color[y] = RED
then color[p[z]] ← BLACK ? Case 1
color[y] ← BLACK ? Case 1
color[p[p[z]]] ← RED ? Case 1
z ← p[p[z]] ? Case 1
else if z = right[p[z]]
then z ← p[z] ? Case 2
LEFT-ROTATE(T, z) ? Case 2
color[p[z]] ← BLACK ? Case 3
color[p[p[z]]] ← RED ? Case 3
RIGHT-ROTATE(T, p[p[z]]) ? Case 3
else (same as then clause
with "right" and "left" exchanged)
color[root[T]] ← BLACK
//case1表示情况1，case2表示情况2，case3表示情况3
现在，先来透彻分析红黑树插入的第一种情况：
情况1：z的叔叔y是红色的
第一种情况，即下述代码。
if color[y] = RED
then color[p[z]] ← BLACK ? Case 1
color[y] ← BLACK ? Case 1
color[p[p[z]]] ← RED ? Case 1
z ← p[p[z]] ? Case 1
如上图所示，a图：z为右孩子；b图：z为左孩子。
只要p[z]和y（图a中，A为p[z]，D为y；图b中，B为p[z]，D为y）都是红色的时候，才会执行此情况1；
下面分析下图a的情况，即z为右孩子时。
因为p[p[z]]，即C为黑色，所以将p[z]、y都着为黑色（如上图a部分的右边），此举解决了z、p[z]都是红色的问题，将p[p[z]]着为红色，则保持了性质5。
OK，请看下图。
红黑树插入的第一种情况，到此结束。
七、红黑树插入的第二种、第三种情况
情况2：z的叔叔y是黑色的，且z是右孩子
情况3：z的叔叔y是黑色的，且z是左孩子
这两种情况，是通过z是p[z]的左孩子还是右孩子区别的。
参照上图，针对情况2，z是它父亲的右孩子，则为了保持红黑性质，左旋则变为情况3，此时z为左孩子。因为z、p[z]都为黑色，所以不违反红黑性质（注意：情况3中，z的叔叔y是褐色的，否则此种情况就变成了上述情况1了）。
OK，我们已经看出来了，情况2、情况3都违反性质4（即一个红结点的两个儿子都应是黑色的）。
所以，情况2—>左旋后—>情况3，此时情况3同样违反性质4，所以情况3进行右旋，得到上图的最后那部分。
注意：情况2、情况3只违反性质4，其他的性质1、2、3、5都不违反。
好的，最后看下画的图。
八、红黑树的删除部分
if left[z] = nil[T] or right[z] = nil[T]
then y ← z
else y ← TREE-SUCCESSOR(z)
if left[y] ≠ nil[T]
then x ← left[y]
else x ← right[y]
p[x] ← p[y]
if p[y] = nil[T]
then root[T] ← x
else if y = left[p[y]]
then left[p[y]] ← x
else right[p[y]] ← x
if y ≠ z
then key[z] ← key[y]
copy y's satellite data into z
if color[y] = BLACK //如果y是黑色的
then RB-DELETE-FIXUP(T, x) //则调用RB-DELETE-FIXUP(T,x)
return y //如y不是黑色的，是红色的，则当y被删除时，
//红黑性质仍然得以保持。不做操作，返回。
//因为：1、树中各结点的黑高度没有变化。2、不存在两个相邻的红色结点
// 3、因为入口y是红色的，就不可能是根。所以，根仍然是黑色的
九、红黑树删除之四种情况
while x ≠ root[T] and color[x] = BLACK
do if x = left[p[x]]
then w ← right[p[x]]
if color[w] = RED
then color[w] ← BLACK ? Case 1
color[p[x]] ← RED ? Case 1
LEFT-ROTATE(T, p[x]) ? Case 1
w ← right[p[x]] ? Case 1
if color[left[w]] = BLACK and color[right[w]] = BLACK
then color[w] ← RED ? Case 2
x p[x] ? Case 2
else if color[right[w]] = BLACK
then color[left[w]] ← BLACK ? Case 3
color[w] ← RED ? Case 3
RIGHT-ROTATE(T, w) ? Case 3
w ← right[p[x]] ? Case 3
color[w] ← color[p[x]] ? Case 4
color[p[x]] ← BLACK ? Case 4
color[right[w]] ← BLACK ? Case 4
LEFT-ROTATE(T, p[x]) ? Case 4
x ← root[T] ? Case 4
else (same as then clause with "right" and "left" exchanged)
color[x] ← BLACK
“上面的修复情况看起来有些复杂，下面用一个分析技巧：从被删除结点后来顶替它的那个结点开始调整，并认为它有额外的一重黑色。这里额外的一重黑色是什么意思呢？我们不是把红黑树的结点加上除红色与黑色的另外一种颜色，这里只是一种假设，我们认为我们当前指向它，因此空有额外一种黑色，可以认为它的黑色是从它的父结点被删除后继承给它的，它现在可以容纳两种颜色，如果它原来是红色的，那么它现在是红+黑，如果原来是黑色，那么它现在的颜色是黑+黑。有了这额外的黑色，原红黑性质5就能保持不变。现在只要花时间恢复其他性质就可以了，做法还是尽量向根移动和穷举所有可能性。”——saturnman。
红黑树修复操作的几种情况。
注意：以下情况3、4、5、6，与上述算法导论的代码RB-DELETE-FIXUP(T,x)恢复与保持中case1、case2、case3、case4相对应。
情况1：当前结点是红+黑色
对策：直接把当前结点染成黑色，结束。
此时红黑树性质全部恢复。
情况2：当前结点是黑+黑，并且是根结点
对策：什么都不做，结束。
情况3：当前结点是黑+黑，并且兄弟结点是红色（此时父结点和兄弟结点的子结点都为黑）
对策：把父结点染成红色，把兄弟结点染成黑色，左旋之后重新进入算法（只讨论当前结点是其父结点的左孩子时的情况）。此变换后原红黑树性质5不变，而把问题转化为兄弟结点为黑色的情况（注意：变换前，原本就未违反性质5，只是为了把问题转化为兄弟结点为黑色的情况）。
变化前：
变化后：
情况４：当前结点是黑＋黑，并且兄弟结点是黑色，兄弟结点的两个孩子结点全为黑色
对策：把当前结点和兄弟结点中抽取一重黑色追加到父结点上，把父结点当前新的当前结点，重新进入算法（此变换后性质５不变）。
变换前：
变换后：
情况５：当前结点是黑＋黑，兄弟结点是黑色，兄弟结点的左孩子是红色，右孩子是黑色
对策：把兄弟结点染红，兄弟左孩子染黑色，之后再在兄弟结点为支点解右旋，之后重新进入算法。此时把当前的情况转化为情况６，而性质５得以保持。
变化前：
变化后：
情况６：当前结点是黑＋黑，兄弟结点是黑色，但兄弟结点的右孩子是红色，左孩子的颜色任意
对策：把兄弟结点染成当前结点父结点的颜色，把当前结点父结点染成黑色，兄弟结点的右孩子染成黑色，之后以当前结点的父结点为支点进行左旋，此时算法结束，红黑树所有性质调整正确。
变化前：
变化后：
补充两图
红黑树插入修复的３种情况：
红黑树删除修复的四种情况：
通过对这篇文章的阅读，对红黑树确实有了进一步的了解，但是，还是要再接再厉，感谢原作者。
参考：http://blog.csdn.net/v_JULY_v/article/details/6105630
作者：July、saturnman
梦醒潇湘love
2013-01-22 10:40