红黑树学习参考资料集合

红黑树(red-black tree)算法，附 AVL 树的比较

linux内核中的用户态地址空间管理使用了红黑树(red-black tree)这种数据结构，我想一定有许多人在这

种数据结构上感到困惑，我也曾经为此查阅了许多资料以便了解红黑树的原理。最近我在一个外国网站上

看到一篇讲解红黑树的文章，觉得相当不错，不敢独享，于是翻译成中文供所有内核版的弟兄们参考。由

于本人水平有限，难免有出错之处，欢迎大家指正。

原文网址：

http://sage.mc.yu.edu/kbeen/teaching/algorithms/resources/red-black-tree.html

红黑树的定义

正如在CLRS中定义的那样（译者： CLRS指的是一本著名的算法书Introduction to Algorithms，中文

名应该叫算法导论，CLRS是该书作者Cormen, Leiserson, Rivest and Stein的首字母缩写），一棵红

黑树是指一棵满足下述性质的二叉搜索树（BST, binary search tree）：

数据项只能存储在内部结点中（internal node）。我们所指的"叶结点"在其父结点中可能仅仅用一个NULL

指针表示，但是将它也看作一个实际的结点有助于描述红黑树的插入与删除算法，叶结点一律为黑色。

定理：一棵拥有n个内部结点的红黑树的树高h<=2log(n+1)

(译者：我认为原文中的有关上述定理的证明是错误的，下面的证明方法是参考CLRS中的证明写出的。）

证明：首先定义一颗红黑树的黑高度Bh为：从这颗红黑树的根结点（但不包括这个根结点）到叶结点的路

径上包含的黑色结点（注意，包括叶结点）数量。另外规定叶结点的黑高度为 0。

下面我们首先证明一颗有n个内部结点的红黑树满足n>=2^Bh-1。这可以用数学归纳法证明，施归纳于

下面我们完成剩余部分的证明，记红黑树树高为h。我们先证明Bh>=h/2。在任何一条从根结点到叶结点

的路径上（不包括根结点，但包括叶结点），假设其结点数量为m，注意其包含的黑色结点数量即为Bh。

当m为偶数时，根据性质 5 可以看出每一对儿相邻的结点至多有一个红色结点，所以有Bh>=m/2；而当

m为奇数时，这条路径上除去叶结点后有偶数个结点，于是这些结点中的黑色结点数B'满足B'>=(m-1)/2，

将该不等式前后加 1 得出Bh>=(m+1)/2，可以进一步得出Bh>m/2，综合m为偶数的情况可以得出

最终得到h<=2log(n+1)。证明完毕。

本文余下的内容将阐释如何在不破坏红黑树性质的前提下进行结点的插入与删除，以及为什么插入与删除

性质 4（不能有两个相邻的红色结点）。

如果新插入的结点是根结点的话（这意味着在插入前该红黑树是空的），我们仅仅将这个结点的颜色改为

黑色，插入操作就完成了。

如果性质 4 遭到了破坏，这一定是由于新插入结点的父结点也是红色造成的。由于红黑树的根结点必须是

黑色的，因此新插入的结点一定会存在一个祖父结点，并且根据性质 4 这个祖父结点必然是黑色的。此时，

由新插入结点的祖父结点为根的子树的结构一共有四种可能性（译者，前面这句话我没有看明白原文，我

是用我的理解写出来的，如果有误请指正。），如下面的图解所示。在Okasaki插入方法中，每一种可能

出现的子树都被转换为图解正中间的那种子树形式。

首先，请注意在变换的过程中<AxByCzD>的顺序保持不变。

另外，注意该变换不会改变从这颗子树的父结点到这颗子树中任何一个叶结点的路径中黑色结点的数量（当

然前提是这颗子树有父结点）。我们再一次遇到了这样的情形：即该红黑树只有可能违反性质 2（如果y

是根结点）或性质 4（如果y的父结点是红色的），但这次变换带来了一个好处，即我们现在距离红黑树的

根结点靠近了两步。我们可以重复这种操作直到：或者y的父结点为黑色，在这种情况下插入操作完成；或

者y成为根结点，在此情况下我们将y染为黑色后插入操作完成。（将根结点染为黑色会对每条从根结点到

叶结点的路径增加相同数量的黑色结点，因此如果在染色操作之前性质 5 没有遭到破坏那么操作之后也不

会。）

很显然，在旋转操作中<AxByC>的顺序保持不变。因此，如果操作前该树是一颗二叉搜索树，而且结构

调整时只使用了旋转操作，那么调整后该树仍然是一颗二叉搜索树。在本文的余下部分，我们将仅仅使用

旋转操作对树进行调整，因此我们无须再言明关于如何保持树中元素的正确排序问题。

在下面的图解中，Okasaki插入方法中的变换操作被表示为一个或者两个旋转操作。

CLRS中给出了一种比Okasaki插入方法更复杂但效率稍高的插入方法。它的时间复杂度仍然是O(log n)，

但在大O中的常数要更小一些。

的那个子结点。）让我们先考虑叔叔结点为黑色的情况。根据每个红色结点是其父结点的左子结点还是右

在这里我们感兴趣的是上面图解中的方法与Okasaki方法的比较。它们有两点不同。第一点是关于如何对

最终的子树（图解中间的那个子树）进行染色的。在Okasaki方法中，这颗子树的根结点y被染成红色而它

的子结点被染成黑色，然而在CLRS方法中y被染成了黑色而它的子结点被染成了红色。将y染成黑色意味

着红黑树性质 4（不能存在两个相邻的红色结点）不会在y这一点遭到破坏，因此对树的调整不需要向根结

点的方向继续进行下去。在此情况下，CLRS插入方法最多需要进行两次旋转操作即可完成插入。