数据结构之红黑树见解

红黑树是计算机科学内比较常用的一种数据结构，它使得对数据的搜索，插入和删除操作都能保持在O(lgn)的时间复杂度。然而，相比于一般的数据结构，红黑树的实现的难度有所增加。网络上关于红黑树的实现资料汗牛充栋，但是乏于系统介绍红黑树实现的资料。本文通过一个自己实现的红黑树数据结构以及必要的搜索，插入和删除操作算法，为大家更系统地剖析红黑树数据结构的实现。

对于大部分数据结构，一般都会使用抽象数据类型的方式实现，C++提供的模板机制可以做到数据结构与具体数据类型无关，就像STL实现的那样。不过本文并非去实现STL中的红黑树，更重要的是透过红黑树的实现学习相关的算法和思想。当然，我们还是会借鉴STL中关于红黑树实现部分有价值内容。

一、基本概念

在具体实现红黑树之前，必须弄清它的基本含义。红黑树本质上是一颗二叉搜索树，它满足二叉搜索树的基本性质——即树中的任何节点的值大于它的左子节点，且

按照二叉搜索树组织数据，使得对元素的查找非常快捷。比如图1中的二叉搜索树，如果查询值为48的节点，只需要遍历4个节点即可完成。理论上，一颗平衡的二叉搜索树的任意节点平均查找效率为树的高度h，即O(lgn)。但是如果二叉搜索树的失去平衡（元素全在一侧），搜索效率就退化为O(n)，因此二叉搜索树的平衡是搜索效率的关键所在。为了维护树的平衡性，数据结构内出现了各种各样的树，比如AVL树通过维持任何节点的左右子树的高度差不大于1保持树的平衡，而红黑树使用颜色的概念维持树的平衡，使二叉搜索树的左右子树的高度差保持在固定的范围。相比于其他二叉搜索树树，红黑树对二叉搜索树的平衡性维持有着自身的优势。

顾名思义，红黑树的节点是有颜色概念的，即非红即黑。通过颜色的约束，红黑树维持着二叉搜索树的平衡性。一颗红黑树必须满足以下几点条件：

规则1、根节点必须是黑色。

规则2、任意从根到叶子的路径不包含连续的红色节点。

规则3、任意从根到叶子的路径的黑色节点总数相同。

如图2所示，为一颗合法的红黑树，可以发现红黑树在维持二叉搜索树的基本性质的前提下，并满足了红黑树的颜色条件，整体上保持了二叉搜索树的平衡性。（构造如下红黑树的数据序列为：（50，35，78，27，56，90，45，40，48），读者可以自行验证。）

小于它的右子节点。

二、数据结构设计

和一般的数据结构设计类似，我们用抽象数据类型表示红黑树的节点，使用指针保存节点之间的相互关系。

作为红黑树节点，其基本属性有：节点的颜色、左子节点指针、右子节点指针、父节点指针、节点的值。

在红黑树类中，定义了树根（root）和节点数（count），其中还记录红黑树在插入删除操作时执行的旋转次数rotate_times。其中核心操作有插入操作（insert），搜索操作（find），删除操作（remove），递减操作（prev）——寻找比当前节点较小的节点，递增操作（next）——寻找比当前节点较大的节点，最大值（maximum）和最小值（minimum）操作等。其中验证操作（__ validate）通过递归操作红黑树，验证红黑树的三个基本颜色约束，用于操纵红黑树后验证红黑树是否保持平衡。

由于插入和删除操作是红黑树的关键所在，下边重点介绍这两个操作。其他的操作一般通过对树进行递归操作都可以轻松的完成，这里不再赘述。

三、红黑树的插入操作

红黑树的插入操作和查询操作有些类似，它按照二分搜索的方式递归寻找插入点。不过这里需要考虑边界条件——当树为空时需要特殊处理（这里未采用STL对树根节点实现的特殊技巧）。如果插入第一个节点，我们直接用树根记录这个节点，并设置为黑色，否则作递归查找插入（__insert操作）。

默认插入的节点颜色都是红色，因为插入黑色节点会破坏根路径上的黑色节点总数，但即使如此，也会出现连续红色节点的情况。因此在一般的插入操作之后，出现红黑树约束条件不满足的情况（称为失去平衡）时，就必须要根据当前的红黑树的情况做相应的调整（__rebalance操作）。和AVL树的平衡调整通过旋转操作的实现类似，红黑树的调整操作一般都是通过旋转结合节点的变色操作来完成的。

红黑树插入节点操作产生的不平衡来源于当前插入点和父节点的颜色冲突导致的（都是红色，违反规则2）。

四、红黑树的删除操作

相比于插入操作，红黑树的删除操作显得更加复杂。很多资料都没有将红黑树的删除解释清楚，清华的数据结构教材对红黑树删除的描述也十分混乱，《STL源码剖析》中侯sir对红黑树的删除更是闭口不谈。这里参考了STL对红黑树删除操作的实现方式，并做了适当的修改（红黑树使用哨兵节点表示空节点，而这里使用空指针的方式，因此要杜绝空指针的引用问题）。

由于红黑树就是二叉搜索树，因此节点的删除方式和二叉搜索树相同。不过红黑树删除操作的难点不在于节点的删除，而在于删除节点后的调整操作。因此红黑树的删除操作分为两步，首先确定被删除节点的位置，然后调整红黑树的平衡性。

先考虑删除节点的位置，如果待删除节点拥有唯一子节点或没有子节点，则将该节点删除，并将其子节点（或空节点）代替自身的位置。如果待删除节点有两个子节点，则不能将该节点直接删除。而是从其右子树中选取最小值节点（或左子树的最大值节点）作为删除节点（该节点一定没有两个子节点了，否则还能取更小的值）。当然在删除被选取的节点之前，需要将被选取的节点的数据拷贝到原本需要删除的节点中。选定删除节点位置的情况如图11所示，这和二叉搜索树的节点删除完全相同。

以上是我个人的学习心得，能力有限，如有错误和建议，恳请批评指正！