红黑树算法的层层剖析与逐步实现
本文主要参考：算法导论第二版
本文主要代码：参考算法导论。
本文图片来源：个人手工画成、算法导论原书。
推荐阅读：Leo J. Guibas 和 Robert Sedgewick 于1978年写的关于红黑树的一篇论文。
引言：
昨天下午画红黑树画了好几个钟头，总共10页纸。
特此，再深入剖析红黑树的算法实现，教你如何彻底实现红黑树算法。
经过我上一篇博文，“教你透彻了解红黑树”后，相信大家对红黑树已经有了一定的了解。
个人觉得，这个红黑树，还是比较容易懂的。
不论是插入、还是删除，不论是左旋还是右旋，最终的目的只有一个：
即保持红黑树的5个性质，不得违背。
再次，重述下红黑树的五个性质：
一般的，红黑树，满足一下性质，即只有满足一下性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
抓住了红黑树的那5个性质，事情就好办多了。
如，
1.红黑红黑，要么是红，要么是黑；
2.根结点是黑；
3.每个叶结点是黑；
4.一个红结点，它的俩个儿子必然都是黑的；
5.每一条路径上，黑结点的数目等同。
五条性质，合起来，来句顺口溜就是：（1）红黑 （2）黑 （3）黑 （4&5）红->黑 黑。
本文所有的文字，都是参照我昨下午画的十张纸（即我拍的照片）与算法导论来写的。
希望，你依照此文一点一点的往下看，看懂此文后，你对红黑树的算法了解程度，一定大增不少。
ok，现在咱们来具体深入剖析红黑树的算法，并教你逐步实现此算法。
此教程分为10个部分，每一个部分作为一个小节。且各小节与我给的十张照片一一对应。
一、左旋与右旋
先明确一点：为什么要左旋?
因为红黑树插入或删除结点后，树的结构发生了变化，从而可能会破坏红黑树的性质。
为了维持插入、或删除结点后的树，仍然是一颗红黑树，所以有必要对树的结构做部分调整，从而恢复红黑树的原本性质。
而为了恢复红黑性质而作的动作包括：
结点颜色的改变(重新着色)，和结点的调整。
这部分结点调整工作，改变指针结构，即是通过左旋或右旋而达到目的。
从而使插入、或删除结点的树重新成为一颗新的红黑树。
ok，请看下图：
如上图所示，‘找茬’
如果你看懂了上述俩幅图有什么区别时，你就知道什么是“左旋”，“右旋”。
在此，着重分析左旋算法：
左旋，如图所示（左->右），以x->y之间的链为“支轴”进行，
使y成为该新子树的根，x成为y的左孩子，而y的左孩子则成为x的右孩子。
算法很简单，还有注意一点，各个结点从左往右，不论是左旋前还是左旋后，结点大小都是从小到大。
左旋代码实现，分三步（注意我给的注释）：
The pseudocode for LEFT-ROTATE assumes that right[x] ≠ nil[T] and that the roots parent is nil[T].
LEFT-ROTATE(T, x)
1 y ← right[x] ▹ Set y.
2 right[x] ← left[y] //开始变化，y的左孩子成为x的右孩子
3 if left[y] ！=nil[T]
4 then p[left[y]] <- x
5 p[y] <- p[x] //y成为x的父母
6 if p[x] = nil[T]
7 then root[T] <- y
8 else if x = left[p[x]]
9 then left[p[x]] ← y
10 else right[p[x]] ← y
11 left[y] ← x //x成为y的左孩子（一月三日修正）
12 p[x] ← y
//注，此段左旋代码，原书第一版英文版与第二版中文版，有所出入。
//个人觉得，第二版更精准。所以，此段代码以第二版中文版为准。
左旋、右旋都是对称的，且都是在O（1）时间内完成。因为旋转时只有指针被改变，而结点中的所有域都保持不变。
最后，贴出昨下午关于此右旋算法所画的图：
左旋（第2张图）：
//此图有点bug。第4行的注释移到第11行。如上述代码所示。（一月三日修正）
二、左旋的一个实例
不做过多介绍，看下副图，一目了然。
LEFT-ROTATE(T, x)的操作过程（第3张图）：
---------------------
提醒，看下文之前，请首先务必明确，区别以下俩种操作：
1.红黑树插入、删除结点的操作
//如插入中，红黑树插入结点操作：RB-INSERT(T, z)。
2.红黑树已经插入、删除结点之后，
为了保持红黑树原有的红黑性质而做的恢复与保持红黑性质的操作。
//如插入中，为了恢复和保持原有红黑性质，所做的工作：RB-INSERT-FIXUP(T, z)。
ok，请继续。
三、红黑树的插入算法实现
RB-INSERT(T, z) //注意我给的注释...
1 y ← nil[T] // y 始终指向 x 的父结点。
2 x ← root[T] // x 指向当前树的根结点，
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x] //向左，向右..
6 then x ← left[x]
7 else x ← right[x] // 为了找到合适的插入点，x 探路跟踪路径，直到x成为NIL 为止。
8 p[z] ← y // y置为 插入结点z 的父结点。
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z //此 8-13行，置z 相关的指针。
14 left[z] ← nil[T]
15 right[z] ← nil[T] //设为空，
16 color[z] ← RED //将新插入的结点z作为红色
17 RB-INSERT-FIXUP(T, z) //因为将z着为红色，可能会违反某一红黑性质，
//所以需要调用RB-INSERT-FIXUP(T, z)来保持红黑性质。
17 行的RB-INSERT-FIXUP(T, z) ，在下文会得到着重而具体的分析。
还记得，我开头说的那句话么，
是的，时刻
补充：软件开发 , C语言 ,
