基于红黑树的操作与检验

唐 松，格桑多吉，高定国

（西藏大学工学院，拉萨850000）

红黑树属于自平衡二叉查找树，是二叉2-3-4树和对称B-树，是在计算机科学技术中使用的一种数据结构，其典型用途是关联数组的实现。红黑树的每个节点都有颜色属性，颜色为红色或黑色。除了二叉查找树的一般要求以外，对于任何有效的红黑树增加了如下的要求：

性质1：节点颜色为红色或黑色。

性质2：根节点为黑色。

性质3：每个叶节点（NIL）为黑色。

性质4：每个红色节点的两个子节点皆为黑色(从根到每个叶子所有路径上不能有两个连续红色节点)。

性质5：从任一节点到其每个叶子的所有路径都含有相等数目的黑色节点。

这些约束规定了红黑树的关键性质:从根到叶子的最长可能路径少于或等于最短可能路径的两倍长，且这棵树大致上是平衡的。因为插入、删除和查找某个值的操作的最坏情况，其时间都要求与树高度成比例，这个高度的理论上限不同于普通的二叉查找树，且允许红黑树在最坏情况下都是高效的。

1 优点和用途

虽然hash表查找非常迅速，但随着数据种类变多，hash表长会变得更长且冲突也会增多，那么如何能实现数据量无论多大，查找依然高性能？一般情况下，树是很好的一种数据结构，用于插入、查找和删除等操作都很高效，但在很坏的情况下，操作很费时间，性能难以保证。向树中插入时，按一定规则调整，使其达到规则，从而提高其整体与局部的查找效率。

红黑树复杂，但其操作有良好的最坏情况运行时间，且在实践中高效：可以在O(log n)时间内插入、查找和删除（log n中的n是树中元素的数目）。它的统计性能优于平衡二叉树(AVL-树)，所以红黑树应用很广，如字典的实现、关联数组上，且内存使用率较高。在C++STL中，不少部分(目前包括set、multiset、map、multimap)应用了红黑树的变体(SGI STL中的红黑树的修改提供了更好的性能、对set操作的支持)。

2 红黑树的构建、操作

2.1 红黑树的构建

2.1.1 旋转

图1 旋转

左旋：在某结点x上做左旋操作时，先假设其右孩子y不是NIL[T]，x可为树内任意右孩子而非NIL[T]结点。左旋以x至y间的链为“支轴”进行，使y变为该孩子树新的根，y的左孩子β变为pivot的右孩子。

右旋：可由左旋类推之。

树旋转后，保持不变的唯有原树的搜索性质，而不能保持原树的红黑性质，红黑树的数据插入、删除后可用旋转和重新涂色来恢复树的红黑性质。

2.1.2 插入和调整

调用插入操作时，为了维护红黑树的五个性质，需要进行左旋、右旋相应操作，因为插入算法中将z涂为红色可能违背红黑性质的某一条，所以要进行相应的调整和颜色重涂，直至满足红黑树的全部性质。

2.2 红黑树的操作

2.2.1 结点的插入

插入分为下面两类情况，相应的流程图如图2和图3。

1）情况1（如图2）：z的叔叔y为红色。(a)情况，即z是右孩子,因p[p[z]（]c）为黑色，所以将p[z]、y都涂成黑色，这就解决了z、p[z]皆为红色的问题，将p[p[z]]涂为红色，则维持了性质5。(b)情况同理分析。

图2 结点的插入情况1

2）插入情况2（如图3）：z的叔叔y为黑色，且z为右孩子。

插入情况3（如图3）：z的叔叔y为黑色，且z为左孩子。

对于情况2（z是它父亲的右孩子），为了维持红黑树性质，左旋变成情况3，此时z为左孩子，因z、p[z]皆为黑色，故不违背红黑树性质（注：情况3中，z的叔叔y为黑色，否则此种情况就变为情况1）。

情况2、情况3都违背性质4（一个红结点的两个儿子都为黑色）。因此，情况2-＞左旋后-＞情况3，这时情况3同样违背性质4，所以情况3-＞右旋，同时B变成黑色，C变成红色，得到图3的最后那一部分。（注：情况2、3都只违背性质4，不违背其他性质。）

图3 结点的插入情况2

对以上三种情况，首先将待插入结点涂成红色，接着按照二叉树的方式进行插入操作，因此元素的搜索性质不会改变。为了保证红黑树性质在插入后依然保持，上面代码调用了一个调整的辅助程序，对结点进行重新涂色并旋转。若插入的结点是根结点，会破坏性质2，若插入结点的父结点为红色，则性质4会被破坏。总而言之，插入一个红色结点只会破坏性质2或性质4。

(a)结点z为红色。

(b)若p[z]是根，则p[z]为黑色。

(c)若有红黑树的性质被破坏，则最多有一个被破坏，不是性质2就是性质4。若违反性质2，则发生原因是z为根且为红色。若违反性质4，则原因为z和p[z]皆为红色，p[p[z]]必然为黑色。

2.2.2 结点的删除

1)若待删除结点不在红黑树中，则输出“not found!”提示。

2)若待删除结点在红黑树中，则删除分为四种情形，相应的操作如图4。

图4 结点的删除

注：若待删除结点y有左孩子，那么x是y的左孩子，否则为右孩子。

情况1：x的兄弟w为红色。同时改变w、p[z]的颜色，对p[x]左旋一次，保持了红黑树全部性质。x的新兄弟new w为旋转之前w的左孩子，且为黑色。所以，情况1转变成情况2或3、4。

情况2：x的兄弟w为黑色，且w的两个孩子都为黑色。因为w也为黑色，所以x和w中必须去掉一个黑色，经颜色重涂，w变为红色。p[x]为新结点new x，赋给x，即操作x＜-p[x]。

情况3：x的兄弟w为黑色，w的左孩子为红色，w的右孩子为黑色。将w和其左孩子left[w]的颜色都改变（即它们的颜色交换——上图的D、C颜色互换），并对w进行右旋操作，从而保持了红黑树性质。现在x的新兄弟new w是有红色右孩子的黑结点，从而把情况3转变为情况4.

情况4：x的兄弟w为黑色，且w的右孩子为红色。改变w颜色，并旋转p[x]一次，可以去掉x的额外的黑色，变x为单一黑色，这些并没有破坏红黑树性质。将x置为根（new x=root[T]），结束程序循环。

若从被删除结点的颜色分析，可以得到：

结论1：若被删除的结点为红色,则结点被删除后,红黑树性质仍保持,原因如下:

(a)树中各结点的黑高都没变。

(b)不存在两个相邻红色结点。

(c)因为若该节点为红色,就不可能为根,所以根仍然为黑色。

结论2：若被删除的结点为黑色，则会产生三个问题。（待删除结点是y，若y有一个不是NIL的孩子，则x是y的唯一孩子；若y没有孩子，则x为NIL，赋y的父节点值给x的父节点(原来是y)。）

(a)若y原来为根，而y的一个红色孩子变为新的根，这就违背了性质2。

(b)若x和p[y](现在也为p[x])都为红色，就违背了性质4。

(c)删除y将导致之前包含y的任何路径上黑结点个数少1。因此，y的一个祖先破坏了性质5，应对的一个方法是将x视为还有另外的一重黑色，即是说，若将任意包含x的路径上的黑结点个数加1，则此假设下性质5成立。当删除黑节点y时，将其黑色“下推”至y的子节点。现在就有这样的问题，x可能既不是红，也不是黑，违背了性质1。x为双重黑色或红黑，这就分别给包含x的路径上黑结点的个数贡献2个或1个。x的颜色属性仍为红(若x是红黑的)或者黑(若x为双重黑色)。换言之，一个结点额外的黑色体现在x指向它，而不是它的颜色属性。

3 红黑树的检验

利用中序遍历函数，将构建或是操作（插入、删除）后经过调整的红黑树输出，能直观地看出构建或是操作（插入、删除）后经过调整的红黑树的正确与否，若输出的数列是升序，那么正确（调整后结点颜色的正确性基于算法的正确性），反之错误，因为树的中序遍历按照结点进行升序排列。

4 流程图和运行结果

流程图和运行结果如图5和图6所示。

图5 流程图

5 小结

红黑树为树的构建、插入、查找和删除操作的时间提供了最佳可能的最坏情况保证，这不仅使它们在对时间敏感的应用如实时应用中有价值，而且使它们在最坏情况担保的其他数据结构中拥有作为建造板块的价值，如计算几何中使用的很多数据结构皆可基于红黑树。在函数式编程中，红黑树也特别有用，它们是最常用的持久数据结构之一，用来构造集合和关联数组，且在突变之后仍能保持以前的版本。除了O(log n)的时间，红黑树持久版本对每次的插入或删除都要O(log n)的空间。

图6 运行结果

因此，深入研究红黑树的算法，在理解的基础上实现，并用中序遍历输出这种简易且可靠的方法检验，对红黑树的应用方面有很重要的参考价值。

[1]THOMAS H C,LEISERSON C E.Introduction to algorithms[M].北京:机械工业出版社,2006.

[2]Kenneth A·Reek.C和指针 POINTERS ON C[M].北京：人民邮电出版社，2008.

[3]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2001.