红黑树

万次阅读 2011-02-11 21:56:00

介绍另一种平衡二叉树：红黑树（Red Black Tree），红黑树由Rudolf Bayer于1972年发明，当时被称为平衡二叉B树（symmetric binary B-trees），1978年被Leonidas J. Guibas 和Robert Sedgewick改成一个比较摩登的...

介绍另一种平衡二叉树：红黑树（Red Black Tree），红黑树由Rudolf Bayer于1972年发明，当时被称为平衡二叉B树（symmetric binary B-trees），1978年被Leonidas J. Guibas 和Robert Sedgewick改成一个比较摩登的名字：红黑树。

红黑树和之前所讲的AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。自从红黑树出来后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。不过在我了解了红黑树的实现原理后，并不相信这是真的，关于这一点我们会在后面进行讨论。

红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。之前我们在讲解AVL树时，已经领教过AVL树的复杂，但AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。

首先来一个Silverlight做的红黑树的动画，它有助于帮你理解什么是红黑树。这里需要注意，必须安装Silverlight 2.0 RTW 才能正常运行游戏，下载地址：

http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0

使用注意事项：

l 结点只接收整数，如果在添加和删除操作中输入非法字串，则会随机添加或删除一个0~99之间的整数。

l 可以不在编辑框中输入数字，直接单击添加和删除按钮进行添加和删除操作。

l 可以拖动拖动条控制动画速度。

红黑树的平衡

红黑树首先是一棵二叉查找树，它每个结点都被标上了颜色（红色或黑色），红黑树满足以下5个性质：

1、 每个结点的颜色只能是红色或黑色。

2、 根结点是黑色的。

3、 每个叶子结点都带有两个空的黑色结点（被称为黑哨兵），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。

4、 如果一个结点是红的，则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

5、 对于每个结点来说，从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。

红黑树的这5个性质中，第3点是比较难理解的，但它却非常有必要。我们看图1中的左边这张图，如果不使用黑哨兵，它完全满足红黑树性质，结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后（如图1右图中的小黑圆点），叶结点的个数变为8个黑哨兵，根结点50到这8个叶结点路径上的黑高度就不一样了，所以它并不是一棵红黑树。

要看真正的红黑树请在以上动画中添加几个结点，看看是否满足以上性质。

红黑树的旋转操作

红黑树的旋转操作和AVL树一样，分为LL、RR、LR、RL四种旋转类型，差别在于旋转完成后改变的是结点的颜色，而不是平衡因子。旋转动画演示请参考AVL这篇文章中的Flash动画：

http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html

红黑树上结点的插入

在讨论红黑树的插入操作之前必须要明白，任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点父结点为红色时（如图2所示），将会违返红黑树性质：一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。

为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点；使用“父”字表示新插入点的父结点；使用“叔”字表示“父”结点的兄弟结点；使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况：

1、黑父

如图3所示，如果新点的父结点为黑色结点，那么插入一个红点将不会影响红黑树的平衡，此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。

2．红父

如果新点的父结点为红色，这时就需要进行一系列操作以保证整棵树红黑性质。如图3所示，由于父结点为红色，此时可以判定，祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作，而每次进行不平衡判断的起始点（我们可将其视为新点）都不一样。所以我们在此使用一个蓝色箭头指向这个起始点，并称之为判定点。

2.1 红叔

当叔父结点为红色时，如图4所示，无需进行旋转操作，只要将父和叔结点变为黑色，将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色，从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上进行平衡操作。

需要注意，无论“父”在“叔”的左边还是右边，无论“新”是“父”的左孩子还是右孩子，它们的操作都完全一样。

2.2 黑叔

当叔父结点为黑色时，需要进行旋转，以下图示了所有的旋转可能

情形1：

情形2：

情形3：

情形4：

可以观察到，当旋转完成后，新的旋转根全部为黑色，此时不需要再向上回溯进行平衡操作，插入操作完成。需要注意，上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。

其实红黑树的插入操作不是很难，甚至比AVL树的插入操作还更简单些。但删除操作就远远比AVL树复杂得多，下面就介绍红黑树的删除操作。

红黑树上结点的删除

红黑树本身是一棵二叉查找树，它的删除和二叉查找树的删除类似。首先要找到真正的删除点，当被删除结点n存在左右孩子时，真正的删除点应该是n的中序遍在前驱，关于这一点请复习二叉查找树的删除。如图9所示，当删除结点20时，实际被删除的结点应该为18，结点20的数据变为18。

所以可以推断出，在进行删除操作时，真正的删除点必定是只有一个孩子或没有孩子的结点。而根据红黑树的性质可以得出以下两个结论：

1、 删除操作中真正被删除的必定是只有一个红色孩子或没有孩子的结点。

2、 如果真正的删除点是一个红色结点，那么它必定是一个叶子结点。

理解这两点非常重要，如图10所示，除了情况(a)外，其他任一种况结点N都无法满足红黑树性质。

在以下讨论中，我们使用蓝色箭头表示真正的删除点，它也是旋转操作过程中的第一个判定点；真正的删除点使用“旧”标注，旧点所在位置将被它的的孩子结点所取代（最多只有一个孩子），我们使用“新”表示旧点的孩子结点。删除操作可分为以下几种情形：

1、旧点为红色结点

若旧点为红色结点，则它必定是叶子结点，直接删除即可。如图11所示

2、一红一黑

当旧点为黑色结点，新点为红色结点时，将新点取代旧点位置后，将新点染成黑色即可（如图12所示）。这里需要注意：旧点为红色，新点为黑色的情况不可能存在。

3、双黑

当旧点和新点都为黑色时（新点为空结点时，亦属于这种情况），情况比较复杂，需要根据旧点兄弟结点的颜色来决定进行什么样的操作。我们使用“兄”来表示旧点的兄弟结点。这里可分为红兄和黑兄两种情况：

3.1 红兄

由于兄弟结点为红色，所以父结点必定为黑色，而旧点被删除后，新点取代了它的位置。下图演示了两种可能的情况：

红兄的情况需要进行RR或LL型旋转，然后将父结点染成红色，兄结点染成黑色。然后重新以新点为判定点进行平衡操作。我们可以观察到，旋转操作完成后，判定点没有向上回溯，而是降低了一层，此时变成了黑兄的情况。

3.2 黑兄

黑兄的情况最为复杂，需要根据黑兄孩子结点（这里用“侄”表示）和父亲结点的颜色来决定做什么样的操作。

3.2.1 黑兄二黑侄红父

如图14所示，这种情况比较简单，只需将父结点变为黑色，兄结点变为黑色，新结点变为黑色即可，删除操作到此结束。

3.2.2 黑兄二黑侄黑父

如图15所示，此时将父结点染成新结点的颜色，新结点染成黑色，兄结点染成红色即可。当新结点为红色时，父结点被染成红色，此时需要以父结点为判定点继续向上进行平衡操作。

3.2.3 黑兄红侄

黑兄红侄有以下四种情形，下面分别进行图示：

情形1：

情形2：

情形3：

情形4：

由以上图例所示，看完以上四张图的兄弟有可能会有一个疑问，如果情形1和情形2中的两个侄子结点都为红色时，是该进行LL旋转还是进行LR旋转呢？答案是进行LL旋转。情形3和情形4则是优先进行RR旋转的判定。

教你透彻了解红黑树

作者 July、saturnman 2010年12月29日

本文参考：Google、算法导论、STL源码剖析、计算机程序设计艺术。
本人声明：个人原创，转载请注明出处。

推荐阅读：Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008.

------------------------------
红黑树系列，四篇文章于今日已经完成。[二零一一年一月九日]

教你透彻了解红黑树：
http://blog.csdn.net/v_JULY_v/archive/2010/12/29/6105630.aspx
红黑树算法的层层剖析与逐步实现 [此文被推荐]
http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx
教你彻底实现红黑树：红黑树的c源码实现与剖析
http://blog.csdn.net/v_JULY_v/archive/2011/01/03/6114226.aspx
一步一图一代码，一定要让你真正彻底明白红黑树 [最后更新]
http://blog.csdn.net/v_JULY_v/archive/2011/01/09/6124989.aspx

------------------------------

一、红黑树的介绍

先来看下算法导论对R-B Tree的介绍：
红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其
他路径长出俩倍，因而是接近平衡的。

前面说了，红黑树，是一种二叉查找树，既然是二叉查找树，那么它必满足二叉查找树的一般性质。
下面，在具体介绍红黑树之前，咱们先来了解下二叉查找树的一般性质：
1.在一棵二叉查找树上，执行查找、插入、删除等操作，的时间复杂度为O（lgn）。
因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）。
//至于n个结点的二叉树高度为lgn的证明，可参考算法导论第12章二叉查找树第12.4节。
2.但若是一棵具有n个结点的线性链，则此些操作最坏情况运行时间为O（n）。

而红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）。

ok，我们知道，红黑树上每个结点内含五个域，color，key，left，right。如果相应的指针域没有，则设为NIL。

一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：

1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

下图所示，即是一颗红黑树：

此图忽略了叶子和根部的父结点。

二、树的旋转知识

当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。

为了保持红黑树的性质，我们可以通过对树进行旋转，即修改树种某些结点的颜色及指针结构，以达到对红黑树进行

插入、删除结点等操作时，红黑树依然能保持它特有的性质（如上文所述的，五点性质）。

树的旋转，分为左旋和右旋，以下借助图来做形象的解释和介绍：

1.左旋

如上图所示：

当在某个结点pivot上，做左旋操作时，我们假设它的右孩子y不是NIL[T]，pivot可以为树内任意右孩子而不是NIL[T]的结点。

左旋以pivot到y之间的链为“支轴”进行，它使y成为该孩子树新的根，而y的左孩子b则成为pivot的右孩子。

来看算法导论对此操作的算法实现（以x代替上述的pivot）：

LEFT-ROTATE(T, x)
1 y ← right[x] ▹ Set y.
2 right[x] ← left[y] ▹ Turn y's left subtree into x's right subtree.

3  p[left[y]] ← x
4  p[y] ← p[x]             ▹ Link x's parent to y.
5  if p[x] = nil[T]
6     then root[T] ← y
7     else if x = left[p[x]]
8             then left[p[x]] ← y
9             else right[p[x]] ← y
10  left[y] ← x             ▹ Put x on y's left.
11  p[x] ← y

2.右旋

右旋与左旋差不多，再此不做详细介绍。

对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，

在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。

至于有些书如 STL源码剖析有对双旋的描述，其实双旋只是单旋的两次应用，并无新的内容，

因此这里就不再介绍了，而且左右旋也是相互对称的，只要理解其中一种旋转就可以了。

三、红黑树插入、删除操作的具体实现

三、I、ok，接下来，咱们来具体了解红黑树的插入操作。
向一棵含有n个结点的红黑树插入一个新结点的操作可以在O（lgn）时间内完成。

算法导论：
RB-INSERT(T, z)
1 y ← nil[T]
2 x ← root[T]
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]
8 p[z] ← y
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
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED
17 RB-INSERT-FIXUP(T, z)

咱们来具体分析下，此段代码：
RB-INSERT(T, z)，将z插入红黑树T 之内。

为保证红黑性质在插入操作后依然保持，上述代码调用了一个辅助程序RB-INSERT-FIXUP
来对结点进行重新着色，并旋转。

14 left[z] ← nil[T]
15 right[z] ← nil[T] //保持正确的树结构
第16行，将z着为红色，由于将z着为红色可能会违背某一条红黑树的性质，
所以，在第17行，调用RB-INSERT-FIXUP（T,z）来保持红黑树的性质。

RB-INSERT-FIXUP(T, z)，如下所示：
1 while color[p[z]] = RED
2     do if p[z] = left[p[p[z]]]
3           then y ← right[p[p[z]]]
4                if color[y] = RED
5                   then color[p[z]] ← BLACK                    ▹ Case 1
6                        color[y] ← BLACK                       ▹ Case 1
7                        color[p[p[z]]] ← RED                   ▹ Case 1
8                        z ← p[p[z]]                            ▹ Case 1
9                   else if z = right[p[z]]
10                           then z ← p[z]                       ▹ Case 2
11                                LEFT-ROTATE(T, z)              ▹ Case 2
12                           color[p[z]] ← BLACK                 ▹ Case 3
13                           color[p[p[z]]] ← RED                ▹ Case 3
14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3
15           else (same as then clause
                         with "right" and "left" exchanged)
16 color[root[T]] ← BLACK

ok，参考一网友的言论，用自己的语言，再来具体解剖下上述俩段代码。
为了保证阐述清晰，我再写下红黑树的5个性质：

在对红黑树进行插入操作时，我们一般总是插入红色的结点，因为这样可以在插入过程中尽量避免对树的调整。
那么，我们插入一个结点后，可能会使原树的哪些性质改变列?
由于，我们是按照二叉树的方式进行插入，因此元素的搜索性质不会改变。

如果插入的结点是根结点，性质2会被破坏，如果插入结点的父结点是红色，则会破坏性质4。
因此，总而言之，插入一个红色结点只会破坏性质2或性质4。
我们的回复策略很简单，
其一、把出现违背红黑树性质的结点向上移，如果能移到根结点，那么很容易就能通过直接修改根结点来恢复红黑树的性质。直接通过修改根结点来恢复红黑树应满足的性质。
其二、穷举所有的可能性，之后把能归于同一类方法处理的归为同一类，不能直接处理的化归到下面的几种情况，

//注：以下情况3、4、5与上述算法导论上的代码RB-INSERT-FIXUP(T, z)，相对应：

情况1：插入的是根结点。
原树是空树，此情况只会违反性质2。
对策：直接把此结点涂为黑色。
情况2：插入的结点的父结点是黑色。
此不会违反性质2和性质4，红黑树没有被破坏。
对策：什么也不做。
情况3：当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色。
此时父结点的父结点一定存在，否则插入前就已不是红黑树。
与此同时，又分为父结点是祖父结点的左子还是右子，对于对称性，我们只要解开一个方向就可以了。

在此，我们只考虑父结点为祖父左子的情况。
同时，还可以分为当前结点是其父结点的左子还是右子，但是处理方式是一样的。我们将此归为同一类。
对策：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法。

针对情况3，变化前（图片来源：saturnman）[插入4节点]：

变化后：

情况4：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子

对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。

如下图所示，变化前[插入7节点]：

变化后：

情况5：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子

解法：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋

如下图所示[插入2节点]

变化后：

==================

三、II、ok，接下来，咱们最后来了解，红黑树的删除操作：

算法导论一书，给的算法实现：

RB-DELETE(T, z)   单纯删除结点的总操作
1 if left[z] = nil[T] or right[z] = nil[T]
2    then y ← z
3    else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5    then x ← left[y]
6    else x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9    then root[T] ← x
10    else if y = left[p[y]]
11            then left[p[y]] ← x
12            else right[p[y]] ← x
13 if y 3≠ z
14    then key[z] ← key[y]
15         copy y's satellite data into z
16 if color[y] = BLACK
17    then RB-DELETE-FIXUP(T, x)
18 return y

RB-DELETE-FIXUP(T, x) 恢复与保持红黑性质的工作
1 while x ≠ root[T] and color[x] = BLACK
2     do if x = left[p[x]]
3           then w ← right[p[x]]
4                if color[w] = RED
5                   then color[w] ← BLACK                        ▹ Case 1
6                        color[p[x]] ← RED                       ▹ Case 1
7                        LEFT-ROTATE(T, p[x])                    ▹ Case 1
8                        w ← right[p[x]]                         ▹ Case 1
9                if color[left[w]] = BLACK and color[right[w]] = BLACK
10                   then color[w] ← RED                          ▹ Case 2
11                        x p[x]                                  ▹ Case 2
12                   else if color[right[w]] = BLACK
13                           then color[left[w]] ← BLACK          ▹ Case 3
14                                color[w] ← RED                  ▹ Case 3
15                                RIGHT-ROTATE(T, w)              ▹ Case 3
16                                w ← right[p[x]]                 ▹ Case 3
17                         color[w] ← color[p[x]]                 ▹ Case 4
18                         color[p[x]] ← BLACK                    ▹ Case 4
19                         color[right[w]] ← BLACK                ▹ Case 4
20                         LEFT-ROTATE(T, p[x])                   ▹ Case 4
21                         x ← root[T]                            ▹ Case 4
22        else (same as then clause with "right" and "left" exchanged)
23 color[x] ← BLACK

为了保证以下的介绍与阐述清晰，我第三次重写下红黑树的5个性质

（相信，重述了3次，你应该有深刻记忆了。:D）

saturnman：
红黑树删除的几种情况：

-------------------------------------------------
博主提醒：
以下所有的操作，是针对红黑树已经删除结点之后，
为了恢复和保持红黑树原有的5点性质，所做的恢复工作。

前面，我已经说了，因为插入、或删除结点后，
可能会违背、或破坏红黑树的原有的性质，
所以为了使插入、或删除结点后的树依然维持为一棵新的红黑树，
那就要做俩方面的工作：
1、部分结点颜色，重新着色
2、调整部分指针的指向，即左旋、右旋。

而下面所有的文字，则是针对红黑树删除结点后，所做的修复红黑树性质的工作。

二零一一年一月七日更新。
------------------------------------------------------------

(注：以下的情况3、4、5、6，与上述算法导论之代码RB-DELETE-FIXUP(T, x) 恢复与保持
中case1，case2，case3，case4相对应。)
情况1：当前节点是红色
    解法，直接把当前节点染成黑色，结束。
    此时红黑树性质全部恢复。
情况2：当前节点是黑色且是根节点
    解法：什么都不做，结束

情况3：当前节点是黑色，且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。
解法：把父节点染成红色，把兄弟结点染成黑色，之后重新进入算法（我们只讨论当前节点是其父节点左孩子时的情况）。
然后，针对父节点做一次左旋。此变换后原红黑树性质5不变，而把问题转化为兄弟节点为黑色的情况。

3.变化前：

3.变化后：

情况4：当前节点是黑色，且兄弟是黑色，且兄弟节点的两个子节点全为黑色。
解法：把当前节点和兄弟节点中抽取一重黑色追加到父节点上，把父节点当成新的当前节点，重新进入算法。（此变换后性质5不变）

4.变化前

4.变化后

情况5：当前节点颜色是黑色，兄弟节点是黑色，兄弟的左子是红色，右子是黑色。
解法：把兄弟结点染红，兄弟左子节点染黑，之后再在兄弟节点为支点解右旋，
之后重新进入算法。此是把当前的情况转化为情况6，而性质5得以保持。

5.变化前：

5.变化后：

情况6：当前节点颜色是黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意。

解法：把兄弟节点染成当前节点父节点的颜色，把当前节点父节点染成黑色，兄弟节点右子染成黑色，

之后以当前节点的父节点为支点进行左旋，此时算法结束，红黑树所有性质调整正确。

6.变化前：

6.变化后：

限于篇幅，不再过多赘述。更多，可参考算法导论或下文我写的第二篇文章。

完。

July、二零一零年十二月二十九日初稿。三十日凌晨修订。行文3个小时以上。

----------------

今下午画红黑树画了好几个钟头，贴俩张图：

红黑树插入的3种情况：

红黑树删除的4种情况：

ok，只贴俩张，更多，参考我写的关于红黑树的第二篇文章：

红黑树算法的层层剖析与逐步实现[推荐]
http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx

这篇文章针对算法实现源码分十层，层层、逐层剖析，相信，更清晰易懂。

//尤其文末针对红黑树的删除情况，层次清晰。

July、二零一零年十二月三十一日、最后更新。

收起

展开全文

算法 pivot tree

教你初步了解红黑树

万次阅读 多人点赞 2010-12-29 18:36:00

教你透彻了解红黑树 作者：July、saturnman 2010年12月29日本文参考：Google、算法导论、STL源码剖析、计算机程序设计艺术。推荐阅读：Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, ...

教你初步了解红黑树

作者：July、saturnman 2010年12月29日

本文参考：Google、算法导论、STL源码剖析、计算机程序设计艺术。

推荐阅读：

Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008，直接下载：http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf。
本文的github优化版：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md。

一、红黑树的介绍

红黑树，作为一棵二叉查找树，满足二叉查找树的一般性质。下面，来了解下二叉查找树的一般性质。

二叉查找树

二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树。
没有键值相等的节点（no duplicate nodes）。

因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质：

每个结点要么是红的要么是黑的。
根结点是黑的。
每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
如果一个结点是红的，那么它的两个儿子都是黑的。
对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。

（注：上述第3、5点性质中所说的NULL结点，包括wikipedia.算法导论上所认为的叶子结点即为树尾端的NIL指针，或者说NULL结点。然百度百科以及网上一些其它博文直接说的叶结点，则易引起误会，因，此叶结点非子结点）

如下图所示，即是一颗红黑树(下图引自wikipedia：http://t.cn/hgvH1l)：

此图忽略了叶子和根部的父结点。同时，上文中我们所说的 "叶结点" 或"NULL结点"，如上图所示，它不包含数据而只充当树在此结束的指示，这些节点在绘图中经常被省略，望看到此文后的读者朋友注意。

二、树的旋转知识

当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。

树的旋转分为左旋和右旋，下面借助图来介绍一下左旋和右旋这两种操作。

1.左旋

如上图所示，当在某个结点pivot上，做左旋操作时，我们假设它的右孩子y不是NIL[T]，pivot可以为任何不是NIL[T]的左子结点。左旋以pivot到Y之间的链为“支轴”进行，它使Y成为该子树的新根，而Y的左孩子b则成为pivot的右孩子。

LeftRoate(T, x)
y ← x.right				       //定义y：y是x的右孩子
x.right ← y.left	            //y的左孩子成为x的右孩子
if y.left ≠ T.nil
    y.left.p ← x	
y.p ← x.p				       //x的父结点成为y的父结点
if x.p = T.nil
	then T.root ← y
else if x = x.p.left
	then x.p.left ← y
else x.p.right ← y 
y.left ← x                       //x作为y的左孩子
x.p ← y

2.右旋

右旋与左旋差不多，再此不做详细介绍。

树在经过左旋右旋之后，树的搜索性质保持不变，但树的红黑性质则被破坏了，所以，红黑树插入和删除数据后，需要利用旋转与颜色重涂来重新恢复树的红黑性质。

至于有些书如《STL源码剖析》有对双旋的描述，其实双旋只是单旋的两次应用，并无新的内容，因此这里就不再介绍了，而且左右旋也是相互对称的，只要理解其中一种旋转就可以了。

三、红黑树的插入

要真正理解红黑树的插入，还得先理解二叉查找树的插入。磨刀不误砍柴工，咱们再来了解一下二叉查找树的插入和红黑树的插入。

如果要在二叉查找树中插入一个结点，首先要查找到结点要插入的位置，然后进行插入。假设插入的结点为z的话，插入的伪代码如下：

TREE-INSERT(T, z)
y ← NIL
x ← T.root
while x ≠ NIL
	do y ←  x
	if z.key < x.key
		then x ← x.left
	else x ← x.right
z.p ← y
if y == NIL
	then T.root ← z       
else if z.key < y.key
	then y.left ← z
else y.right ← z

红黑树的插入和插入修复

现在我们了解了二叉查找树的插入，接下来，咱们便来具体了解下红黑树的插入操作。红黑树的插入相当于在二叉查找树插入的基础上，为了重新恢复平衡，继续做了插入修复操作。

假设插入的结点为z，红黑树的插入伪代码具体如下所示：

RB-INSERT(T, z)
y ← nil
x ← T.root
while x ≠ T.nil
	do y ← x
	if z.key < x.key
		then x ← x.left
	else x ← x.right
z.p ← y
if y == nil[T]
	then T.root ← z
else if z.key < y.key
	then y.left ← z
else y.right ← z
z.left ← T.nil
z.right ← T.nil
z.color ← RED
RB-INSERT-FIXUP(T, z)

把上面这段红黑树的插入代码，跟之前看到的二叉查找树的插入代码比较一下可以看出，RB-INSERT(T, z)前面的第1～13行代码基本上就是二叉查找树的插入代码，然后第14～16行代码把z的左孩子和右孩子都赋为叶结点nil，再把z结点着为红色，最后为保证红黑性质在插入操作后依然保持，调用一个辅助程序RB-INSERT-FIXUP来对结点进行重新着色，并旋转。

换言之，如果插入的是根结点，由于原树是空树，此情况只会违反性质2，因此直接把此结点涂为黑色；如果插入的结点的父结点是黑色，由于此不会违反性质2和性质4，红黑树没有被破坏，所以此时什么也不做。

但当遇到下述3种情况时又该如何调整呢？

● 插入修复情况1：如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色
● 插入修复情况2：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子
● 插入修复情况3：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子

答案就是根据红黑树插入代码RB-INSERT(T, z)最后一行调用的RB-INSERT-FIXUP ( T , z )函数所示的步骤进行操作，具体如下所示：

RB-INSERT-FIXUP(T, z)
while z.p.color == RED
	do if z.p == z.p.p.left
		then y ← z.p.p.right
		if y.color == RED
			then z.p.color ← BLACK               ▹ Case 1
			y.color ← BLACK                    ▹ Case 1
			z.p.p.color ← RED                    ▹ Case 1
			z ← z.p.p                            ▹ Case 1
		else if z == z.p.right
			then z ← z.p                          ▹ Case 2
			LEFT-ROTATE(T, z)                   ▹ Case 2
		z.p.color ← BLACK                        ▹ Case 3
		z.p.p.color ← RED                         ▹ Case 3
		RIGHT-ROTATE(T, z.p.p)                  ▹ Case 3
	else (same as then clause with "right" and "left" exchanged)
T.root.color ← BLACK

下面，咱们来分别处理上述3种插入修复情况。

插入修复情况1：当前结点的父结点是红色，祖父结点的另一个子结点（叔叔结点）是红色。

如下代码所示：

while z.p.color == RED
	do if z.p == z.p.p.left
		then y ← z.p.p.right
		if y.color == RED

此时父结点的父结点一定存在，否则插入前就已不是红黑树。与此同时，又分为父结点是祖父结点的左孩子还是右孩子，根据对称性，我们只要解开一个方向就可以了。这里只考虑父结点为祖父左孩子的情况，如下图所示（勘误：图中15节点应改为13，特此说明，下同）：

对此，我们的解决策略是：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法。即如下代码所示：

			then z.p.color ← BLACK               ▹ Case 1
			y.color ← BLACK                    ▹ Case 1
			z.p.p.color ← RED                    ▹ Case 1
			z ← z.p.p                            ▹ Case 1

所以，变化后如下图所示：

于是，插入修复情况1转换成了插入修复情况2。

插入修复情况2：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子

此时，解决对策是：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。即如下代码所示：

		else if z == z.p.right
			then z ← z.p                          ▹ Case 2
			LEFT-ROTATE(T, z)                   ▹ Case 2

所以红黑树由之前的：

变化成：

从而插入修复情况2转换成了插入修复情况3。

插入修复情况3：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子

解决对策是：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋，操作代码为：

		z.p.color ← BLACK                        ▹ Case 3
		z.p.p.color ← RED                         ▹ Case 3
		RIGHT-ROTATE(T, z.p.p)                  ▹ Case 3

最后，把根结点涂为黑色，整棵红黑树便重新恢复了平衡。所以红黑树由之前的：

变化成：

「回顾：经过上面情况3、情况4、情况5等3种插入修复情况的操作示意图，读者自会发现，后面的情况4、情况5都是针对情况3插入节点4以后，进行的一系列插入修复情况操作，不过，指向当前节点N指针一直在变化。所以，你可以想当然的认为：整个下来，情况3、4、5就是一个完整的插入修复情况的操作流程」

四、红黑树的删除

接下来，咱们最后来了解，红黑树的删除操作。

"我们删除的节点的方法与常规二叉搜索树中删除节点的方法是一样的，如果被删除的节点不是有双非空子女，则直接删除这个节点，用它的唯一子节点顶替它的位置，如果它的子节点分是空节点，那就用空节点顶替它的位置，如果它的双子全为非空，我们就把它的直接后继节点内容复制到它的位置，之后以同样的方式删除它的后继节点，它的后继节点不可能是双子非空，因此此传递过程最多只进行一次。”

二叉查找树的删除

继续讲解之前，补充说明下二叉树结点删除的几种情况，待删除的节点按照儿子的个数可以分为三种：

没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了。
只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了。
有两个儿子。这是最麻烦的情况，因为你删除节点之后，还要保证满足搜索二叉树的结构。其实也比较容易，我们可以选择左儿子中的最大元素或者右儿子中的最小元素放到待删除节点的位置，就可以保证结构的不变。当然，你要记得调整子树，毕竟又出现了节点删除。习惯上大家选择左儿子中的最大元素，其实选择右儿子的最小元素也一样，没有任何差别，只是人们习惯从左向右。这里咱们也选择左儿子的最大元素，将它放到待删结点的位置。左儿子的最大元素其实很好找，只要顺着左儿子不断的去搜索右子树就可以了，直到找到一个没有右子树的结点。那就是最大的了。

二叉查找树的删除代码如下所示：

TREE-DELETE(T, z)
 1  if left[z] = NIL or right[z] = NIL
 2      then y ← z
 3      else y ← TREE-SUCCESSOR(z)
 4  if left[y] ≠ NIL
 5      then x ← left[y]
 6      else x ← right[y]
 7  if x ≠ NIL
 8      then p[x] ← p[y]
 9  if p[y] = NIL
10      then root[T] ← x
11      else if y = left[p[y]]
12              then left[p[y]] ← x
13              else right[p[y]] ← x
14  if y ≠ z
15      then key[z] ← key[y]
16           copy y's satellite data into z
17  return y

红黑树的删除和删除修复

OK，回到红黑树上来，红黑树结点删除的算法实现是：

RB-DELETE(T, z) 单纯删除结点的总操作

 1 if left[z] = nil[T] or right[z] = nil[T]  
 2    then y ← z  
 3    else y ← TREE-SUCCESSOR(z)  
 4 if left[y] ≠ nil[T]  
 5    then x ← left[y]  
 6    else x ← right[y]  
 7 p[x] ← p[y]  
 8 if p[y] = nil[T]  
 9    then root[T] ← x  
10    else if y = left[p[y]]  
11            then left[p[y]] ← x  
12            else right[p[y]] ← x  
13 if y ≠ z  
14    then key[z] ← key[y]  
15         copy y's satellite data into z  
16 if color[y] = BLACK  
17    then RB-DELETE-FIXUP(T, x)  
18 return y

“在删除节点后，原红黑树的性质可能被改变，如果删除的是红色节点，那么原红黑树的性质依旧保持，此时不用做修正操作，如果删除的节点是黑色节点，原红黑树的性质可能会被改变，我们要对其做修正操作。那么哪些树的性质会发生变化呢，如果删除节点不是树唯一节点，那么删除节点的那一个支的到各叶节点的黑色节点数会发生变化，此时性质5被破坏。如果被删节点的唯一非空子节点是红色，而被删节点的父节点也是红色，那么性质4被破坏。如果被删节点是根节点，而它的唯一非空子节点是红色，则删除后新根节点将变成红色，违背性质2。”

RB-DELETE-FIXUP(T, x) 恢复与保持红黑性质的工作

 1 while x ≠ root[T] and color[x] = BLACK  
 2     do if x = left[p[x]]  
 3           then w ← right[p[x]]  
 4                if color[w] = RED  
 5                   then color[w] ← BLACK                        ▹  Case 1  
 6                        color[p[x]] ← RED                       ▹  Case 1  
 7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1  
 8                        w ← right[p[x]]                         ▹  Case 1  
 9                if color[left[w]] = BLACK and color[right[w]] = BLACK  
10                   then color[w] ← RED                          ▹  Case 2  
11                        x ← p[x]                                ▹  Case 2  
12                   else if color[right[w]] = BLACK  
13                           then color[left[w]] ← BLACK          ▹  Case 3  
14                                color[w] ← RED                  ▹  Case 3  
15                                RIGHT-ROTATE(T, w)              ▹  Case 3  
16                                w ← right[p[x]]                 ▹  Case 3  
17                         color[w] ← color[p[x]]                 ▹  Case 4  
18                         color[p[x]] ← BLACK                    ▹  Case 4  
19                         color[right[w]] ← BLACK                ▹  Case 4  
20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4  
21                         x ← root[T]                            ▹  Case 4  
22        else (same as then clause with "right" and "left" exchanged)  
23 color[x] ← BLACK

“上面的修复情况看起来有些复杂，下面我们用一个分析技巧：我们从被删节点后来顶替它的那个节点开始调整，并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢，我们不是把红黑树的节点加上除红与黑的另一种颜色，这里只是一种假设，我们认为我们当前指向它，因此空有额外一种黑色，可以认为它的黑色是从它的父节点被删除后继承给它的，它现在可以容纳两种颜色，如果它原来是红色，那么现在是红+黑，如果原来是黑色，那么它现在的颜色是黑+黑。有了这重额外的黑色，原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了，做法还是尽量向根移动和穷举所有可能性。"--saturnman。

如果是以下情况，恢复比较简单：

a)当前节点是红+黑色
解法，直接把当前节点染成黑色，结束此时红黑树性质全部恢复。
b)当前节点是黑+黑且是根节点，解法：什么都不做，结束。

但如果是以下情况呢？：

删除修复情况1：当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)
删除修复情况2：当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色
删除修复情况3：当前节点颜色是黑+黑，兄弟节点是黑色，兄弟的左子是红色，右子是黑色
删除修复情况4：当前节点颜色是黑-黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意

此时，我们需要调用RB-DELETE-FIXUP(T, x)，来恢复与保持红黑性质的工作。

下面，咱们便来分别处理这4种删除修复情况。

删除修复情况1：当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。

解法：把父节点染成红色，把兄弟结点染成黑色，之后重新进入算法（我们只讨论当前节点是其父节点左孩子时的情况）。此变换后原红黑树性质5不变，而把问题转化为兄弟节点为黑色的情况(注：变化前，原本就未违反性质5，只是为了把问题转化为兄弟节点为黑色的情况)。即如下代码操作：

//调用RB-DELETE-FIXUP(T, x) 的1-8行代码
 1 while x ≠ root[T] and color[x] = BLACK
 2     do if x = left[p[x]]
 3           then w ← right[p[x]]
 4                if color[w] = RED
 5                   then color[w] ← BLACK                        ▹  Case 1
 6                        color[p[x]] ← RED                       ▹  Case 1
 7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1
 8                        w ← right[p[x]]                         ▹  Case 1

变化前：

变化后：

删除修复情况2：当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色。

解法：把当前节点和兄弟节点中抽取一重黑色追加到父节点上，把父节点当成新的当前节点，重新进入算法。（此变换后性质5不变），即调用RB-INSERT-FIXUP(T, z) 的第9-10行代码操作，如下：

//调用RB-DELETE-FIXUP(T, x) 的9-11行代码
9                if color[left[w]] = BLACK and color[right[w]] = BLACK
10                   then color[w] ← RED                          ▹  Case 2
11                        x p[x]                                  ▹  Case 2

变化前

变化后

删除修复情况3：当前节点颜色是黑+黑，兄弟节点是黑色，兄弟的左子是红色，右子是黑色。

解法：把兄弟结点染红，兄弟左子节点染黑，之后再在兄弟节点为支点解右旋，之后重新进入算法。此是把当前的情况转化为情况4，而性质5得以保持，即调用RB-INSERT-FIXUP(T, z) 的第12-16行代码，如下所示：

//调用RB-DELETE-FIXUP(T, x) 的第12-16行代码
12                   else if color[right[w]] = BLACK
13                           then color[left[w]] ← BLACK          ▹  Case 3
14                                color[w] ← RED                  ▹  Case 3
15                                RIGHT-ROTATE(T, w)              ▹  Case 3
16                                w ← right[p[x]]                 ▹  Case 3

变化前：

变化后：

删除修复情况4：当前节点颜色是黑-黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意。

解法：把兄弟节点染成当前节点父节点的颜色，把当前节点父节点染成黑色，兄弟节点右子染成黑色，之后以当前节点的父节点为支点进行左旋，此时算法结束，红黑树所有性质调整正确，即调用RB-INSERT-FIXUP(T, z)的第17-21行代码，如下所示：

//调用RB-DELETE-FIXUP(T, x) 的第17-21行代码
17                         color[w] ← color[p[x]]                 ▹  Case 4
18                         color[p[x]] ← BLACK                    ▹  Case 4
19                         color[right[w]] ← BLACK                ▹  Case 4
20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4
21                         x ← root[T]                            ▹  Case 4

变化前：

变化后：

最后值得一提的是上述删除修复的情况1~4都只是树的局部，并非树的整体全部，且删除修复情况3、4在经过上面的调整后，调整还没结束（还得继续调整直至重新恢复平衡，只是图并没有画出来）。
后面会继续修改完善下本文，感谢关注，thanks。

July、二零一四年九月十五日修订。

----------------

之前在学校寝室画红黑树画了好几个钟头，贴俩张图：

红黑树插入修复的3种情况：

红黑树删除修复的4种情况：

updated

继续请看本文的github优化版本：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md，或看看这个PPT：http://vdisk.weibo.com/s/zrFL6OXJNfNVU。另，对应新书《编程之法：面试和算法心得》3.1节。July、二零一四年五月三日。

收起

展开全文

算法 pivot tree