红-黑树

在第8章“二叉树”中已经讲过，普通的二叉搜索树作 为数据存储工具有重要的优势：可以快速地找到一个给定关 键字的数据项，并且可以快速地插入和删除数据项。其他的 数据存储结构，例如数组、有序数组以及链表，执行这些操作却很慢。因此，二叉搜索树似乎是理 想的数据存储结构。

遗憾的是，二叉搜索树有一个很麻烦的问题。如果树中插入的是随机数据，则执行效果很好。 但是，如果插入的是有序的数据（17, 21, 28, 36,…）或者是逆序的数据（36, 28, 21, 17,…）， 速度就变得特别慢。因为当插入的数值有序时，二叉树就是非平衡的了。而对于非平衡树，它的快 速查找（插入，删除）指定数据项的能力就丧失了。

本章将讨论一种解决非平衡树问题的方法：红-黑树，它是增加了某些特点的二叉搜索树。

还有其他的一些方法来保证树是平衡的。在本章的最后将会提到一些，并将讨论几种第10章 "2-3-4树和外部存储”中讲的2-3-4树和树。实际上，正如在那章中讲的那样，在2-3-4树上 的操作和在红-黑树上的操作有惊人的对应之处。

本章讨论的方法

本章将要讨论的在红-黑树中的插入方法和在己经讲过的在其他数据结构中的方法有一点不同。 理解红-黑树至关重要。因为这一点,也因为有大量的对称情况（如是左子节点或者是右子节点，内 部或者外部的子孙节点，等等），实际的代码要比人们想像的长而且复杂。因此通过研究代码学习 算法是十分困难的。所以，这一章中没有程序代码清单。可以利用第10章中2・3・4树的代码来创建 相似的功能。不过，本章学习的概念将对理解2-3-4树有所帮助，况且它们本身也相当有趣。

概念
现在用RBTree专题applet来帮助理解红-黑树的概念。下面将讲解读者如何与applet共同操作， 在树中插入一个新数据项。把人为的作用包括在插入例程中，肯定会使它的速度放慢，然而使读者 更容易理解这个过程的执行情况。

红.黑树中的搜索方法和普通二叉树的一样。然而在另一方面，尽管插入和删除操作都基于普通 树的算法，但有的改动非常大。因此，这一章的重点放在插入操作的处理上。

自顶向下插入
这里将讨论的插入算法称为自顶向下的插入，也就是说在搜索例程沿着树向下査找插入点，在

此进程中可能要对树的结构做一些改变。

另一种方法称为自底向上的插入。它需要找到插入新数据项的位置，然后沿着树向上改变树的 结构。自底向上插入效率比较低，这是因为必须顺着树扫描两趟。

平衡树和非平衡树

在开始讲解红•黑树之前，先来回顾一下树是如何变得 不平衡的。启动第8章中的Binary Tree专题applet (不是这 章中的RBTree专题applet)。点击Fill按钮创建一棵只有一 个节点的树，然后插入一系列关键字有序的数据项，其关键 字是升序或者是降序的。所得到的结果类似图9.1所示。

这些节点排列在一条直线上，没有分支。若关键字为 升序的，每一个节点都大于上一个插入的节点，每一个节 点都是上一个节点的右子节点，所有的节点都在根的一侧。 这棵树属于极端不平衡的情况。如果插入数据项的关键字 是按降序排列的，则每一个节点都是它父节点的左子节点, 节点都在另一侧，树也是极不平衡的。

图9.1插入升序排序的数据项

时间复杂度降低到O(N)

当树没有分支时，它其实就是一个链表。数据的排列是一维的，而不是二维的。不幸的是，和 在链表中一样，现在就必须要(平均)查找一半的数据项来寻找要找的数据项。在这种情况下，查 找的速度下降到O(N),而不是平衡树的O(logN)。在一棵有10000个数据项的非平衡树中捜索数据 项平均需要5000次比较，而在随机插入生成的平衡树中搜索数据项只需要14次比较。其实对于已 经有序的数据首先使用链表也无妨。

由部分有序的数据所生成的树只是部分不平衡。如果用第8章中的Binary Tree专题applet生成 31个节点的一棵树，可以看到这些节点中的一部分比另一部分不平衡，如图9.2所示。

图9.2部分非平衡树

尽管它比最不平衡的树情况要好，但是在这种情况下的査找时间不是最佳的。

在Binary Tree专题applet中，甚至对随机生成的数据，树都可能是部分非平衡的，这是因为数 据的数目太少，以至于很短的一段有序数据都会对树的平衡性造成很大的影响。同时，一个很小或 很大的关键字值也会产生一个不平衡树，因为这将使很多节点不能插入到这个节点的一边或者另一 边。例如，树的根是3,在根的左边就只允许再插入两个数据项。

对于随机数据的实际数量来说，一棵树特别不平衡的情况是不大可能的。但是，可能会有一小 部分有序数据使树部分非平衡。搜索部分非平衡树的时间介于0（N）和O（logN）之间，这取决于树的 不平衡程度。

平衡的补救

为了能以较快的时间O（logN）来搜索一棵树，需要保证树总是平衡的（或者至少大部分是平衡 的）。这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。

红-黑树的平衡是在插入的过程中（删除时也是，但暂时忽略这个问题）取得的。对一个要插入 的数据项，插入例程要检査不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更 改树的结构。通过维持树的特征，保持了树的平衡。

红-黑树特征
这种树有什么神奇的特征呢？有两个特征，一个简单，另一个比较复杂：

• 节点都有颜色。
• 在插入和删除的过程中，要遵循保持这些颜色的不同排列的规则•

带颜色的节点
在红-黑树中，每一个节点或者是黑色的或者是红色的。也可以是任意的两种颜色；蓝色和黄色 也是可以的。实际上，所说的节点有“颜色”是任意的比方。可以使用其他类似方法来表示：比如 可以说每一个节点不是深色的就是是浅色的，或者说不是阴就是阳。不过，颜色便于标记。在节点 类中增加一个数据字段，可以是boolean型的（例如，isRed）,以此来表示颜色的信息。

在RBTree专题applet中，节点的红•黑特征通过节点边界的颜色来表示的.在前面章节的Binary Tree专题applet中节点的中心颜色，只是节点随机生成的数据字段。

在这一章中说到节点颜色，几乎总是指节点的红■黑色的边界颜色。在这一章的图中（除了图 9.3之外），用加粗的黑色边界表示黑色节点，用白色边界表示红色节点。（注意有时显示的节点没 有边界，表示了节点无所谓黑色或者红色。）

红-黑规则

当插入（或者删除）一个新节点时，必须要遵循的一定的规则，它们被称为红-黑规则。如果遵 循这些规则，树就是平衡的。下面简要介绍一下这些规则：
1.每一个节点不是红色的就是黑色的。

2.根总是黑色的。

3.如果节点是红色的，则它的子节点必须是黑色的（反之倒不一定必须为真）。

4.从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。

规则4中的“空子节点”是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的 节点的可能接左子节点的位置，或者是有左子节点的节点的可能接右子节点位置。在下面的讲解中会更表现出它的意义。

在从根到叶节点的路径上的黑色节点的数目称为黑色高度（black height）o规则4的另一种陈 述方法是所有从根到叶节点路径上的黑色高度必须相同。

这些规则可能使人一头雾水。看不清楚这些规则怎么能使一棵树平衡，然而它们做到了；某些 很聪明的人发明了它们。请把这些规则抄在一个便签上，贴在计算机旁边，因为在这一章的学习中 需要经常查阅它们。

通过使用RBTree专题applet进行一些实验，以便了解上述这些规则是如何起作用的。但是在 实验前，应当先知道，如果违犯了一条红-黑规则，应该采取什么措施来修正。

重复的关键字
如果有多于一个数据项的关键字值相同，将会出现什么情况呢？这给红-黑树提出了一个小问 题。把有相同关键字的数据项分配到其他也有相同关键字数据项的两侧是很重要的。这也就是说， 如果关键字的序列为50, 50, 50,要把第二个50放到第一个50的右边，并且把第三个50放到第 一个50的左边。否则，树将不平衡。

在插入算法中，用某种随机的过程处理相同关键字节点的分配问题。但是，如果要找到所有相 同的关键字，插入过程就变得更复杂

因此不允许有关键字相同的数据项能使问题简单一些，目前的讨论假定不允许有重复关键字岀 现。

修正违规的情况

假设看到（或者applet提示）颜色的规则被违犯了。如何修正才能使树遵守上述规则呢？有两 个，而且只有这两个可能的修正措施：

• 改变节点的颜色。
• 执行旋转操作。

在applet中，改变节点的颜色就是要改变节点的红-黑边界的颜色（而不是中心的颜色）。旋转 是指重新排列节点，一次旋转使树更趋于平衡。
这些概念现在看起来可能很抽象，因此需要 熟悉一下RBTree专题applet,它有助于搞清楚这 些概念。

使用RBTree专题applet

用专题applet做试验

红-黑规则和平衡树

试创建一棵树，它虽然已经超过两层不平衡了，但却要满足红-黑规则。事实证明，这是不可能 的。这就是为什么红-黑规则能保证树是平衡的。如果一条路径上的节点数比另一条路径上的节点数多一个以上，那它要么有更多的黑色节点，违背了规则4,要么有两个相邻接的红色节点，违背了 规则3。通过在applet上做试验来证实这一点。

空子节点

回忆一下规则4,它明确指出从根到叶节点或空子节点的每条路径中，必须包含相同数目的黑 色节点。空子节点是指非叶节点本可能有，但实际上没有的那个子节点。（即，如果节点只有右子 节点，那么它的空缺的左子节点就是空子节点，反之亦然。）因此，在图9.8中从节点50到25再到 25的右子节点（它是空子节点）的路径只有一个黑色节点，而从根到6以及根到75的路径上右两个黑色节点。树的这种排列违背了规则4,尽管两条到叶节点的路径上的黑色节点数相同。

“黑色高度”是指从根到指定节点路径上的黑色节点数目。图9.8中节点50的黑色高度为1, 节点25的高度也是1,节点12的为2,以此类推。

图9.8到空子节点的路径

旋转
为了平衡一棵树，需要重新手动地排列节点。例如，如果所有的节点都在根的左侧，就需要把 一些节点移到右侧。这使用旋转来实现。这一节将要学习什么是旋转以及如何执行旋转。旋转必须 一次做两件事：

使一些节点上升，一些节点下降，帮助树平衡。

保证不破坏二叉搜索树的特征。

回想一下二叉搜索树的特征，即任何节点的左子节点及其子树的关键字值都小于该节点，而它 的右子节点及其子树的关键字值都大于或等于它。如果旋转不能保证树是一棵合法的二叉搜索树， 那它就没有什么用处，因为正如在前面章节已经讲过的，搜索算法的实现依赖于搜索树的这个排列 特征。

注意利用颜色规则和节点颜色变换只是有助于决定何时执行旋转。光改变单个节点的颜色不能 起到任何作用；旋转才是起关键作用的操作。颜色规则像盖房子时的拇指规则（例如“外面的门向 里开”），而旋转则像实际盖房子时所需的锤子和锯。

简单旋转

在试验2中做过向左和向右旋转。这些选择都很容易看出来，因为它们只包含三个节点。下面 来解释关于这个过程的一些问题。

什么是旋转？
“选择”这个术语可能会产生一点误导。节点自身是不会旋转的；旋转改变的只是节点之间的

关系。选择一个节点作为旋转的“顶端” （top）o如果做一次右旋，这个“顶端"节点将会向下和向 右移动到它右子节点的位置。它的左子节点将会上移到它原来的位置上。

注意顶端节点不是旋转的“中心"。如果拿汽车轮胎作比较，顶端节点并不是指轮轴或者轮毂 罩：它更像是轮胎胎面最上面的部分。

试验2中执行的旋转是以根作为顶端节点的，不过当然任何节点都可以作为旋转中的顶端节点， 只要它有适当的子节点。

注意子节点

必须要确保，如果做右旋，顶端节点必须有一个左子节点。否则，将没有节点旋转到顶端节点 原来所在的位置。类似的，如果做左旋，顶端节点必须有一个右子节点。
奇异的横向移动节点
旋转远比前面讨论过的三节点的例子要复杂得多。点击Start,然后节点50就已经在根的位置 上了，插入下列值的节点，顺序如下：25, 75, 12, 37o

当要插入节点12时，可以看到Can*t insert: needs color flip （不能插入：需要颜色变换）的信息 提示。点击Flip按钮。父节点和子节点的颜色发生改变。然后再次点击Ins按钮完成节点12的插入。 最后，插入节点37。插入的结果如图9.9a所示。

图9.9需要横向移动节点的旋转

现在试着做一次旋转。箭头指向根（不要忘了这一点！）然后点击RoR按钮。所有的节点都发 生了移动。节点12跟着节点25上升，节点50跟着节点75下降。

但这是怎么回事？节点37虽然是25的右子节点，但它断幵了和节点25的连接，并且取代25 成为节点50的左子节点。一些节点上升，一些节点下降。但是节点37却横向移动了。结果如图9.9b 所示。这次旋转破坏了规则4；后面将会看到如何解决这个问题。

在图9.9a显示的原来位置中，节点37称为顶端节点50的内侧子孙。（节点12是外侧子孙节点。） 对内侧子孙节点而言，如果它是上移节点（在右旋中是顶端节点的左子节点）的子节点，它总是要 断开和父节点的连接并且重新连接到它以前的祖父节点上。这就好像成为自己的叔叔一样。

移动子树

前面已经讲过了旋转过程中单个节点的位置改变，但是整棵子树也可以发生移动。为了解释这 个问题，点击Start按钮，节点50为根，然后按下列顺序插入节点序列：25, 75, 12, 37, 62, 87, 6, 18, 31, 43。只要因为提示信息Can’t insert: needs color flip （不能插入，需要颜色变换），而不 能完成插入操作时就点击Flip按钮。插入的结果如图9.10a所示。

图9.10旋转过程中的子树移动

箭头指向根节点50。现在点击RoR按钮。那么多节点的位置都发生了改变！结果如图9.10b 所示。下面是发生的事情：

•顶端节点（50）移动到它右子节点的位置。

•顶端节点的左子节点（25）移动到顶端的位置上。

•以节点12为根的整棵子树都向上移动。

•以节点37为根的整棵子树横向移动，成为节点50的左子节点。

•以节点75为根的整棵子树都向下移动。

将会出现提示信息Error: root must be black （根必须是黑色的），但是这里先暂时地忽略它。可 以用箭头指向顶端节点，然后交替地点击RoR和Rol按钮，这样可以来回地变换。照此操作，同时 观察子树的情况，特别是节点37为根的子树的情况。

图9.10中，用虚线三角形标出了子树。注意旋转不会改变每棵子树中节点间的相互关系。整棵 子树作为一个单元整体移动。子树可以比这个例子中所示的三个节点的子树大（有更多的子孙）C 不论一棵子树中有多少个节点，在旋转的过程中它们都作为整体一起移动。

人类与计算机

到现在为止，已经讲解了关于旋转所有需要知道的知识。为了执行旋转，要把箭头指向顶端节 点，然后点击RoR或者RoL按钮。当然，在真正的红-黑树插入算法中，旋转操作由程序控制，不 需要人为地干预。

然而注意，作为人的一种能力，只需要通过观察树，然后对树作适当的旋转就可以平衡任何树。 只要一个节点的左边有很多子孙节点而右边没有这么多节点，就可以向右旋转，反之亦然。

不幸的是，计算机并不善于“只靠观察”这种工作方式。如果计算机能遵守几个简单的规则， 它们就会做得更好。这些规则就是在红■黑方法中提供的，表现形式为颜色码和四个红-黑规则。

插入一个新节点

现在已经有了足够的背景知识，可以学习红-黑树的插入算法如何利用旋转和颜色规则来保持树 的平衡。

插入过程预览

下面将要简要地介绍本章描述插入过程的方法。这里如果不完全明白也不用担心；马上会更详 细地讨论这个过程。

在下面的讨论中，使用X、P和G表示关联的节点。X表示违反规则的节点。（有时X指一个 新插入的节点，有时在父节点和子节点发生红-红颜色冲突时指子节点。）

•X是一个特殊的节点。

•P是X的父。

•G是X的祖父节点（P的父节点）。

在顺着树向下查找插入点时，只要发现一个黑色节点有两个红色的子节点（违反规则2）就执 行一次颜色变换。有时颜色变换会造成红-红颜色冲突（违反规则3）。称红色子节点为X,红色父 节点为P。只用一次或者两次旋转就可以解决这个冲突，旋转次数由X是G的外侧子孙节点还是内 侧子孙节点来决定。执行了颜色变换和旋转之后，继续向下査找插入点，并且插入新的数据项。

在完成新节点X的插入之后，如果P是黑色的，只需要连接这个新的红色节点。如果P是红色 的，则有两种可能性：X是G的外侧子孙节点，或者X是G的内侧子孙节点。需要两次改变节点 颜色（稍后将看到如何改变）。如果X是外侧节点，则执行一次旋转，而如果X是内侧节点，则执

行两次旋转。这能使树达到平衡状态。

现在要深入讨论一些细节问题。讨论分为三个部分，按复杂程度排列，分别是：

1.在下行路途中的颜色变换。

2.插入节点之后的旋转。

3.在向下路途上的旋转。

如果要严格地按照时间的顺序来讨论这三部分，那应该先讨论第三部分再讨论第二部分C但是, 在树底部的旋转比树中间的旋转容易，而且第一部分和第二部分中的操作比第三部分的操作更常 用，所以这里先讨论第二部分，然后再讨论第三部分。

在下行路途中的颜色变换

红-黑树的插入例程的开始时所做的事和普通的二叉搜索树所做的基本上一样：沿着从根朝插入 点位置走，在每一个节点处通过比较节点的关键字相对大小来决定向左走还是向右走。

但是，在红-黑树中，找到插入点更复杂，因为有颜色变换和旋转。在试验3中已经介绍了颜色 变换；现在需要更详细地讨论一下。

假设插入例程顺着树向下执行，在每一个节点处向左走或者向右走，查找插入新节点的位置。 为了不违反颜色规则，在必要的时候需要进行颜色变换。 个红色子节点的黑色节点时，它必须把子节点变为黑色， 点，根总是黑色的）。

颜色变换对红-黑规则有什么影响呢？为了方 便起见，称三角形顶端的节点为P,该节点在颜色 变换前是红色节点c这里称P的左子节点和右子节 点分别为XI和X2。图形如图9.11a所示，

黑色高度不改变

图9.11b显示了颜色变换之后节点的情况。这 次变换没有改变从根向下过P到叶节点或者空节点 的路径上的黑色节点的数目。所有这样的路径都经 过P,然后或者经过XI或者经过X2。在颜色变换 前，只有P是黑色的，所以三角形（由P、XI和 X2组成）在每条这样的路径上增加了一个黑色节点。

在颜色变换之后，P不再是黑色的了，但是XI和X2都是黑色的，所以三角形仍然为通过它的 每条路径贡献一个黑色节点。因此颜色变换不会造成违背规则4。

颜色变换是有用的，因为这使红色的叶节点变为黑色的叶节点，因此在不违背规则3的情况下 连接新的红色节点更容易。

违背规则3

尽管颜色变换不会违背规则4,但是可能会违背规则3（一个节点和它的父节不能都是红色的）。 如果P的父是黑色的，则P由黑色变为红色时不会有任何问题。但是，如果P的父节点是红色的， 那么在P的颜色变化之后，就有两个红色节点相连接了。

这个问题需要在继续向下沿着路径插入新节点之前解决。可以通过旋转修正这个情况，马上就 可以看到。

根的情况

根怎么办呢？记住对根和它的两个子节点做颜色变换时，根和它的子节点一样都是黑色的。这 样的颜色变换避免了违背规则2。这会影响到其他的红-黑规则吗？显然，不会有红色节点连接红色 节点的冲突，因为这使更多的节点变为黑色并且没有红色节点了。因此，不会违背规则3。同时， 因为根和它两个子节点中的一个子节点或另一个子节点在各自的路径上，每条路径上的黑色高度增 加了相同的数量一一都是1。因此，也不会违背规则4。

最后，插入节点

在顺着树的路径向下找到合适的位置之后，如果需要在下行路途中执行颜色变换（和旋转）， 然后就可以插入新的节点，过程和前面那章中描述的普通二叉搜索树一样。但是，这还不是这个问 题的结尾。

插入节点之后的旋转

新数据项的插入可能会违背红■黑规则。因此，在插入之后，必须要检测是否违背规则，并釆取 相应的措施。

记住，正如前面讲过的一样，新插入的称为X的节点总是红色的。X可能插入到相对于P （X 的父节点）和G （P的父节点）不同的位置上，如图9.12所示。

记住如果节点X在P的一侧与P在G的一侧相同，则X就是一个外侧子孙节点。这也就是说， 如果节点X是P的左子节点并且P是G的左子节点（图9.12a）,或者X是P的右子节点并且P是 G的右子节点（图9.12d）时，X是一个外侧子孙节点。相反，如果节点X在P的一侧，而P在G 的另一侧，则X就是一个内侧子孙节点（见图9.12b和图9.12c）。

图9.12显示了红黑树“指向”左或右变化的多样性，这是编写插入例程比较困难的原因之一。

为恢复红-黑规则所釆取的措施由颜色以及X和它亲属的布局所决定。可能很让人奇怪，节点 只以三种方式排列（上面提到过的指向的变换不算在内）。每种可能性都必须由一种不同的方法处 理，以保证红-黑树的正确性以及由此而生成的平衡树。下面将简要地列出这三种可能性，然后分别 在各自的小节中详细讨论它们。图9.13显示了它们的情况。记住X总是红色的。

1.P是黑色的。

2.P是红色的，X是G的一个外侧子孙节点。

3.P是红色的，X是G的一个内侧子孙节点。

读者可能会认为这并没有包括所有的可能情况。先探讨一下这三种情况，然后再回到这个问题 上来。

可能性1： P是黑色的

如果P是黑色的，就什么事也不做。刚刚插入的节点总是红色的。如果它的父节点是黑色的, 则没有红色节点连接红色节点的冲突（规则3）并且也不会增加黑色节点的数目（规则4）。因此, 不会违背颜色规则。这时不需要做其他任何事情。插入完成了。

可能性2: P是红色的，X是G的一个外侧子孙节点

如果P是红色的并且X是一个外侧子孙节点，则需要一次旋转和一些颜色的变化。在RBTree 专题applet中设置这种情况，这样就可以看到正在讨论的情况。具体作法是初始只设有根节点50, 然后插入25, 75和12。在插入12之前需要做一次颜色变换。

现在插入6,它是X,为新节点。图9.14a显示了所得到的树。专题applet ±的信息提示Error: parent and child both red,所以需要做一些改动。

在这种情况下，可以釆取三个步骤使树重新符合红-黑规则，并由此使树平衡。下面就是这三个 步骤：

1.改变X的祖父节点G （本例中是25）的颜色。

2.改变X的父节点P （12）的颜色。

3.以X的祖父节点G （25）为顶旋转，向X （6）上升的方向。在本例中是右旋。

已经讲过，要更改节点颜色，使箭头指向该节点，然后点击R/B按钮。要向右旋，使箭头指向 顶端节点，然后点击RoR按钮。当执行完以上三个步骤之后，专题applet会提示Tree is red/black correct （树是正确的红.黑树。）。树也比以前更趋于平衡了，如图9.14b所示。

在这个例子中，X是一个外侧子孙节点而且是左子节点。X是外侧子孙节点且为右子节点，是 一种与此对称的情况。通过用50, 25, 75, 87, 93创建树（需要时变换节点颜色）来试验这种情 况。通过改变节点75和87的颜色来修正树，然后以75为顶左旋树。树就再次平衡了。

可能性3: P是红色的，X是G的一个内侧子孙节点

如果P是红色的，X是内侧子孙节点，则需要两次旋转和一些颜色的改变。为了能实际地看到 这种情况，使用RBTree专题applet创建节点为50, 25, 75, 12, 18的树。（同样，在插入节点12

之前需要一次颜色变换。）结果如图9.15a所示。

注意节点18是一个内侧子孙节点。它和它的父节点都是红色的，所有又看到提示错误的信息 Error: parent and child both red （错误：子节点和父节点均为红色）。

修正这种情况稍微复杂一些。如果像在情况2中所做的那样，以祖父节点G （25）为顶做右旋， 内侧子孙节点X （18）将会横向移动而不是向上移，所以树比以前更不平衡了。（试着这么做一下， 然后以12为顶旋转它以恢复原来的树型。）因此需要一个不同的解决方法。

当X是内侧子孙节点时，其解决技巧是执行两次旋转而不是一次。第一次把X由内侧子孙节 点变为外侧子孙节点，如图9.15a和图9.15b所示。现在的情况和可能情况1类似了，然后可以应 用相同的旋转，用祖父节点作为顶，和前面所做的一样。结果如图9.15c所示。

图9.15 P是红色的，X是内侧子孙节点

同时还得重新为节点着色。在做任何旋转之前来做这件事情。（这个顺序其实没有什么关系， 但是要是等到旋转完了之后再改变节点的颜色，就很难知道如何称呼它们。）步骤如下：

1.改变X的祖父节点（本例中为25）的颜色。

2.改变X （不是它的父节点；这里X是18）的颜色。

3.用X的父节点P作为顶（不是祖父节点；父节点是12）旋转，向X上升的方向旋转（本例 中是向左旋转）。

4.再以X的祖父节点（25）为顶旋转，向X上升的方向旋转（本例为右旋）。

旋转和改变颜色使树恢复为正确的红-黑树，也（尽可能的）使树平衡。和可能性2一样，它也 有一个类似的情况，即P是G的右子节点而不是左子节点。

其他可能情况怎样？

上面讨论的插入操作可能性真的包含了所有的情况吗？

例如，假设，X有一个兄弟节点S,它是P的另一个子节点。这种情景可能会使插入X所需的 旋转更加复杂。但是如果P是黑色的，插入X没有任何问题（这是情况1）。如果P是红色的，它 的两个子节点必须都是黑色的（避免违背规则3）。它不能有单独的一个黑色的子节点S,因为这样 S和空子节点的黑色高度会不同。但是，已知X是红色的，由此可以得出结论，X不可能有一个兄 弟节点，除非P是红色的。

另一种可能性是P的父节点G有一个子节点U, U是P的兄弟节点和X的叔节点。这种情景 可能也会使任何需要的旋转复杂化。但是，如果P是黑色的，正如看到的一样，插入X时不需要旋 转。所以假设P是红色的。那么U必须也是红色的；否则，从G到P的黑色高度就和从G到U的 黑色髙度不同了。但是有两个红色子节点的黑色父节点在沿着路径向下的时候颜色变换了，所以这 种情况也是不存在的。

因此，上面讨论的三种可能性是全部可能存在的情况（除了这样的情况，即在可能性2和可能 性3中，X可能是右子节点或者左子节点，以及G可能是右子节点或者左子节点。）

颜色变换实现了什么

假设执行旋转和适当颜色改变造成了在树的上方出现其他红-黑规则违规情况。可以想像这就必 须沿着树一直向上来做各种操作。执行旋转和颜色变化；直到消除所有违规情况。

幸运的是，这种情况不会发生。在下行的路途中使用颜色变换已经消除了旋转造成树的上方任 何规则的违规情况。这保证了一次或两次旋转可以使整棵树再次成为正确的红■黑树。它的证明已经 超出了本书的范围，但是这种证明是可行的。

在下行路途中的颜色变换使红-黑树的插入效率比其他平衡树，例如AVL树的插入效率更高。 颜色变换保证了在下行的路途中仅在树上行走了一遍。

在下行路途中的旋转

现在来讨论插入一个节点时三种操作中的最后一种：在下行路途中査找插入点时所做的旋转。 前面已经讲过，尽管最后讨论这个操作，但是它实际上发生在节点插入之前。直到现在才讨论它只 是因为解释为刚刚插入的节点所作的旋转比解释树中间的节点的旋转容易。

在插入的过程中讨论颜色变换时，已经讲过颜色变换可能会造成对规则3 （父节点和子节点不 能都是红色的）的违犯，还讲过旋转可以纠正这种违规的情况。

在向下的路径上有两种旋转的可能性，分别对应前面描述的在插入阶段的可能性2和可能性3O 违背规则的节点可能是一个外侧子孙节点，也可能是一个内侧子孙节点。（对应可能性1的情况， 不需要做任何操作。）

外侧子孙节点

首先来看一个例子，例子中违背规则的节点是一个外侧子孙节点。“违背规则的节点”是指在 造成红.红冲突的父.子节点对中的子节点。

从节点50开始建一棵新树，插入如下节点：25, 75, 12, 37, 6和18。在插入12和6时需要

做颜色变换。

现在要插入值为3的节点。注意，必须对节点12以及它的子节点6和18做颜色变换。点击Flip 按钮。变换执行完毕，但是现在信息提示Error: parent and child are both red （错误：父节点和子节 点都是红色的），这是指25和它的子节点12。此时生成的树如图9.16a所示。

图9.16下行路途中的外侧子孙节点

纠正这种违规的过程和前面描述的插后操作中对外侧子孙节点的类似。必须要执行两次颜色改 变和一次旋转。因此这里用前面讨论插入节点时的相同的术语，称刚作了颜色变换三角形的顶端节 点（本例中是12）为X。这似乎有点古怪，因为以前是用X表示要插入的节点，但这里它甚至不 是一个叶节点。然而，这些在下行路途中的旋转在树中的任何位置都可能发生。

X的父节点是P （此例中为25）, X的祖父节点，即P的父节点，是G （50）o遵守和前面讨论 可能情况2时相同的那组规则：

1-改变X的祖父节点G （本例中是50）的颜色。忽略根必须是黑色的提示信息。

2.改变X的父节点P （25）的颜色。

3.以X的祖父节点G （50）为顶旋转，向X上升的方向旋转（这里是右旋）。

突然之间，树就平衡了！同时树也令人满意地变成对称的了。这好象是发生了奇迹，但这只是 遵循颜色规则的结果。

现在值为3的节点可以按通常的方法插入到树中。因为要连接到的节点（6）是黑色的，所以 插入一点都不复杂。只需要一次颜色变换（在50处）。图9.16b显示了插入3之后的树。

内侧子孙节点

如果在下行路途中岀现红-红冲突时，X是内侧子孙节点，则需要两次旋转来改正它。这种情况 和在前面讲过的插后操作可能性3即新插入节点X为内侧子孙节点的情况类似,，在RBTree专题 applet中点击Start创建一棵树，根为50,插入25, 75, 12, 37, 31和43。在插入12和31之前需 要颜色变换。

现在试着插入一个新的节点，值为28。提醒自己需要颜色变换（节点37处）。但当执行颜色变 换时，37和25都是红色的，出现提示信息Error: parent and child are both red （错误:父节点和子节 点都是红色的）。不要再点击Ins按钮。

此时G为50, P为25, X是37,如图9.17a所示。

图9.17下行路途中的内侧子孙节点

为了解决红-红冲突，必须要做和可能性3相同的两次颜色改变和两次旋转:

1.改变G （50,忽略根必须是黑色的提示信息）的颜色。

2.改变X （37）的颜色。

3.以P （25）为顶旋转，向X上升的方向旋转（这里是左旋）。结果如图9.17b所示。

4.以G （50）为顶旋转，向X上升的方向旋转（这里是右旋）。

现在可以插入节点28 了。当插入它颜色变换把25和50都变为黑色。结果如图9.17c所示。 由此可以得出结论，在插入的过程中，保持树的红-黑正确性，因此可以取得树的平衡。

删除

可以回忆一下，在普通的二叉搜索树中编写删除操作的代码比编写插入操作的代码要难得多。 在红•黑树中也是这样的，并且除此之外，可以想像得到删除过程由于需要在节点删除之后恢复树的 红-黑正确性，变得更复杂。

实际上，删除过程太复杂了，很多程序员都用不同的方法来回避它。一种方法（和在普通的二 叉树中一样）就是为删除的节点做个标记而不实际地删除它。任何找到该节点的查找例程都知道不 用报告已找到该节点。很多情况下都应用这种方法，特别是在不经常执行删除操作时。不管怎么说, 这里将不讨论删除过程。如果想要继续了解这方面的知识，可以参看附录B “进一步阅读气

红■黑树的效率

和一般的二叉搜索树类似，红-黑树的査找、插入和删除的时间复杂度为O（log2N）o在红■黑树 中的査找时间和在普通二叉搜索树中的査找时间应该几乎完全一样，因为在査找的过程中并没有应 用红.黑树的特征。额外的开销只是每一个节点的存储空间都稍微增加了一点，来存储红■黑的颜色 （一个 boolean 变量）。

更为特别的，根据Sedgwick的说法（参见附录B）,实际上在红•黑树中的查找大约需要logzN 次比较，并且也说明了査找不可能需要超过2*log2N次比较。

插入和删除的时间要增加一个常数因子，因为不得不在下行的路径上和插入点执行颜色变换和 旋转。平均起来，一次插入大约需要一次旋转。因此，插入的时间复杂度还是0（log2N），但是比在 普通的二叉搜索树中要慢。

因为在大多数应用中，査找的数次比插入和删除的次数多，所以应用红■黑树取代普通的二叉搜 索树总体上不会增加太多的时间开销。当然，红•黑树的优点是对有序数据的操作不会慢到0（N）的 时间复杂度。

红■黑树的实现

如果编写红.黑树的插入例程，只需要编写代码执行前面所描述的操作。前面已经讲过，显示和 描述这样的代码不在本书的范围之内。但是下面还是有一些需要考虑的问题。

需要在Node类中增加一个标志红-黑的数据字段（可以是boolean类型）。

可以修改第8章中tree.java程序（清单8.1）的插入例程。在向下到插入点的路径上，检査当 前节点是否为黑色，以及它的两个子节点是否都是红色的。如果是这样，改变这三个数据项的颜色 （除非父节点是根，根总是保持黑色）。

在颜色变换之后，检查确实没有违背规则3。如果有，执行适当的旋转：对外侧子孙节点旋转 一次，对内侧子孙节点旋转两次。

当到达一个叶节点时，像在tree.java中一样插入新节点，保证这个节点是红色的。再次检查是 否有红-红的冲突，然后执行需要的旋转操作。

读者也许会觉得比较奇怪，程序中不需要跟踪树不同路径的黑色高度（虽然在调试的过程中可 能需要査看它）。只需要检查是否违背规则3,即一个红色父节点有一个红色子节点，若有,当时就 可以解决掉（检査黑色高度（规则4）则不同，它需要更复杂的记录）。

如果执行前面描述的颜色变换、颜色改变以及旋转，节点的黑色高度应当能自动调整，并且树 应该保持平衡° RBTree专题applet提示黑色高度有错，只是因为没有强迫用户按正确的步骤完成插 入算法。

其他平衡树

AVL树是最早的一种平衡树。它以发明者的名字命名：Adelson-Velskii和Landis。在AVL树 中每个节点存储一个额外的数据：它的左子树和右子树的高度差。这个差值不会大于lo这也就是 说，节点的左子树的高度和右子树的高度相差不会大于一层。

插入之后，检查新节点插入点所在的最低子树的根。如果它的子节点的高度相差大于1，执行 一次或者两次旋转使它们的高度相等。然后算法向上移动，检査上面的节点，必要时均衡高度。这 个检测检査所有路径一直向上，直到根为止。

AVL树査找的时间复杂度为O（logN）,因为树一定是平衡的。但是，由于插入（或删除）一个 节点时需要扫描两趟树，一次向下査找插入点，一次向上平衡树，AVL树不如红-黑树效率高，也 不如红■黑树常用。

另一个重要的平衡树是多叉树，每个节点可以有两个以上的子节点。本书将介绍多叉树的一种， 在下一章中介绍2・3・4树。关于多路树的一个问题是每个节点都必须比二叉树的大，因为它需要保 存它的每个子节点的引用。

小结

•保持二叉搜索树的平衡是非常重要的，这样可以使找到给定节点所必需的时间尽可能短。

•插入有序的数据将创建最不平衡的树，它査找的时间复杂度为0（N）。

•在红■黑平衡的方法中，每个节点都有一个新的特征：它的颜色不是红的就是黑的。

•一组称为红-黑规则的规则，详细说明了允许排列不同颜色节点的方法。

•当插入（或删除）一个节点时应用这些规则。

•一次颜色变换把一个黑色节点和它的两个红色子节点改成一个红色节点和两个黑色子节 点0

•在一次旋转中，指定一个节点为顶端节点。

•右旋把顶端节点移到它的右子节点的位置，并把顶端节点的左子节点移到顶端节点的位 置。

•左旋把顶端节点移到它的左子节点的位置，并把顶端节点的右子节点移到顶端节点的位 置。

•当顺着树向下查找新节点的插入位置时，应用颜色喳换，并且有时应用旋转。颜色变换通 过简单的方法，就使树在插入后恢复成正确的红一黑树。

•新节点插入之后，再次检查红-红冲突。如果发现有违背红•黑规则的现象，执行适当的旋 转使树恢复红-黑正确性。

•这些调整使树成为平衡的，或者至少大致平衡。

•在二叉树中加入红•黑平衡对平均执行效率只有很小的负面影响，然而却避免了对有序的 数据操作的最坏的性能。