灵魂守卫

二叉树的深度优先遍历就是二叉树地前序遍历．二叉树的广度遍历就是层序遍历.（最后面有完整的代码）．
一．深度优先遍历(DFS)

深度优先遍历与前序遍历的结果是一样的．那么递归实现应该是

与之对应的非递归算法是，使用栈的先进后出的特性．

二.广度优先遍历(BFS)

二叉树的广度优先遍历其实很简单，大概的思路是访问一个结点时，将它的子结点放入队列后面，当本层访问结束后，队列中就剩下下一层的所有结点，直到队列中没有结点为止．
可以看到队列的前部是当前层剩下的结点，队列的后部是当前层已经访问过的结点的子结点．

完整代码 阅读全文…

在本文，我将比较透彻地讲解红黑树。本文适合那些有对二叉树有一定的基础，并且熟悉C语言的读者。本文最主要的参考资料是《Introduction to Algorithms 3rd Edition》。

1.1 二叉查找树

1.1.1 基本概念

二叉查找树是在数据结构中比较重要的数据结构之一，从外部看它满足集合性质，具有查找，插入和删除的基本功能，同时还可以求最大值和最小值。由于二叉查找树独特的性质，它特别适合用来存储动态集合。
定义：对于二叉树上的所有结点x，如果y是x的左子树，那么y.key ≤ x.key。如果y是x的右子树，那么y.key ≥ x.key，这样的二叉树就称为二叉查找树(Binary Search Tree)。
我们关心的二叉查找树的逻辑结构，下面的两棵二叉树：

图1 二叉查找树。(a)这一棵高度为3的二叉树，因为10比15小，所以10在15的左子树上；同理在以10为根的左子树里，7比10小所以7在左子树上，12在10为根的子树的右子树上；20在以15为根的右子树上。(b)这是一棵高度是4的二叉查找树，它的所有key与图(a)是一样的。在图(a)中，查找最坏的情况是7和12，它们需要经过3次比较才能找到，而图(b)最坏情况是20，需要经过4次比较才能找到。
要想二叉树的查找的花费时间小，我们尽可能让二叉树不出现类以于单链形态的二叉树，让树的高度尽量的低。对于高度为h的二叉查找树，从树根对叶子最坏的情况是比较h次。也就是说，对于高度为h的二叉查找树的最坏查找情况的运行时间是O(h)。二叉树的查找效率取决于树的高度。

1.1.2 操作

二叉树做为动态集，它有查找、插入、删除、最大值、最小值、前驱和后继这些基本操作。为了后序的方便，我们定义了结点和树，另外我们还用NIL表示空子树。

查找
在二叉查找树中根据给定的key找到该结点。由于二叉树的性质，我们就知道，如果目标key比当前结点的key要小，那么目标结点必定在当前结点的左子树上。

最小值与最大值
我们来分析一下最小值的位置。我们认为最小值的位置是从根出发一直沿结点的左子树直到某个结点x的左子树为空，那么这个结点x就是整个二叉树中key最小的结点。注意，我们并没有做任何key的比较。
证明：假设这个结点x不是最小值，另外有最小值结点y，那么y.k > x.k。如果y是x的祖先，因为x位于y的左子树上，那么x肯于定比y要小，所以y不是x的祖先。如果y不是x的祖先，假设y与x的最小的共同祖先的z，又因为y不是x的祖先，所以y在z的右子树上，所以z.k < y.k，并且有z.k > x.k，与假设的y.k > x.k矛盾，所以假设不成立，x是二叉查找树中key最小结点。最大值的分析方法也是一样的。

前驱和后继
前驱与后继定义来源于二叉树中序遍历的key序列。我们知道二叉的中序遍历的key序列是一个升序序列。在二叉查找树中，对于结点x，如果有结点y，满足y.key>x.key并且y是这些结点中key最小的，那么y就称之为x的后继。同理，在二叉查找树中，对于结点x，如果有结点y，满足y.key

图2结点的后继和前驱。(a)y是x的后继，因为y没有左子树，所以y是x右子树上key最小的结点。(b)y是x的后继，因为x的左子不为空，所以y是x左子树中最左那个小那个，所以y是x的后继。(c)x是y的前驱，因为y没有左子树，所以y是x左子树上key最大的那个结点。(d)y是x的前驱，因为x有左子树，所以x左子树上key最大的在x左子树上最右的那个结点。也有可能是z右孩子的最左的那个子孙结点(图b所示)。如果y是的后继，那么y就是x的前驱。
对于某个结点y它的后继的位置是：如果y的右子树存在，那么后继是y的右子树中的key最小的结点；如果y的右子树不存在，那么我们只要找到哪个结点的前驱是y，那么那个结点就是y的后继(图2中的d)。

根据前驱和后继的定义，我们知道通过对树中最小值一直沿着后继直到结束，这样的序列就是中序遍历的序列。下面给出中序遍历的代码：

插入
对二叉查找树的插入，不能破坏二叉查找树的性质，那么我们要结点插入到什么地方呢？答案是叶子，新插入的结点，都是将成为某个叶子结点的左孩子或者右孩子。

图3 二叉查找树的插入。图中key为11的结点插入到树中，其中浅色结点表示插入时候比较的路径。虚线表示插入的位置。

我们发现insert与search方法是一样的，只不过search是查找特定的key，而insert是查找合适的叶子结点的位置，它的运行时间为O(n)。

删除
在介绍删除二叉查找算法之前，我们先来介绍一个辅助函数transplant，这个函数有3个参数，在树T中，将v替换u的位置，即u的双亲变成v的双亲，v替换u成为u双亲的孩子。另外一个辅助函数replace，这个函数有3个参数，在树T中，将v完全代替u，即u的双亲变成v的双亲，v替换u成为u双亲的孩子，另外左右孩子均为u的孩子。

图4演示了transplant中v在树中替换u的过程。如果u是根，即v.p==0时，T的树根就改变了。

我们来考查一下待删除的结点是z。那么z可能有几种情况：

• z没有右孩子；
• z有右孩子：z的右孩子有左孩子，z的右孩子没有左孩子。

图5 二叉树删除的三种情形。图中z（浅色的）为待删除的结点。(a)没有右孩子的删除，将z的左孩子替换z即可，z的左孩子有可能是NIL指针。(b)z的右孩子不为空,y是z的后继，但右孩子的左孩子为空，我们知道z的右孩子就是z的继，所以用z的右孩子替换z即可。(c)z的后继y不是z的右孩子，y的右孩子替换y，从树中移出y，将y作为z右孩子的双亲连接上，此时情形成了情形b了。
下面我具体针对这3种情形进行分解。情形1，z没有右孩子，我们只要将左孩子替换z在树中位置就能完成删除操作，其实我们拿z的前驱替换也是可以的；情形2，z有右孩子，所以我们找到z的后继替换z。因为z的key小于右子树所有的key（假设没有重复的key），那么z的后继就是右子树上的最小key。如图5的中b和c，z的后继可能是z的右孩子（当右孩子没有左孩子就会出现该情况），那么调用transplant(T,z,y)。另外，要连接上原来z的左子树；z的后继也有可能不是z的右孩子（图c所示的情况），首先我们调用transplant(T,y,y->r)，这时候y已经从树中脱离了，然后我们将y嫁接到z的右孩子的双亲上，这样y就成了z右孩子的双亲了，这和情形b是同一种情况了。下面是删除的代码：

1.1.3 实现

参考附件：bstree.c。

1.1.4 思考题

1.Bunyan教授认为他发现了二叉查找树的一个重要的性质。假设在二叉查找树上查找key为k的结点,并且key为k的结点是一个叶子结点。那么有三个集合：A，搜索路径的左边结点的集合；B，搜索路径上的结点的集合；C是搜索路径右边的结点集合。Buyan教授认为对于三个集合的任意值a∈A，b∈B，c∈C一定满足a≤b≤c。对于上面的观点，请给出最小可能一个的反例。
2.证明：在高度为h的二叉查找树上，我们实现的动态集基本操作:min，max，successor，predecessor，search，insert和remove的运行时间都是O(h)。
3.在二叉查找树的删除操作中，假设我们不取z的后继而取z的前驱替换z，请相应对称的代码。

1.2 红黑树

在上节的思考题中，我们证明了在高度为h的二叉查找树上，我们实现的动态集基本操作运行时间都是O(h)。总而言之，树度h决定查找效率。如果我们通过某种方法能够将二叉树尽可能的低，那么二叉树的查找效率将会大大地提高。
对于一个含有n结点的最坏的情况是这n个结点形成一条单链，那么二叉查找树的树高为n，运行时间为O(n)；那么最好情况是n个结点形了一棵完全二叉树。所谓完全二叉树是指对于一棵高度为h的二叉树，除第h层外，其它各层的结点数都达到最大个数，并且第h层所有的结点都连续集中在最左边，这样的二叉树称为完全二叉树。那么h介于lg n与lg n+1之间，也就是说运行时间为O(lg n)。可以说它的效率是极高的。

1.2.1 基本概念

如果我把二叉查找树的每个结点都涂上红色或者黑色。如果它满足下面的5个性质，那么我们就称它为红黑树（Red Black Tree）：

• 每个结点不是红色就是黑色。
• 根结点是黑色的。
• 每个叶子结点（NIL）都是黑色的。
• 如果一个结点是红色的，那么它所有的孩子都是黑色的。
• 对于每一个结点，从当前结点到后代的叶子的路径上包含黑色结点的数量是相同的。

根据红黑树的性质，我们可得出下面的结论：具有n内部结点的红黑树的高度最高为2lg(n+1)。
在证明这个结论之前，我们来看看红黑树的表示。每个结点到叶子结点（NIL）经过的黑色结点的个数（包括自已）称之为黑高度(black-height)。我们把NIL称之为外部结点，那些带有key的“合法”的结点称之为内部结点。

图6 红黑树的表示。key为64的结点的黑高度为3，key为26，81，14，44的结点黑高度为2，key为5，19，30，76，92的结点黑高度为1。
证明：我们将红色结点吸附到黑色的双亲结点上，那么一个黑色结点最多可以吸附2个结点，并且可以有4个孩子，那么就形成了一个大结点，如图7所示。这样树我称之为234树。红黑树的数学本质就是234树，并且所有的“叶子”结点的高度都是相等的。不难看出，黑高度就是这棵234树的高度。

图7 将图6中的红色结点吸附到双亲结点上，这样对应数学结构为234树。
对于高度为h并且所有的“叶子”结点的高度都是相等的234树最少有多少个结点呢？要想结点最少，那么它就退化出了满二叉树了。所以，树的结点个数n满足：
（公式1）
由公式1得出：两边取对数即。这里的h是234树的高度，由前面所述，红黑数的黑高度就是对应234树的高度。对于黑高度了h，由性质2、3、4得出红色结点不可能多于黑色结点。所以结点个数不大于黑高度的2倍。所以具有n内部结点的红黑树的高度最高为2lg(n+1)，证毕。
我们证明的结论说明红黑树的搜索运行时间为O(2lg(n+1))也就是O(lg n)。
为了方便操作，我们引入一个NIL结点，这个NIL结点是跟普通的结点一样，不过我们只使用color这个域，因为NIL结点是黑色的。

我们定义了结点的颜色，同时每个结点都增加了一个c域来表示结点的颜色。除此之外我们还为树定义了一个nil结点，之前实现的二叉查找树中指向NIL都改为指向T->nil。

1.2.2 查找

因为红黑树本身就是一棵二叉查找树，所以对红黑树的查找操作跟普通的二叉查找树的操作没有什么不一样，但注意的时，在这里我们已经用T.nil取代了0。下面仅仅给出查找操作的代码，读者可以比较一下与普通的二叉查找树有什么不一样的地方。

有两处不一样，第一处是x!=0替换成了x!=&T->nil，另外一处是在结尾出增加了对x是否是nil的判断，操作上的代码没有二致。对于前驱和后继，我就不举例了，有兴趣的读者可以自行思考或者参考一下附件的实现。

1.2.3 旋转

在介绍红黑色的插入与删除前，我们介绍一下二叉树的旋转操作：旋转分为左旋(Left-Rotate)和右旋(Right-Rotate)。
左旋

图8 树的左旋和右旋。(a)将x结点右孩子y替换x成树中的位置，同时x成为y的左孩子，y原来的左孩子成为x的右孩子。观察在调整前α　　下面是左旋代码，先用y替换x的位置，再将y的原左子树变成x的右子树，x成y的左子树。

右旋
下面给出右旋的代码，先用y替换x的位置，再将y的原右子树变成x的左子树，x成y的右子树。

小技巧：区分左旋还是右旋，我们只要看x最终是y的左孩子还是右孩子，如果左孩子那就是左旋，如果右孩子那就是右旋。
综述，二叉查找树的左旋和右旋并不会破坏其二叉查找树的数学性质。

1.2.4 插入

红黑树的插入前半部分与普通的二叉查找树的插入大致相同的，我们来看一下插入的代码。

从代码中可以看出，它与我们前面的二叉查找树的插入操作有两个地方不同，首先是用T.nil取代了0，其次是在代码的结尾，多出了两行，一行是z->c=RBT_RED,另一行是调用了_rbt_insert_fixup函数。
我们知道，将结点插入到红色黑树的叶子结点上，可能会导致这棵树不再满足红黑树的性质。我们将新插入的结点着成红色，插入到红黑中，然后通过_rbt_insert_fixup修正红黑树的性质。
当插入结点z时，我如果把z着成红色，看看我们会破坏原有的那些性质呢？
我们已经将z着成红色了，所以性质1不会被破坏。当往空的红黑树插入结点的时候，这个性质2会被破坏。每个叶子结点（NIL）都是黑色的，所以性质3不会被破坏。因为我们插入的结点是红色的，所以性质4可能被破坏，同样是因为我们插入的是红色结点，所以性质5不会被破坏。综述，我们往将z着成红色插入到红黑树的时候，可能会破坏性质2和性质4，其它性质不会被破坏。

图9 红黑树的插入情形。(a)z的叔叔是红色的，z是左孩子;(b)z的叔叔是红色的，z是右孩子;(c)z的叔叔是黑色的，z是左孩子;(d)z的叔叔是黑色的，z是右孩子。这里我们略了z的叔叔是左孩子的情况，因为它们是对称的。
当结点z插入时，如果z的双亲结点不是红色的，那么它不会破坏红黑树的性质。所以只有z的双亲是红色的时候，z和z的双亲都是红色会破坏红黑树的性质4，所以我们目的是在不破坏现有的性质1,3,5来恢复性质2和4。
我们考查z和z的叔叔，当z的双亲是左孩子，性质4被破坏的情况只有图9所示的4种情况；当z的双亲是右孩子的时候，跟这个是对称的。我们知道，是因为性质4被破坏了，所以z和z的双亲都红色的，所以z双亲肯定不是根结点，因为根结点是黑色的。下面针对这四种情况进行恢复红黑色树的性质。
情形1：z的叔叔是红色的。
这种情况，不管z是右孩子还是左孩子，我们将z的双亲的双亲上的黑色的分别涂给z的双亲和z的叔叔，这样不会可能破坏性质2或者性质4，其它性质依然保持，因为z的双亲是红色且z的叔叔也是红色的(假设的条件)。我们不知道z的祖亲的双亲颜色，所以我把z的祖亲当作新的结点z，继续调整。

图10 我们将z.p和叔叔都着成黑色，z.p.p当作新的z继续修复。直到z.p的颜色是黑色的，那么z.p.p是根时，由于z.p是T.nil，它也是黑色的，也会退出循环，不会将叶子着成红色的。我们在最后恢复性质2，暂且不考虑性质2被破坏。
情形2：z的叔叔是黑色的，z是双亲的左孩子。

图11 情形2。我们发现可以将B右旋到右子树，通过一次右旋和着色就可以恢复红黑树的性质4了，因为没有哪个红结点是红色的孩子双亲。
进入每一个情形都是因为z和z.p都红色的，由于插入之前是合法的红黑树，所以z.p的另一个孩子是黑的，z.p.p也黑色的，图示的y是是z.p.p，所以y是黑色的。对y进行右旋，我们发现通过z的路径少了一个黑色，如图示交换一下颜色就恢复了红黑树的性质4了。
情形3：z的叔叔是黑色的，z是双亲的右孩子。

图12 情形3。z的叔叔是黑色的，并且z是右孩子。
我们发现对z的双亲y进行左旋，因为只有z和z的双亲不满足红色树的性质4，所以z的左右孩子都是黑色的，这样旋转并不会破坏z的孩子和z兄弟的黑高度的。然后把z指向z的左孩子，这时候就将情形3转换到了情形2了。
下面是修复红黑树四种情形的代码。最后，我们修复了根是黑色的性质2。

从上面的修复性质4的可以看，只有情形一在不做旋转的情况下，z的指针向上在树中移动两层。情形2经过一次旋转就可以恢复，情形3要先通过旋转变成情形2。所以我们得出结论，向红黑树中新插入一个结点着成红色，我们可以通过不超过两次的旋转就可以恢复红黑树的性质。

1.2.5 删除

红黑树的删除，其实也是先进行二叉查找树的删除，再调整颜色。
二叉树删除的三种情况中，对比观察图13，情况c中，使用y替换了z,只要我们将y着成z的颜色，那么我们很容易发现一个共同之处，那就是如果我们将虚线圈起来当成一个特殊的结点，那么所有从根结点出发经过双亲结点到达NIL树叶结点的路径肯定也经过孩子结点。那么二叉树删除的结果就是，圈中少了一个结点，如果我们将结点删除，但颜色保留，将刚移走的结点的颜色“塞”给x，也就是圈中的剩下的结点x,加上自身的颜色，此时x可能是“黑黑”也有可能是“红黑”。那么我们发现剩下的部分，除了性质1外，其它性质都没有变化。

图13 红黑树结点删除的初始情形。内圏的颜色是表示孩子的颜色，圈外表示双亲的颜色。x表示原删除或移走后剩下的结点的位置。(a)x的位置是z的左孩子，留下了z的颜色；(b)x的位置是z的右孩子，z的右孩子替换了z，留下了z右孩子的颜色；(c)x的位置是z后继的位置，z的后继已经替换了z，留下了原z后继的颜色。
我们发现一个规律，如果圈内有一红一黑，那么我们并不需要调整红黑树，直接将x着成黑色就行了。所以我们删除代码比之前普通二叉查找树的删除多了一些记录位置的代码 。还有一个值得注意的地方就是如果圈中的孩子是叶子结点，那么通过叶子结点是无法找到双亲的，所以我们不管是不是叶子结点都将p指向圈中双亲的双亲。

好了，现在我们可以开始调整“塞”给x上的黑色了，根据判断条件，只要x和y有一个是红色，均不用调整，而且调整前是合法的红黑树，x和y不可能同为红色，所以唯一的情况是x是黑色，被移走结点留下的也是黑色。下图所示的x的兄弟w都是右子树的例子，同样如果w是左子树是对称的。

图14 上面是分别是调整颜色是遇到的所有情况。(a)情形1，w颜色为黑色的，并且w的右孩子为红色，这时候，我们对x的双亲左旋转将x的新双亲和新叔叔都着成黑色，x的祖亲着成原x的双亲的颜色。(b)情形2,w颜色是黑色的，并且w的左孩子是红色的w的右孩子是黑色的，将w进行一次右转，重新着色，我们发现这个状态正好是情形1。(c)情形3,w的是黑色的并且左右孩子都是黑色的，我们将x和w都提取一个黑色给x的双亲，这时候我们把双亲看成新的x，继续调整。(d)情形4，w颜色是红色的，由于w是颜色是红色的，所以w的左右孩子都是黑色的。我们对x的双亲做一次左旋，重新着色，我们发现状态转换到了(a)(b)(c)中的任意一种了。
假设有函数C(m)表示如果m结点是黑色的，C(m) = 1；如果m结点是红色的C(m) = 0。并且我们知道x是双黑的，所以w不可能是nil结点，所以w是有左右孩子的。
情形1:x的兄弟w是黑色的，并且w的右孩子是红色的。
我们假设C(x.p)=p，C(x.r)=q。在调整前：
α子树的根到图示的根黑结点个数是2+p；
β、γ子树的根到图示的根黑结点的个数是2+p+q；
δ、ε、ζ子树的根到图示的根黑结点的个数是1+q’’。
我们交换w和x双亲的颜色，并将w的右孩子着成黑色，再对x.p执行一次左旋。我们发现在调整后：
α子树的根到图示的根黑结点个数是3+p；
β、γ子树的根到图示的根黑结点的个数是3+p+q；
δ、ε、ζ子树的根到图示的根黑结点的个数是1+q’’。
α、β和γ均比之前多了一个黑色，如果我们将x身上的额外的黑色去掉，那么α、β和γ到图示的黑结点个数与调整之前一样，分别是2+p和2+p+q，调整结束。

情形2:x的兄弟w是黑色的，并且w的左孩子是红色的。右孩子是黑色的。
这个情形比较简单，我们交换一下w和右孩子的颜色执行一次右旋，α、β、γ、δ、ε和ζ到图示的根的黑结点个数仍然不变，观察这个情形就转化了情形1了。

情形3:x的兄弟w是黑色的，并且w的左孩子是黑色的，右孩子也是黑色的。
因为w和左右孩子都是黑色的，并且x是“双黑的”，将w和x的黑色都向上提，这时候将w着成红色。x的双亲成了新的x了，继续向上调整。

情形4:x的兄弟w是红色的。
因为x是红色的，所以x的孩子和x的双亲都是黑色的，调换w的双亲与w的颜色进行一次左旋。我们发现x的新兄弟成了黑色，那么这就成情形1、2和3中的任意一种来调整了。
下面是fixup代码：

1.2.6 实现

参考附件：rbtree.c。

1.2.7 思考题

1. 先依次画出从初始空树中成功插入key为41，38，31，12，19，8的结点的红黑树。再画出依次删除8，12，19，31，38，41之成功后红黑树。

附件

bstree.c : 二叉查找树实现代码
rbtree.h : 红黑树的接口
rbtree.c : 红黑树的实现
如果你是windows用户
main.c :红黑树的操作实例
rbtree.exe：一个红黑树的操作实例编译方法: gcc -o rbree.exe rbtree.c main.c -mwindows
本文的其它参考文档：
第12章 二叉查找树
第13章 红黑树
全文下载：红黑树详解

13.4 删除

跟其它n结点红黑色树的基本操作一样，删除一个结点的运行时间是O(lg n)。从红黑树中删除一个结点比插入一个结点要复杂一点。
从红黑树中删除一个结点的方法在基于TREE-DELETE方法的（第12.3节）。首先我们需要定制一下TRANSPLANT子方法，这样TREE-DELETE可以将它运用在红黑树上。

RB-TRANSPLANT与TRANSPANT有两个地方不一样。首先，第1行用T.nil代替了NIL。其次，在第6行的v.p赋值是无条件的：即使v指向哨兵结点，我们可以将v.p赋值。事实上，当v=T.nil，我们将能够利用v.p来赋值。
RB-DELETE方法有点像TREE-DELETE方法，但是增加了数行伪代码。一些增加的代码是为了跟踪y，它有可能导致破坏红黑的性质。当我们要删除结点z并且z有小于两个孩子，那么z将从树中删除，我们将y当作z。当z有两个孩子，y将是z的后继，y将会移动到z在树中的位置。当它从树中删除或者移动，我们将记下y的颜色，我们跟踪了结点x，将x移动到y在树中原来的位置，因为x可能会破坏红黑树的性质。删除结点z后，RB-DELETE将调用辅助方法RB-DELETE-FIXUP，这个方法会修改颜色和做一些旋转来恢复红黑树性质。

尽管RB-DELETE包含的伪代码是TREE-DELETE的两倍那么多，但是这两个方法有着相同的基本结构。你可以在RB-DELETE找到TREE-DELETE的每一行（有一点点变化，用T.nil替换了NIL，调用TRANSPLANT替换成了调用RB-TRANSLPLANT），在相同的条件下执行。
下面是这两个方法的其它的不同之处：

• 我们维护了结点y，y做为从树中删除的结点或才在树中移动的结点。第1行设置了y指向z，当z有少于两个孩子时直接删除了。当z有两个孩子，第9行设置y指向z的后继，如同TREE-DELETE一样，并且y将会移动到z在树中的位置。
• 因为y的颜色可能会改变，变量y-original-color存储了y在改变之前的颜色。第2和10行在对y进行了赋值后立即设置了这个变量。当z有两个孩子的时候，那么y≠z，并且结点y将移动到结点z在红黑树中的原始位置；第20行让y着成z相同的颜色。我们需要保存y的原始颜色在RB-DELETE的结尾测试它；如果它是黑色的，那么移除或者移动的y可能会破坏红黑树的性质。
• 正如我们刚才讨论过的，我们记录y的原始位置的结点x。第4，7，11设置x指向y唯一的孩子或者，如果y没有孩子，指向哨兵T.nil。（回顾12.3节y没有左孩子。）
• 因为结点x移动到了y的原始位置，x.p一直指向y的双亲结点在树中原始位置，甚至是,事实上也有可能是哨兵T.nil。就算z是y的原始双亲（如果z有两个孩子并且它的后继就是z的右孩子），x.p在RB-TRANSPLANT的也在第6行进行了赋值。（观察第5，8或者14的RB-TRANSPLANT的调用，传递的第二参数跟x是一样的。）
  当y的原始双亲是z的时候，然而，我们不希望让x.p指向y的原始双亲，因为我们将会删除这个结点。（译者注：z结点将用从树中删除，x.p指向这个结点就没有意义了）由于结点y将会提升取代z的位置，在第13行设置了x.p指向y，这会导致x.p指向y双亲的原始位置（译者注：原双亲的位置就是z在树中的位置），不管x=T.nil与否。
• 最后，如果y是黑色结点，我们可能破坏一个或更的红黑树性质，所以我们在第22行调用RB-DELETE-FIXUP去恢复红黑树的性质。如果y是红色的，当y删除或者移动的时候，红黑树的性质没有被破坏，理由如下：
  1. 树中没有结点的black-height被改变。
  2. 没有红结点是相邻的。因为y取代了z在树中的位置，跟z的颜色是一致的，我们不可能在y的新位置找到两个相邻的红色结点。更进一步，如果y不是z的右孩子，那么y的原始右孩子x替换了y在树中的位置。如果y是红色的，那么x一定是黑色的，所以用x替换y不会导致两个红色结点变成相邻的。
  3. 因为如果y是红色的，它就不可能是根，根继续是黑色的。

如果结点y是黑色的，可能会出现三个问题，可以调用RB-DELETE-FIXUP将会修正它们。首先，如果y一开始是根并且y的一个红色的孩子变成了新的根，这样我们破坏了性质2。第二，如是x和x.p都是红色的，那么我们破坏了性质4。第三，在树内移动y将会导致任意一条之前包含y的简单路径少一个黑色结点。因此在树中任何以y为祖先的结点不都满足性质5。我们说之前的y的位置上的结点x有一个“额外”的黑色结点，这样就修正了性质5。换句话说，我们在任意包含x的简单路径上增加一个黑色结点，这样情形下，性质5就保持了。当我们移除或者移动黑色结点y，我们将y的黑属性“推”给结点x。问题就是现在结点x既不是红色也不是黑色，性质1将不满足。（译者著：x本身是有颜色的，y的颜色色留在了原地也就是现在x位置，那么x结点就有两种颜色，一种是本身的颜色，一种是黑色）换句话说，结点x可能是“双黑”或者“红和黑”，在包含x的简单路径上，它贡献了2个或者1个黑结点数量。结点x的颜色属性现在仍然是红色（如果x是红和黑）或者黑色（如果x是双黑）。换句话说，在x指向的结点上有一个额外的额外的黑附加上这个结点上而不是在color属性上。（译者著：color属性不能表示该结点的颜色了）。
我们现在可以看看RB-DELETE-FIXUP并考察它是如何修复查找树上的红黑属性的。

方法RB-DELETE-FIXUP恢复了性质1，2和4。练习13.4-1和13.4-2让你去说明方法是如何恢复性质2和4的，所以本节的余下部分，我们专注于性质1。第1-22行的while循环的目的是在树中向上移动额外的黑，直到：

1. x指向了一个红和黑结点，这种情形我们在第23行将x的着成（单色）黑色。
2. x指向了根，这种情况我们简单的“移除”额外的黑；或者
3. 做一些适当的旋转和重新着色，然后我们退出循环。

在while循环里，x一直指向一个非根的双黑结点。我们在第2行里判断x是它双亲x.p的左孩子还是右孩子。（我们给出了x是左孩子情形的代码；x是右孩子的情况在第22行，这们是对称的）我们维护了指针w指向x的兄弟。因为结点x是双黑的，节点w肯定不是T.nil，否则从x.p到叶子w（单黑）（译者著：叶子是黑色的）的路径上的黑结点将会比x.p到x路径上的黑结点的数量要少。
代码中的这四种情形将会在表13.7中出现。在考查每一种情形前，让我们大致地看一下如何验证每一种情形的转换保持了性质5。关键思想在于每种情形的变化，所示的每一个树根（包括）到它的子树α，β，…… ζ都保持了黑结点的数量（包括x的额外的黑色）。因些如果变化之前满足性质5，那么之后它也满足。举个例子，如图13.7(a)，它描述了情形1，变化前和变化后从根到任意子树α，β的黑结点的数量都是3。（再次提醒，记住x结点添加了一个额外的黑色）相同地，在变换前后，从根到任意的子树γ，δ，ε的黑结点的数量是2。在图13.7(b)，图示的树根统计必须包含根根的颜色属性值c,它可能是红色或者黑色。如果我定义count(RED)=0和count(BLACK)=1，那么大变换前后，从根到α的黑结点的数量都是2+count(c)。这种情形下，通过变换后，新结点x的color属性c，但是这个结点的是红黑（当c=RED）或者双黑(当c=BLACK)。同样地，你还可以验证其它情形（参看练习13.4-5）。

情形1：x的兄弟w是红色的。

当结点x的兄弟w是红色的就是情形1（RB-DELETE-FIXUP的第5-8行和图13.7(a)）。由于w肯定有黑色的孩子，我们可以交换w和x.p的颜色，并在x.p上做一次右旋，这不会违反红黑树的性质。旋转前w的孩子是x的新兄弟，它现在颜色是黑色的，因些我们把情形1变成了情形2，3或者4。

情形2：x的兄弟x是黑色的，并且w的孩子都是黑色的。

在情形2中（RB-DELETE-FIXUP的第10到11行和图13.7(b)），w的孩子都是黑色的。因为w也是黑色的，我们可以将x和w的黑都关掉，让x只有一个黑和w变成红色。为了补偿从x和w中移除的黑色，我们添加一个额外的黑色到x.p上，x.p原始可能是红色或者黑色。观察如果是通过情形1进入情形2的，新结点x是红黑色的，由于原始的x.p是红色的，新的结点是红黑的。意味着，新结点x的color属性值是红色的，然后当我们测试循环条件的时，循环结束。然后我们在第23行将新结点x（单黑）着成黑色。

情形3：x的兄弟w是黑色的，w的左孩子是红色的，并且w的右孩子是黑色的。

当w是黑色的，它的左孩子是红色的并且它的右孩子是黑色的就是情形3（第13到16行和图13.7(c)）。我们可以先交换w和它左孩子的颜色并用w做一次右旋，这并不会破坏红黑树的属性。X的新兄弟w现在一棵带有红色右孩子的黑色的结点，这样我们就将情形3转换成了情形4了。

情形4：x的兄弟w是黑色的，并且w的右孩子是红色的。

当结点x的兄弟w是黑色的并且w的右孩子是红色的就是情形4(第17到21行和图13.7(d))。通过改变一些颜色和在x.p上的一次左旋，使它变成单黑，这样我们可以移除x上的额外的黑色并且不会破坏任何红黑树的性质。设置x成根将会在测试循环条件时使while循环终止。

分析

RB-DELETE的运行时间是多少呢？因为高度为n的红黑树是O(lg n)，除去调用RB-DELETE-FIXUP的时间方法总时间花费O(lg n)。在RB-DELETE-FIXUP里，情形1，3和4的每一个都会在常数次颜色修改和最多三次旋转结束循环。情形2是唯一一个重复while循环的，并且只是x指针在树中向上移动，并不会旋转。因些RB-DELETE-FIXUP会花费O(lg n)的时间和最多三次旋转，因此RB-DELETE的总时间也是O(lg n)。

图13.7 RB-DELETE-FIXUP的while循环里的情形。黑色结点的color属性为BLACK，深色的阴影结点color属性为RED，浅色阴影结点color属性用c和c’表示，它可能是红色或者黑色的。字母α,β,…,ζ代表任意子树。每一种情形通过改变颜色和/或做一次旋转从左边的状态变成右边的状态。任何x的指向的结点都有一个额外的黑，这个结点可能是双黑或者红黑。只情形2会重复循环。(a)通过交换B和D的颜色和做一次左旋，将情形1转换在2，3或者4。(b)情形2中，通过将D结点着成黑色并将x指向B结点，x指向的额外的黑在树中向上移动。如果我们是通过情形1进入情形1，while循环将会终止，因为新结点x是红黑的，因此它color属性值c是红色。(c)通过交换C结点和D结点的颜色和一次右旋将情形3转换成情形4。(d)情形4通过改变一些颜色和一次左旋(不会破坏红黑树的性质)移除额外的黑，然后循环终止。

练习

13.4-1 证明执行完RB-DELETE-FIXUP，树根一定黑色的。
13.4-2 证明如在RB-DELETE中x和x.p都是红色的，通过调用RB-DELETE-FIXUP性质4被恢复了。
13.4-3 在练习13.3-2中，你发现一查从初始空树通过成功插入key41，38，31，12，19，8的红黑树。现在画出依次删除8，12，19，31，38，41之成功后红黑树。
13.4-4 RB-DELETE-FIUXP的哪一行代码我们将检查了修改哨兵T.nil？
13.4-5 在图13.7的的各种情形中，给出从图示的根到各个子树α，β，…，ζ的黑结点个数，并验证每个个数与变化后的相同。当结点的color属性值是c或者c’,就使用表达式count(c)或者count(c’)表示在你的统计中。
13.4-6 Skelton和Baron教授认为在RB-DELETE-FIXUP情形1开始的时候，x.p结点可能是黑色的。如果这个教授的说法是正确的，那么第5-6行就是错了。证明x.p在情形1开始的时候一定是黑色的，教授们的担心是多余的。
13.4-7 假设结点x通过RB-INSERT插入到红黑树，然后通过RB-DELETE立即删除。结果的红黑树与初始的红黑树一亲吗？验证一下你的答案。
全文下载：第13章 红黑树

13.3 插入

我们可以在O(lg n)时间将一个结点插入到含有n结点的红黑树。为了插入结点，我们将TREE-INSERT方法（第12.3节）做稍稍的修改把树T当做普通的二叉查找树插入结点z，然后将z着成红色。（练习13.3-1让你解释一下为什么我们选择红色而不是黑色。）为了保持红黑树的性质，我们调用辅助方法RB-INSERT-FIXUP去着色和旋转。调用RB-INSERT(T,z)将结点z插入树T中，其中z结点已经包含填充了key。

TREE-INSERT和RB-INSERT方法有四个地方不一样。第一，所有TREE-INSERT使用NIL的地方都被替换成了T.nil。第二，在RB-INSERT的第14到15行，我们将z.left和z.right设置成了T.nil，是为了维护合适的树结构。第三，在第16行，我们将z着成红色。第四，由于将z着成红色将会导致红黑树的某个性质发生了违例，所有我们在第17行调用RB-INSERT-FIXUP(T,z)去恢复红黑树的性质。

为了理解RB-INSERT-FIXUP是如何工作的，我们将代码分成三个主要步骤去解释。首先，我们要判断在RB-INSERT中将z着成红色会出现哪些违反红黑树的性质的情况。其次，我们将考查第1到15行的while循环的目的。最后，我们将分析while循环体的的三种情况看它们是如何达到目的的。图13.4展示了RB-INSERT-FIXUP在红黑树上的执行过程的一个例子。
在调用RB-INSERT-FIXUP之前红黑树的哪些性质将不能保持？性质1将会继续保持，同理性质3，因为新插入的红色结点的两个孩子是T.nil。性质5，内容是从指定结点出发到叶子结点的每条简单路径上的黑色结点的数量是相同，这个性质也跟之前一样的，是因为结点z替换了（黑色）哨兵结点，并且z结点带有哨兵结点的红色结点。因此，只有性质2，要求根结点是黑色的，和性质4，红色结点不能有红色结点的孩子。这两个可能的不能保持的情况都是由z着成红色造成的。性质2是当z是根结点的时候不能保持，性质4是当z的双亲是红色的不能保持。图13.4(a)展示了z插入后违反性质4的一个例子。

图13.4 RB-INSERT-FIXUP操作。(a)插入后的结点z。因为z和它的双亲都是红色的，所以发一次性质4违例。因为z的叔叔是红色的，所以适应于情形1。我们重新将结点着色并且将指针z从树上向上提升，结果如(b)所示。跟上面的情形一样，z的它的双亲双都是红色的，但是z的叔叔是黑色的。因为z是z.p的右孩子，所以适用于情形2。我们做一次左旋，结果如图(c)所示。现在z是双亲的左孩子，那它适用于情形3。重新着色并右转直到成为图(d)中的树，它一棵合法的红黑树。
第1到15行的while循环在每次迭代的开始都维护了下面三个不变式：

1. 结点z是红色的
2. 如果z.p是根，那么z.p是黑色的。
3. 如果红黑树的性质招到破坏，那么最多只有一个性质被破坏，性质2或者性质4被破坏。如果是性质2，那是因为z是根并且是红色。如果性质4被破坏那是因为z和z.p都是红色的。

c部分，处理这些违反红黑树性质的部分，在RB-INSERT-FIXUP恢复红黑树性质上比(a),(b)部分更为重要，我们用它来了解程序代码中的情况。因为我们注意力聚集在z结点及它在树中的周围结点上，从(a)部分我们知道z是红色的。我们可以利用(b)部分知道z.p.p是存在的，我们在第2，3，7，8，13中引用到它。（译者注，因为b部分说根是黑色的，而且z.p也是红色的，所以z.p.p肯定存在。）
我们证明在第一次迭代时循环不变式是真的，每次迭代都维护这个不变式，在循环结束时，这个不变式将给我们提供一个很好性质。
我们从初始化和终止开始讨论。然后我们详细考查循环体是如何工作的，我们将讨论每次迭代的循环维护这个不变式。随后，我们将表明每次循环迭代后都有两种可能的结果：z指针向上移动或者做一些旋转后循环终止。
初始化：在第一次迭代前，我们用一棵合法的红黑树开始，然后我们插入了红色结点z。我们各种情况下调用RB-INSERT-FIXUP时不变式都是成立的：
当调用RB-INSERT-FIXUP时，z是被添加的红色结点。
如果z.p是根，那么z.p开始时就是黑色调用RB-INSERT-FIXUP不用修改。
当我们调用RB-INSERT-FIXUP时，我们已经看到性质1，3，5保持不变。
如果树的性质2不能保持，那么说明添加了红色的根结点z，z是树中的唯一一个内部结点。因为双亲和两个孩子都是哨兵结点，它们都是黑色的，树就不会违反性质4。因些违反性质2的情况，是整棵树中唯一一处破坏红黑树性质的地方。
如果树的性质4不能保持，由于结点z的孩子是黑色的哨兵并且在添加z前整个棵树没有其它的违反红黑性质的地方，那么这种违反一定是z和z.p都是红色的。而且，没有 对红黑树的其它性质的违反。
终止：当循环结束时，它是因为z.p是黑色才结束的。（如果z是根结点，那z.p是哨
兵T.nil,它也是黑色的）因此，在循环结束时，树不会违反性质4。通过循环不变式，仅仅只有性质2可能不满足。第16行也恢复了这个性质。所以在RB-INSERT-FIXUP结束时，所有的红黑树性质都满足了。
维护：在while循环里我们实际上需要考虑到6种情形，但有三种情形与另外三种情形是对称的，取决于第二行的z的双亲z.p是z的祖亲z.p.p的左孩子还是右孩子。我们仅仅给出了z.p是左孩子的解决方案的代码。结点z.p.p是存在的，是由于b部分的循环不等式，如是z.p是根，那么z.p是黑色的。因为我们仅当z.p是红色才会进入循环迭代，我们知道z.p肯定不是根。意味着z.p.p是存在的。
我们根据z双亲的兄弟或称作“叔叔”的颜色来区分情形1与情形3。第3行让y指向z的叔叔z.p.p.right，第4行测试y的颜色。如是y是红色的，我们执行情形1。否则，执行跳到情形2和情形3。所有的三种情况，z的祖亲是黑色的，是因为z.p是红色的，只有z和z.p是违反性质4。

情形1：z的叔叔是红色的

图13.5展示了情形1（第5到8行），z.p和y都是红色的时候属于这种情形。因为z.p.p和y是黑色的，我们将z.p和y都着成黑色，用来修复z和z.p都是红色的问题，并且我们z.p.p着成红色来保持性质5。我们把z.p.p当成新的结点z来重得while循环。在树上z指针向上移动了两层。
现在，我们证明情形1在下一次迭代前维护了循环不等式。我们用z来表示当前迭代中的结点z,那z’ = z.p.p来表示第1行下次迭代被为结点z的结点。

1. 因为本次迭代将z.p.p着成了红色，结点z’在下一次迭代开始时是红色的。
2. 结点z’.p是本次迭代的z.p.p.p，它的颜色没有改变。如是这个结点是根，它在本次迭代前是黑色的，并且在下次迭代开始是也保持黑色。
3. 我们已经讨论了情形1维护了性质5，它不会破坏性质1或者3。

图13.5 RB-INSERT-FIXUP情形1的处理过程。性质4被破坏了，由于z和它的双亲z.p都是红色的。不管z是右孩子还是左孩子，我们操作方法都是一样的。每一个子树α，β，γ，δ和ε都有一个黑色的根，并且它们有相同的black-height。情形1改变了一些结点的颜色，为了保持性质5：从一结点向下到叶子结点都有相同数量的黑结点。while循环所z.p.p当成新的z继续下去。所以违反性质4都只可能发现在新红色z和它的双亲之间，如它的双亲是红色的，处理方法跟上面的一样。

情形2：z的叔叔是黑色的并且z是右孩子
情形3：z的叔叔是黑色的并且z是左孩子

在情形2和情形3中，z的叔叔的颜色是黑色的。我们通过z是z.p的左孩子还是右孩子来区分这两种情形。第10到11行形成了情形2，在图13.6中与情形上放在一起。在情形2中，结点z是双亲的右孩子。我们立即使用一次左旋变成了情形3（第12到14行），这种情形z变成了左孩子。因为z和z.p都是红色的，旋转影响了结点的black-height和性质5。不管直接的情形3还是通过情形2转化而来的，z的叔叔都是黑色的，否则的话将会执行情形1了。另外，z.p.p是存在的，在执行第2和3行时，我们已经讨论了这个结点是存在的，并且在第10行将z向上提升了一层然后在第11行向下降了一层，z.p.p仍然没有变化。在情形3中，我们将一些结点的颜色改变了并且做了一次右旋，这些是为了保持性质5，然后在一条线上就不存在两个红色的结点，就这样完成了。因为现在z.p是黑色的了，while循环不再进行下一次的迭代了。

图13.6 RB-INSERT-FIXUP情形2和3的处理过程。跟情形1一样，不管是情形2还是情形3由于z和z的双亲都是红色的而破坏了性质4。它的任意一棵子树α，β，γ，δ都有一个黑色的根（α，β，γ是根据性质4，δ如果不是黑色将执行情形1），并且它有相同的black-height。我们通过一次左旋将情形2转化成情形3，保持了性质5：从一结点向下到叶子结点都有相同数量的黑结点。情形3一些点颜色被改变了并且做了一次右转，也是为了保持性质5。然后while循环结束了，因为性质4满足了：在一条线上不再有两个红色结点。
现在我们来证明情形2与情形3保持了循环不等式。（正如我们讨论过的，z.p将会在第1的下次测试z.p将会是黑色，并且循环体将不再执行。）

1. 情形2使z指向z.p，z.p是红色的。z和它的颜色在情形2和3中不再变化。
2. 情形3使z.p着成黑色，所以如果z.p是下次迭代开始的根，那么它就是黑色的。
3. 跟情形1一样，性质1、3和5在情形2，3中也得以保持。由于在情形2和3中，结点z不是根，我们知道这不会破坏性质2，由于唯一结着成红色的结点在情形3变成一个黑色结点的子女。情形2和3修正了性质4的破坏，同时它们也不会引进新的破坏。

在讨论每次循环迭代维护不变式时，我们也证明了RB-INSERT-FIXUP正确地恢复了红黑树的性质。

分析

RB-INSERT的运行时间是多少呢？由于n结点的红黑树的高度是O(lg n)，RB-INSERT第1到16行花费了O(lg n)时间。在RB-INSERT-FIXUP中，while循环只有遇到情形1的时候才会重复循环，然后z向树上移动两层。while循环执行的总次数因此是O(lg n)。因此RB-INSERT总共花了O(lg n)的时间。更有意思的是，它旋转次数决不会多于两次，因为如果执行了情形2或者情形3,while循环就结束了。

练习

13.3-1 在RB-INSERT的第16行，我们将新插入的结点z设置成了红色。观察如果我们选择将z的颜色设置成黑色，那么红黑树的性质4会不会破坏。为什么我不选择将z设置成红色？
13.3-2 成功将key为41,38,31,12,19,8都插入空的红黑树后，画出这棵红黑树。
13.3-3 假设在图13.5和图13.6中任意子树α，β，γ，δ和ε的back-height是k。标记每个结点的black-height去验证图示的转换能保持性质5。
13.3-4 Teach教授担心RB-INSERT-FIXUP可能会设置T.nil.color为红色，这样的话当z是根的时候循环将不会结点。通过证明RB-INSERT-FIXUP决不会将T.nil.color设置成红色来说明这位教授的担心是没有必要的。
13.3-4 假设红黑树是通过RB-INSERT插入n结点形成的。证明如果n>1,那么树中至少有一棵红结点。
13.3-6 考虑一下，如果红黑树表示没有存储双亲结点的指针，应该如何有效地实现RB-INSERT。
全文下载：第13章 红黑树

13.2 旋转

查找树操作TREE-INSERT和TREE-DELETE，运行在n个key的红黑树上，花费时间O(lg n)。由于改动了树，所以结果树可能不符合13.1节列举的红黑树的性质。为了恢复这些性质，我们必须改变树中一些结点的颜色和修改一指针结构。
我们通过旋转来修改指针结构，它是一个局部操作使查找树保持二叉查找树的属性。图13.2展示了两种旋转：左旋和右旋。当我们对结点x进行左旋时，我们假设y是x的右孩子并且不是T.nil； x可以是树中任意右孩子不空的结点。左旋的“轴”是沿着x到y的。它使y成为子树的根，x成为y的左孩子，y左孩子成为x的右孩子。
LEFT-ROTATE伪代码假设x.right≠T.nil和root的双亲为T.nil。

      图13.2 二叉查找树的左旋操作。左旋操作LEFT-ROTATE(T,x)通过修改常数个指针来改变两个结点的结构把右边的结点的结构变成左边的结构。相反的右旋操作RIGHT-ROTATE(T,y)将左边的结构变成右边的结构。α、β和γ表示任意形态的子树。旋转操作要保持二叉树的性质：α子树上的所有keys要小x.key,x.key要小于β子树上的所有keys，β子树的keys要小于y.key，y.key要小于γ子树上的所有的keys。

图13.3 展示了LEFT-ROTATE如何修改二叉查找树的实例。代码跟RIGHT-ROTATE是对称的。LEFT-ROTATE和RIGHT-ROTATE的运行时间者是O(1)。一次旋转只修改了指针；结点其它属性都保持不变。

图13.3 方法LEFT-ROTATE(T,x)如何修改一棵二叉查找树的实例。中序遍历输入树和中序遍历修改过后的树产生相同的key序列。

练习

13.2-1 写出RIGHT-ROTATE方法。
13.2-2 证明在任意n结点的二叉查找树上，刚好有n-1种可能的旋转。
13.2-3 设a,b,c分别是α、β和γ的任意结点，在图13.2的左侧。如图在结点x上做一次左旋转a,b,c的深度是如何变化的？
13.2-4 证明任意n结点的二叉查找树经过O(n)次旋转得其它任意形态的n结点二叉查找树。（提示：首先证明最多通过n-1次右旋可以将树的结构变成右链的形态。）
13.2-5 我们说如果通过一系列的调用RIGHT-ROTATE可以从二叉查找树T1转换成T2，那么二叉查找树T1右转（right-convert)成T2 。举出一个例子T1和T2，使得T1不能右转成T2。然后证明如果树T1右转成T2，那么它可以通过调用O(n^2)次RIGHT-ROTATE得到。
全文下载：第13章 红黑树

第12章我们讨论了在高度为h的二叉查找树能够在O(h)时间完成任何动态集操作，比如查找（SEARCH）,前躯（PREDECESSOR）,后继(SUCCESSOR),最小值（MINIMUM），最大值（MAXIMUM）,插入（INSERT）和删除（DELETE）操作。因此，如果树高矮的时候这些动态集的操作是很快的。如果树高很高的话，那么这些动态集的操作就没有链表快了。红黑树是众多“均衡”查找树中的一种，它可以保证基本的动态集操作在最坏的情况下运行时间为O(lg n)。

13.1 红黑树的性质

红黑树是一棵二叉查找树，并且每个结点都附加一个额外的存储位：结点颜色，它的值可以是红色或者黑色。通过对根到叶子路径上结点图色的限制，红色黑树保证没有哪一条路径是其它路径的二倍长，所以这棵树大致上是平衡的。
现在每个结点都包含属性color,key,left,right和p。如果结点没有孩子或者双亲结点不存在（译者著：根结点没有双亲结点，普通的叶子结点没有孩子），那么该结点的这些属性（译者著：孩子或者双亲指针）值是NIL。我们把这些NIL当作二叉树中指向叶子（外部结点）的指针，正常包含key的结点为树的内部结点。
红黑树是一种二叉查找树，并且还满足下面的红黑性质：

1. 每个结点不是红色就是黑色。
2. 根结点是黑色的。
3. 每个叶子结点（NIL）都是黑色的。
4.  如果一个结点是红色的，那么它所有的孩子都是黑色的。
5. 对于每一个结点，从当前结点到后代的叶子的路径上包含黑色结点的数量是相同的。

图13.1(a)展示了一棵红黑树的例子。
    为了方便处理边界条件，在实现红黑树的代码里，我们使用了一个哨兵结点也替换NIL（查看第238页）。对于一棵红黑树T，哨兵T.nil是跟树中普通结点有同样属性的一个对象。它的颜色是黑色，它的其它属性-p,left,right和key-可以是任意值。如图13.1(b)所示，所有NIL指针都替换成指向哨兵结点T.nil.
    我们使用哨兵结点是为了我们可以把x结点的NIL孩子看成是x的一个普通的孩子。尽管我们可以在树中我可以用不同的哨兵结点替换每一个NIL，第一个NIL的双亲都这样定义，但是这样将会很浪费空间。所以，我们使用一个哨兵结点T.nil代替所有NIL-所有以的叶子结点和根结点的双亲。哨兵结点的属性p,left,right和key都是无关紧要的，为了方便我们在方法里还是设置了它们。
    我们基本上只对内部结点有兴趣，是因为它们含有key值。本章剩下的部分，当我们绘制红黑树的时候，我们会忽略叶子，如图13.1(c)所示。
    我们把从结点x，不包括到x,向下到叶子结点的结点的任意路径上黑色结点的个数称为结点的black-height,记作bh(x)。通过性质5，black-height概念是明确的，结点所有下降的路径上都有数量相同的黑色结点。我们把红黑树root的black-height定义成这棵红黑色树的black-height。
    下面引理说明了为什么红黑树是一种好的搜索树。

引理13.1

具有n内部结点的红黑树的高度最高为2lg(n+1)。

证明

首先，我们论证对于以任意结点x为根的子树包含至少2^bh(x) – 1个内部结点。我们通过照给x的高度来证明这个论点。如是x的高度是0，那x一定是叶子(T.nil)，以x为根的子树的确包含至少2^bh(x) – 1=2^0-1=0个内部结点。接下来归纳，如果结点x的高度为正数并且是两个孩子的内部结点。每个孩子只的black-height是bh(x)或者bh(x-1),这取决于他们自身的颜色。由于x的孩子的高度肯定比x自身要低，我们用归纳假设得出每个孩子至少包含2^(bh(x)-1) – 1个内部结点。那么以x为根的子树包含至少2^(bh(x)-1) – 1 + 2^(bh(x)-1) – 1 +1 = 2^bh(x)-1个内部结点，这就证明了上面的提出的论点。
    为了完成引理的证明，假设树高为h。根据性质4，从根的出发到达叶子结点的任意路径，不包括根结点，至少有一半结点是黑色的。因此，根结点的black-height至少h/2;所以
    n ≥ 2^(h/2) – 1.
把1移到左边再把两边取对数，lg(n+1) ≤h/2,或h≤2log(n+1)
    由这个引理可以得出，我们可以用红黑色树去实现运行时间为O(lg n)动态集操作查找（SEARCH）,最小值（MINIMUM）,最大值（MAXIMUM）,后继（SUCCESSOR）和前驱（PREDECESSOR），因为在高度为h（第12章介绍的那样）的二叉查找树中每个操作的运行时间为O（h）,n结点的任意红黑树是高为O(lg n)的二叉树。（当然，在第12章中使用NIL指针要替换成T.nil。）对于给定的红黑树用第12章的TREE-INSERT和TREE-DELETE算法运行时间也是O(lg n)，但是这两个算法不能直接支持动态集操作INSERT和DELETE，因为它们不保证修改过的二叉树是否仍然是红黑树。然而，在13.3和13.4节，我们将看到如何在O(lg n)运行时间内实现这两种操作。

图13.1 这是一棵红黑树，黑色表示黑结点，阴影表示红结点。红黑树中的每一个结点，不是红色的就是黑色的，红结点的孩子都是黑色的，从某结点到叶子结点的所有路径中的有相同数量的黑结点。（a）每一个叶子，用NIL来表示，是黑色的。每一个非NIL结点都标记它的black-height；NIL结点的black-heigth为0.(b)同样的红黑树，但是用一个T.nil替换了所有的NILL，它总是黑色的，并且它的black-height被忽略。根结点的双亲是哨兵。（c）同样的红黑色树，但是叶子结点和根的双亲被完全忽略了。在本章的剩余部分，我们将用这种方式绘制红黑树。

练习

13.1-1 按照13.1(a)的方式，绘制高度为3的完全二叉查找树,key值为{1,2,…,15}。添加NIL叶子结点并分别画出black-height为2，3，4三种不同方式的红黑树。
13.1-2 画出向图13.1中的树调用TREE-INSERT，key为36的结点后的红黑树。如果插入的结点着成红色它还是一棵红黑树吗？如果着成黑色呢？
13.1-3 让我定义一种relaxed red-black树，它一棵二叉查找树，并且满足红黑树的性质1，3，4和5。换句说，根可能是红色或者黑色。假设有一棵relaxed red-black树T，它的根是红色的。如果我们将根着成黑色树T其它的都不变，那么着色后它是一棵红黑树吗？
13.1-4 假设在红黑色树我们让每个红色结点都被它的黑色双亲结点“吸纳”，那么红色结点的孩子都变成黑色双亲的孩子。（忽略key的变化）所有红色结点被吸纳后，黑色结点可能的度是多少？你能说出结果这个棵树的高度是多少吗？
13.1-5 证明在红黑树中从结点x开始到叶子最长路径的长度最多是从结点x开始到叶子的最短路径的两倍。
13.1-6 在高度为k的红黑树中内部结点数量最多是多少？最少是多少？
13.1-7 请描述下n个key构成的红黑树，它的红色内部结点与黑色内部结点比值最大，这个最大比值是多少？那比值最小的红黑树是什么样的，比值是多少？
全文下载：第13章 红黑树

12.3 二叉树的插入和删除

插入和删除操作将会导致由二叉树表示的动态集合改变。要反应出这种变化，数据结构也会作出相应变化，但在修改的同时，二叉树的性质还要继续保持。正如我们看到的那样向树中插入一个新元素相对比较简单，但是处理删除操作就更加复杂了。
插入
向二叉查找树T插入一个新的元素v，我们使用TREE-INSERT方法。方法传入一个z,并且z.key=v,z.left=NIL,z.right=NIL.这个方法会将会修改T和z的一些属性，并将z插入到树的合适的位置。


图12.3 向二叉查找树中插入key为13的数据项。浅色阴影部分标明了一条从根到插入数据项的自上而下的简易路径。虚线表明了向树中添加项的链接。

图12.3展示了TREE-INSERT的工作原理。跟TREE-SEARCH和ITERATIVE-TREE-SEARCH一样，TREE-INSERT也是从根开始指针x向下遍历找到NIL替换成输入项z。这个方法维护跟踪指针y作为x的双亲。初始化完成后，第3-7行的while循环中使两个指针沿树直下而上，向左还是向右取决非于z.key与x.key的比较，直到x变成NIL。该NIL的位置就是我希望的项z插入的位置。我们还需要尾随的指针y，因为当我找到z插入的NIL位置，搜索程序往结点后一步找到需要修改的结点。第8-13行设置了相应的指针使z插入。
跟其他的二叉查找树的原始操作一样，TREE-INSERT在高为h的树中运行时间是O(h)。

删除
在二叉查找树T中删除结点z的所有方法中有三种情况，正如我们将看到的那样，有一种情况有一点复杂。

• 如果z没有孩子，我们简单的删除它并修改它的双亲，用NIL作为孩子来代替z。
• 如果z只有一个孩子，我们通过修改z双亲，用该孩子替换z,提升这个孩子代替z在树中的位置。
• 如果z有两个孩子，我们先找到z的后继y，y一定在z的右子树，然后用y替换z的位置，然后z原来的右子树变成y的新右子树，z的左子树变成y的新左子树。这种情况有一点小复杂，因为正我们所看到的，y必须是z的右孩子。

删除二叉查找树T中的指定结点z的的方法需要两个参数指针T和z.它的过程跟之前描述的三种情况有点点不同，如图12.4考虑到了四种情况。

• 如果z没有左孩子(图中的a部分),我们将右孩子替换z,右孩子也有可能是NIL。当z的右孩子为NIL，这种情况等同于z没有孩子那个情形处理。当z的右孩子为非NIL，这种情况的处理相当于z只有一个孩子，并且这个孩子是右孩子。
• 如果z只有一个孩子，这个孩子是左孩子（图中的b部分）,那我们就用z的左孩子替换z。
• 除此之外，z即有左孩子又有右孩子。我们找到z的后继y，y分布在z的右子树上并且没有左孩子（查看练习12.2-5）。我们想把y拼接到当前输出的位置这样就替换了z的位置。
• 如果y是z的右孩子（图示c部分），那我们就用y替换z, 只剩下了y的右孩子。
• 除此之外，y在z的右子树里面，并不是z的右孩子（图示d部分）.这种情况，我们首先我们用y来替换z的右孩子，然后再用y来替换z.

为了方便在二叉查找树中移动子树，我们定义了一个子方法TRANSPLANT，用v为根结点的子树替换以u为根结点的子树，u的双亲变成v的双亲，并且u的双亲连接v作为它合适的孩子(译者注：如果u是双亲的左孩子，那么v就是双亲左孩子，反之亦然)。

第1-2行处理u是根的情况。除此之外，u的双亲不是有左子树就是有右子树(译者注：u如果有双亲，那么u的双亲至少有一个孩子)。第3-4行如果u是一个左孩子更新u.p.left，第5行表示如果u是右孩子更新u.p.right.我们允许v为NIL，第6-7如果v为非NIL，更新v.p。TRANSPLANT没有尝试去更新v.left和v.right；要不更去更新，取决于TRANSPLANT的调用者。

图12.4 从二叉查找树中删除结点z。z结点可能是根结点，结点的q的左孩子或者结点q的右孩子。(a)z没有左孩子。我们拿它的右孩子r替换z,r可能是空或者非空。(b)结点z有左孩子l但没有右孩子。我们拿l替换z.(c)结点z有两个孩子；它的左孩子为l,它的右孩子为就是它的后继y,y的右孩子为结点x.我们用y来替换z,y的左孩子变成了l,剩下的x作为y的右孩子。(d)结点z有两个孩子（左孩子为l并且右孩子为r）,并且它的后继y≠r,y在它的右子树里，右子树根结点为r。我们用y的右孩子x替换y，并且我设置y为r的双亲。然后我们设置y为q的孩子，设置y为l的双亲。

利用上面的方法TRANSPLANT，下面方法是从二叉查找树T删除结点z：

TREE-DELET方法处理了下面的四种情况。第1-2行得理结点z有左孩子，第3-4行处理z有左孩子但没有右孩子的情形。第5-12处理剩下z有两个孩子的两种情况。第5找到y,y是z的后继。因为z右子树非空，它的后继一定是右子树key最小的结点；因此调用方法TREE-MINIMUM(z.right)。从前面的介绍，我们可以知道y没有左孩子（译者注：因为y是z右子树中key最小的结点，故y没有左孩子）。我们想把y拼接到当前输出的位置并且替换树中的z。如果y是z的右孩子，第10-12行用y替换了作为z双亲的孩子替换了z,用z的左孩子替换了 y的左孩子。如是y不是z的左孩子（译者注：这里应该“如果y不是z的右孩子”）第7-9行用y的右孩子作为y双亲的孩子替换y然后把z的右孩子变成y的右孩子，然后第10-12行用y作为z的双亲的孩子替换z,用z的左孩子替换y的左孩子。

TREE-DELETE除了第5行调用了TREE-MINIMUM之行，其它每一行代码，包括调用TRANSPLANT都花费常数时间。因此TREE-DELETE在高为h的树运行时间为O(h).
总之，我们证明了下面的定理。
定理12.2
在高度为h的二叉查找树上，我们实现的动态集操作，INSERT,DELETE运行时间都是O(h)。
练习12.2
12.3-1  给出TREE-INSERT方法的递归版本。
12.3-2 假想我们反复向二叉树插入不同的元素来构建一棵二叉查找树。证明从中查找某一个结点所要检查结点的数量等于首次向树中插入该结点所要检查结点的数量加1.
12.3-3 我们可以通过构建二叉查找树（使用TREE-INSERT反复一个一个地插入数字）对给定有数字集合进行排序，然后中序打印遍历打印这些数字。对于这种排序算法它的最坏情况与最好情况的运行时间是多少？
12.3-4 对二叉查找树的删除先从二叉查找树中删除x再删除y和先从二叉树删除y再删除y的操作是可交换吗?证明是或者举出一个反例。
12.3-5 假设替换结点属性x.p成x.succ，x.p指向双亲结点,x.succ指向x的后继指点。使用这个属性给出二叉查找树T的SEARH,INSERT和DELETE操作的方法。在高为h二叉查找树中，这些方法运行时间是O(h)。（提示：你可以实现一个子方法返回双亲结点）。
12.3-6 在TREE-DELETE中删除结点z时，我们可以选择前驱结点y而不是后继结点。如果这样做TREE-DELETE要做哪些改变？有些人提出一个公平策略，前驱和后继具有相同的优先级，而获取更高的性能。如何修改TREE-DELETE实现这个公平策略。
全文下载:Chapter_12-Binary_Search_Trees

12.2 二叉树的搜索

我们经常需要在二叉查找树查找某个key。除了查找（SEARCH）操作之外，二叉查找树也支持譬如最小值（MINIMUM），最大值（MAXIMUM），后继（SUCCESSOR）和前驱（PREDECESSOR）的查找。在本节，我们将会考查这些操作并且给出如何在高度为h的二叉查找树中，用O(h)时间内完成这些操作。

查找

我们使用下面的方法在二叉查找树中查找指定的key的结点。指定树的根结点root和键值k, TREE-SEARCH返回键值为k的指针，如果不存在k则返回NIL。

图12.2 搜索二叉查找树。要在树中查找key为13的结点，搜索路径为从树出发15->6->7->13。树中最小key值为2，它沿树根的left指针上可以找到。最大key值20，它沿树根的right指针上可以找到。结点key为15的后继是key为17的结点，因为key为17的结点是key为15结点的右子树上key最小的结点。Key为13的结点没有右子树，因此它的后继是它最低的祖先，该祖先的左孩子也是一个祖先。在本例中，key为15的结点是13的后继。

上面的方法从树根开始查找并沿树枝的路径向下搜索，如图12.2所示。每个遍历到地结点，它都会拿这结点的值跟目标对比，如两个值相等，搜索结束。如果k小于前结点的x->key,将会在x的左子树继续搜索，因为根据二叉查找树的性质表明了k不可能x的右子树中。同理，如果k大于前结点的x->key,将会在x的右子树继续搜索。递归遍历的结点形了一条由树根向下的路径。因此TREE-SEARCH运行时间是O(h),h为树的高度。

我们可以用while循环迭代“铺开”递归过程重写上面的算法。在大多数计算机中，这个算法的迭代版本会更高效一点。

最小值和最大值

在二叉查找树上，我们可以从根结点出发沿着结点的left指针直到某个结点的left为空，就可以找到二叉树中key最小的那个元素，如图12.2所示。下面的方法返回以指定结点x为根的二叉树中key最小的元素，假设x为非空。

二叉的性质保持TREE-MINIMUM方法是正确的。如果一个结点没有左子树，那么结点x的右子树上的所有结点的key都不小于x->key,那么根结点key肯定是它们当中的最小值。如果结点x有左子树，那么右子树上没有节点的key比x->key小并且左子树上的结点都不大于x->key,所以以x为根节点的子树上最小值一定在以左子树x->left为根的子树中。

同上，TREE-MAXIMUM方法的伪代码：

同TREESEARCH一样，上述的两个方法在高度为h的树中都要花费O(n),访问的结点形成了一条由根出的向上的一条简易的路径。

后继和前驱

给出一棵二叉查找树上指定的结点，有时候我们需要找到这个结点的中序遍历的顺序的后继。（译者注：二叉查找的中序遍历序列下是有序的）。如果所有结点的key都是不相同的结点x的后继是那些key大于x->key之中最小那个的结点。二叉树的结构特点，使我们不需要比较key就能找到指定结点的后继。下面的方法返回结点x的后继，如果x的key是二叉树中最大的则返回NIL。

我们在TREE-SUCCESSOR方法中的两种情况下退出返回。如果x结点的右子树非空，那么结点x的后继就是它右子树中最左那的结点，在第2行我们可看到调用了TREE-MINIMUM(x->right)。举个例子，在图12.2中key为15的结点后继是key为17的结点。

另一种情况，如练习12.2-6让你去实现的那样，如果x结点的右子树是空的并且x有祖先y，那y是x的祖先中最小的那个祖先，并且y的左孩子也是x的祖先。在图12.2中，key为13的结点的后继是key为15。为了找到y，我们简单的从x向上查找直到我们找到某个结点是双亲结点的左孩子为止；TREE-SUCCESSOR中第3到7行就为了处理这种情况。
TREE-SUCCESSOR在高为h的树上的运行时间是O(h)，因为我们是沿着树向上或者向下的一条简单的路径。TREE-PREDECESSOR,跟TREE-SUCCESSOR同理，运行时间也是O(h)。
即使所有key不都是完全相同，我们也把TREE-PREDECESSOR(x)返回结点作为x的前驱，TREE-SUCCESSOR(x)返回的作为后继。

总之，我们通过上面的叙述证明这样一个定理：

定理12.2 在高度为h的二叉查找树上，我们实现的动态集操作，SEARCH,MINIMUM,MAXIMUM，SUCCESSOR和PREDECESSOR运行时间都是O(h)。

练习
12.2-1 假设我们有一棵二叉查找树，元素值是都是在1到1000之间，我们想查找数字363.下面哪个查找序列不属于正确的访问序列。
a. 2, 252, 401, 398, 330, 344, 397, 363.
b. 924, 220, 911, 244, 898, 258, 362, 363.
c. 925, 202, 911, 240, 912, 245, 363.
d. 2, 399, 387, 219, 266, 382, 381, 278, 363.
e. 935, 278, 347, 621, 299, 392, 358, 363.
12.2-2 写出递归版本的TREE-MINIMUM和TREE-MAXIMUM
12.2-3 写出TREE-PREDECESSOR方法
12.2-4 Bunyan教授认为他发现了二叉查找树的一个重要的性质。假设在二叉查找树上查找key为k的结点,并且key为k的结点是一个叶子结点。那么有三个集合：A，搜索路径的左边结点集合；B，搜索路径上的结点；C是搜索路径右边的结点集合。Buyan教授认为对于三个集合的任意值a∈A，b∈B，c∈C一定满足a≤b≤c。对于上面的观点，请给出最小可能一个的反例。
12.2-5 证明：对于二叉查找树，如果一个结点有两个孩子，那么它的后继没有左孩子并且它的前驱没有右孩子。
12.2-6 二叉查找树T是没有重复key的集合。证明如果结点x的右子树为空并且x有后继y，那么y是x的最低祖先，并且y的左孩子也是x的祖先。（注意每个结点都是自己的祖先）。
12.2-7 有一种非常规的方法中序遍历n个结点的二叉查找树。通过TREE-MINIMUM找到最小元素然后通过n-1次调用TREE-SUCCESSOR。证明这种算法运行时间为O(n)。
12.2-8 证明不论从高度为h的二叉查找树的哪个结点开始，连续k次调用TREE-SUCCESSOR将花费O(k+h)时间。（译者注：前一次调用的结果作为后一次的调用参数）。
12.2-9 T是没有重复key的二叉查找树。如果x为它的一个叶子结点，y为x的双亲。证明y.key是T中大于x.key的集合中最小的或者y.key是T中小于x.key的集合中最大的。
全文下载:Chapter_12-Binary_Search_Trees