0%

数据结构与算法（17）红黑树

发表于 更新于 分类于 本文字数： 13k
红黑树是针对AVL树的不足的改进，通过为节点指定颜色，并巧妙地动态调整，红黑树可保证：在每次插入或删除操作之后的重平衡过程中，全树拓扑结构的更新仅涉及常数个节点。

1.概述

1.1.动机

平衡二叉搜索树的形式多样，如伸展树实现简便，无需修改节点结构、分摊复杂度低，但最坏情况下的单次操作需要$\Omega(n)$时间；AVL树尽管可以保证最坏情况下的单次操作速度，但需在节点中嵌入平衡因子等标识，且删除之后的重平衡可能需做多达$\Omega(\log n)$次旋转，从而频繁地导致全树整体拓扑结构的大幅度变化。

红黑树即是针对后一不足的改进，通过为节点指定颜色，并巧妙地动态调整，红黑树可保证：在每次插入或删除操作之后的重平衡过程中，全树拓扑结构的更新仅涉及常数个节点。尽管最怀情况下需对多达$\Omega(\log n)$个节点重染色，但就分摊意义为言仅为$O(1)$个。

为此需要在AVL树“适度平衡”标准的基础上，进一步放宽条件，红黑树所采用的“适度平度”标准可大致表述为：任一节点左、右子树的高度，相差不得超过两倍。

不论是线性的向量、列表、栈或队列，也无论半线性的树结构 以及非线性的图结构，它们大多呈现这么样一种特征：每当经过一次动态的操作 使得其中的逻辑结构发生变化之后，它都会随即完全的转入新的状态 同时将此前的状态完全的遗忘掉，这类结构也因此称作ephemeral data structure，也就是说它们都是随时变化的，每一个状态只会存在于某一个瞬间。

然而在实际应用中往往可能会有更高的要求，比如若将数据结构比作是人，那么它的每一个瞬间状态都相当于人一生中某一时刻的快照，我们或许会对他的历史档案感兴趣，并希望能够任意调阅甚至修改某个历史时刻的档案。因此无论静态还是动态操作，除了指定目标关键码，还需要同时指定一个版本号，用以说明我们是在这个数据结构的哪一份历史档案中去查找特定对象。如果一个数据结构能够支持这种类型的需求，就称作是一致性结构，或持久性结构（persistent structures）。

乍看起来任意数据结构的持久化都不是那么困难的一件事，比如一种直接了当的方法就是为数据结构的每一个所需的版本都独立的保存一份快照，同时将所有版本的入口组成一个搜索结构。这里我们针对一棵真实的BBST记录了它整个生命期内的5个版本。这样 一旦指定了版本号，我们就可以转入对应的快照，并按照常规搜索方法在其中定位需要操作的元素。

从单次访问的效率而言这个结构还可以接受，如果将整个历史快照的数目记作h，那么每次我们只需$O(\log h)$的时间便可确定版本档案的入口，接下来再花费$O(\log n)$的时间，在这份档案中进行定位和操作，即单次操作需$O(\log h+\log n)$时间。然而就空间而言这种方法是断乎不可接受的，在这样的一组历史快照中每一个元素都可能会被保存多份，渐近的来说n个元素中的每一个都有可能在这组档案中被保存多达h份，这就意味着空间复杂度将伴随着h成线性的速度增长。空间复杂度自然也构成了时间复杂度的一个下限，因此在整个历史过程中为了生成和记录所有的快照，累计所花费的时间也会多达$O(h*n)$这样一个规模，分摊下来为了生成每一组快照都大致需要花费线性的时间来创建一个完整的副本。

那么我们可否就此做一改进呢，比如除了所有元素各自所占用的空间，是否能够将每一个版本所消耗的均摊空间量控制在$O(\ log n)$的范围内呢，即将复杂度控制在$O(n+h\log n)$内呢？答案是可以，为此我们需要*利用同一数据结构相邻版本之间的关联性。

对于每一组相邻的历史快照而言，后者都是在前者的基础上做过相对少量的更新而得的，即绝大部分的数据对象在二者之中都是相同的，二者的差异只是非常非常小的一部分。因此可以改用这样一种策略：大量的元素都作共享，只有发生变化的少量的数据元素才需要进行更新。

实际上只要实现方法得当，完全可以将相邻版本之间的差异量控制在$O(\log n)$的范围。比如对于BBST而言 下图就是一种可行的实现方法：每一条红线都对应于一个共享，蓝色的虚线所指示的是在相邻版本之间的更新量，也是我们不得不花费空间来进行存储的量，而这个量可以控制在极低的水平。在《计算几何》课程中会介绍这类高级结构。

进一步地，我们能否将BBST前后版本的空间差异控制在$O(1)$的范围呢？这样整体的空间复杂度将进一步优化至$O(n+h)$ 而不是$O(h*\log n)$。答案也是可以的。

为此所应具备的一项必要条件是非常好理解的，即就BBST的树形拓扑结构而言，相邻版本之间的差异本身不能超过常数。然而很遗憾绝大多数的BBST，包括AVL树都不能保证这一点。所谓的拓扑结构差异无非是来自自调整过程中的旋转操作，每一次局部的旋转都意味着在结构上引入常数的差异。因此反过来如果需要保证前后版本在拓扑结构上的差异不超过常数，也就意味着在从前一版本转入后一版本的过程中所执行的旋转操作不得超过常数次。

反观AVL树的两个动态操作，插入操作是满足这一条的，每次插入之后一旦经过一次旋转，局部乃至全树的高度都会复原；然而删除操作却不满足，从AVL树中删除一个节点之后有可能自底而上逐层引发多达$O(\log n)$次的旋转，从而导致树形拓扑结构的剧烈变化。

因此为了使得上述的构思能够兑现就需要这样一种BBST，它的任何动态操作，无论插入还是删除对树形拓扑结构的影响都能控制在常数的范围之内，而红黑树（red-black tree）正是具有这一特性的一个变种。

1.2.结构

为便于对红黑树的理解、实现与分析，不妨按照此前介绍的B-树的做法，统一地引入n+1个外部节点NULL，以保证原树中每一节点的左、右孩子均非空，如此可将二叉树扩展为真二叉树。

由红、黑两色节点组成的二叉搜索树若满足一下条件，即为红黑树（red-black tree）：

（1）树根始终为黑色；

（2）外部节点均为黑色；

（3）其余节点若为红色，则其孩子节点必为黑色；

（4）从任一外部节点到根节点的沿途，黑节点的数目相等。

其中，条件（1）和（2）意味着红节点均为内部节点，且其父亲点及左、右孩子必然存在。条件（3）意味着红节点之父必为黑色，因此树中任一通路都不含相邻的红节点。可见在从根节点通往任一节点的沿途，黑节点都不少于红节点，除去根节点本身，沿途所经黑节点的总数称作节点的黑深度（black depth）——根节点的黑深度为0，故条件（4）可理解为“所有外部节点的黑深度统一”。

由条件（4）可进一步推知，在从任一节点通往其任一后代外部节点的沿途，黑节点的总数亦必相等。除去（黑色）外部节点，沿途所经黑节点的总数称作该节点的黑高度（black height）——所有外部节点的黑高度均为0。特别地，根节点的黑高度亦称作全树的黑高度，在数值上与外部节点的黑深度相等。

(2,4)树 == 红黑树

红黑树与B-树之间，存在极其密切的联系，经适当转换之后，二者相互等价。具体地，自顶而下逐层考查红黑树各节点，每遇到一个红节点，都将对应的子树整体提升一层，从而与其父节点（必黑）水平对齐，二者之间的联边则相应地调整为横向。如此转换之后，沿水平方向相邻的边至多两条，涉及的节点至多三个，此时若将原红黑树的节点视作关键码，沿水平方向相邻的每一组（父亲至多三个）节点恰好构成4阶B-树的一个节点。

下图针对所有可能的情况，分别给出了具体的转换过程。按照上述对应关系，每棵红黑树都等价于一棵(2,4)-树：前者的每一节点都对应于后者的一个关键码。通往黑节点的边，对黑高度有贡献，并在(2,4)-树中得以保留；通往红节点的边对黑高度没有贡献，在(2,4)-树中对应于节点内部一对相邻的关键码。

对照红黑树的条件，(2,4)-树中的每个节点应包含且仅包含一个黑关键码，同时红关键码不得超过两个，而且若某个节点果真包含两个红关键码，则黑关键码的位置必然居中。

平衡性

与所有二叉搜索树一样，红黑树的性能首先取决于其平衡性。包含n个内部节点的红黑树T的高度h也不致超过$O(\log n)$，更严格地有：$\log_2(n+1)\le h\le 2 \cdot \log_2(n+1)$。

若将T的黑高度记作H，则H也是T多对应(2,4)-树，故由关于B-树高度与所含关键码总数关系的结论，有：

既然任一通路都不含相邻的红节点，故必有：

尽管红黑树不能如完全树那样可做到理想平衡，也不如AVL树那样可做到较严格的适度平衡，但其高度仍控制在最小高度的两倍以内，从渐进的角度看仍是$O(\log n)$，依然保证了适度平衡——这正是红黑树可高效率支持各种操作的基础。

1.3.红黑树接口定义

基于BST模板类，可派生出RedBlack模板类。

1
2
3
4
5
6
7
8
9
10
11
#include "BST/BST.h" //基于BST实现RedBlack
template <typename T> class RedBlack : public BST<T> { //RedBlack树模板类
protected:
   void solveDoubleRed ( BinNodePosi(T) x ); //双红修正
   void solveDoubleBlack ( BinNodePosi(T) x ); //双黑修正
   int updateHeight ( BinNodePosi(T) x ); //更新节点x的高度
public:
   BinNodePosi(T) insert ( const T& e ); //插入（重写）
   bool remove ( const T& e ); //删除（重写）
// BST::search()等其余接口可直接沿用
};

这里直接沿用了BST的查找算法search()，并根据红黑树的重平衡规则与算法，重写了insert()和remove()接口；新加的两个内部功能接口solveDoubleRed()和solveDoubleBlack()，分别用于在节点插入或删除之后恢复全树平衡。

另外还需使用此前二叉树节点模板类BinNode中预留的两个成员变量height和color，可借助辅助宏来检查节点的颜色以及判定是否需要更新（黑）高度记录。这里的确并未真正地实现外部节点，而是将它们统一地直接判定为黑“节点”——尽管它们实际上只不过是NULL，其余节点则一概视作节点。下面是用以简化红黑树算法描述的宏：

1
2
3
4
5
6
#define IsBlack(p) ( ! (p) || ( RB_BLACK == (p)->color ) )
#define IsRed(p) ( ! IsBlack(p) )
#define BlackHeightUpdated(x) ( /* RedBlack高度更新条件 */ \
   ( stature( (x).lc ) == stature( (x).rc ) ) && \
   ( (x).height == ( IsRed( &x ) ? stature( (x).lc ) : stature( (x).lc) + 1 ) ) \
)

下面是红黑树节点的黑高度更新的算法实现，此处的height已不再是指常规的树高，而是红黑树的黑高度，节点黑高度需要更新的情况共分三种：左、右孩子的黑高度不等；或者作为红节点，黑高度与其孩子不相等；或者作为黑节点，黑高度不等于孩子的黑高度加一。

1
2
3
4
5
6
7
template <typename T> int RedBlack<T>::updateHeight ( BinNodePosi(T) x ) { //更新节点高度
   x->height = __max ( stature ( x->lc ), stature ( x->rc ) ); //孩子一般黑高度相等，除非出现双黑
   /*DSA*/// 红黑树中各节点左、右孩子的黑高度通常相等
   /*DSA*/// 这里之所以取更大值，是便于在删除节点后的平衡调整过程中，正确更新被删除节点父亲的黑高度
   /*DSA*/// 否则，rotateAt()会根据被删除节点的替代者（高度小一）设置父节点的黑高度
   return IsBlack ( x ) ? x->height++ : x->height; //若当前节点为黑，则计入黑深度
} //因统一定义stature(NULL) = -1，故height比黑高度少一，好在不致影响到各种算法中的比较判断

2.节点插入算法

2.1.节点插入与双红现象

假定经调用接口search(e)做查找之后，确认目标节点尚不存在。于是，在查找终止的位置x处创建节点，并随机将其染成红色（除非次时全树仅含一个节点），对照红黑树的四项条件，唯有（3）未必满足——即此时x的父亲可能是红色。

1
2
3
4
5
template <typename T> BinNodePosi(T) RedBlack<T>::insert ( const T& e ) { //将e插入红黑树
   BinNodePosi(T) & x = search ( e ); if ( x ) return x; //确认目标不存在（留意对_hot的设置）
   x = new BinNode<T> ( e, _hot, NULL, NULL, -1 ); _size++; //创建红节点x：以_hot为父，黑高度-1
   BinNodePosi(T) xOld = x; solveDoubleRed ( x ); return xOld; //经双红修正后，即可返回
} //无论e是否存在于原树中，返回时总有x->data == e

因新节点的引入，而导致父子节点同时为红色的此类情况，称作“双红”（double red），为修正双红缺陷，可调用solveDoubleRed(x)接口。每引入一个关键码，该接口都可能迭代地调用多次。在此过程红，当前节点x的兄弟及两个孩子（初始时都是外部节点），始终均为黑色。

将x的父亲与祖父分别记作p和g，既然此前的红黑树合法，故作为红节点p的父亲，g必然存在且为黑色。g作为内部节点，其另一孩子（即p的兄弟、x的叔父）也必然存在，将其记作u。以下，视节点u的颜色不同，分两类情况分别处置。

2.2.双红修正

2.2.1. RR-1

首先，考查u为黑色的情况，此时x的兄弟、两个孩子的黑高度，均与u相等。下图中的(a)和(b)即为此类情况的两种可能（另有两种对称情况）。

此时红黑树条件（3）的违反，从B-树的角度等效地看，即同一节点不应包含紧邻的红色关键码。故只需令黑色关键码与紧邻的红色关键码互换颜色，这等效于按中序遍历次序，对节点x、p和g及其四棵子树，做一次局部“3+4”重构。

如此调整之后，局部子树的黑高度将复原，这意味着全树的平衡也必然得以恢复，同时新子树的根节点b为黑色，也不致引发新的双红现象，至此整个插入操作遂告完成。

2.2.2. RR-2

再考查节点u为红色的情况，此时u的左、右孩子非空且均为黑色，其黑高度必与x的兄弟以及两个孩子相等。

此时红黑树条件（3）的违反，从B-树角度等效地看，即该节点因超过4度而发生上溢。从图(c)红黑树的角度看，只需将红节点p和u转为黑色，黑节点g转为红色，x保持红色；从图(c’)的角度看，等效于上溢节点的一次分裂。

如此调整之后局部子树的黑高度复原，然而子树根节点g转为红色之后，有可能在更高层再次引发双红现象，对应于在关键码g被移出并归入上层节点之后，进而导致上层节点的上溢——即上溢的向上传播。若发生这种传播，可将g视作新插入的节点，同样地分以上两类情况如法处置，每经过一次这样的迭代，节点g都将在B-树中（作为关键码）上升一层，而在红黑树中存在双红缺陷的位置也将相应地上升两层，故累计至多迭代$O(\log n)$次。

特别地，若最后一步迭代之后导致原树根的分裂，并由g独立地构成新的树根节点，则应遵照红黑树条件（1）的要求，将其转换为黑色，如此，全树的黑高度随机增加一层。

2.2.3. 复杂度

以上情况的处理流程可归纳为下图，其中的重构、染色等局部操作均只需常数时间、故只需统计这些操作在修正过程中被调用的总次数。可知节点插入之后的双红修正，累计耗时不会超过$O(\log n)$，即便计入此前的关键码查找预计节点接入等操作，红黑树的每次节点插入操作，都可在$O(\log n)$时间内完成。

需要指出的是，只有在RR-1修复时才需要1~2次旋转，而且一旦旋转后，修复过程必然随即完成，故就全树拓扑结构而言，每次插入后仅涉及常数次调整；下小节将要介绍的红黑树的节点删除操作也是如此，而回顾此前学过的AVL树，却只能保证前一点。

2.2.4. 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*******************************************************************************
 * RedBlack双红调整算法：解决节点x与其父均为红色的问题。分为两大类情况：
 *    RR-1：2次颜色翻转，2次黑高度更新，1~2次旋转，不再递归
 *    RR-2：3次颜色翻转，3次黑高度更新，0次旋转，需要递归
 ******************************************************************************/
template <typename T> void RedBlack<T>::solveDoubleRed ( BinNodePosi(T) x ) { //x当前必为红
   if ( IsRoot ( *x ) ) //若已（递归）转至树根，则将其转黑，整树黑高度也随之递增
      {  _root->color = RB_BLACK; _root->height++; return;  } //否则，x的父亲p必存在
   BinNodePosi(T) p = x->parent; if ( IsBlack ( p ) ) return; //若p为黑，则可终止调整。否则
   BinNodePosi(T) g = p->parent; //既然p为红，则x的祖父必存在，且必为黑色
   BinNodePosi(T) u = uncle ( x ); //以下，视x叔父u的颜色分别处理
   if ( IsBlack ( u ) ) { //u为黑色（含NULL）时 //*DSA*/printf("  case RR-1:\n");
      if ( IsLChild ( *x ) == IsLChild ( *p ) ) //若x与p同侧（即zIg-zIg或zAg-zAg），则
         p->color = RB_BLACK; //p由红转黑，x保持红
      else //若x与p异侧（即zIg-zAg或zAg-zIg），则
         x->color = RB_BLACK; //x由红转黑，p保持红
      g->color = RB_RED; //g必定由黑转红
///// 以上虽保证总共两次染色，但因增加了判断而得不偿失
///// 在旋转后将根置黑、孩子置红，虽需三次染色但效率更高
      BinNodePosi(T) gg = g->parent; //曾祖父（great-grand parent）
      BinNodePosi(T) r = FromParentTo ( *g ) = rotateAt ( x ); //调整后的子树根节点
      r->parent = gg; //与原曾祖父联接
   } else { //若u为红色 //*DSA*/printf("  case RR-2:\n");
      p->color = RB_BLACK; p->height++; //p由红转黑
      u->color = RB_BLACK; u->height++; //u由红转黑
      if ( !IsRoot ( *g ) ) g->color = RB_RED; //g若非根，则转红
      solveDoubleRed ( g ); //继续调整g（类似于尾递归，可优化为迭代形式）
   }
}

3.节点删除算法

3.1. 节点删除与双黑现象

为删除关键码e，首先调用标准接口BST::search(e)进行查找，若查找成功，则调用内部接口removeAt(x)实施删除，按照对该接口所约定的语义，x为实际被摘除者，其父亲为p = _hot，其接替者为r，而r的兄弟为外部节点w = NULL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T> bool RedBlack<T>::remove ( const T& e ) { //从红黑树中删除关键码e
   BinNodePosi(T) & x = search ( e ); if ( !x ) return false; //确认目标存在（留意_hot的设置）
   BinNodePosi(T) r = removeAt ( x, _hot ); if ( ! ( --_size ) ) return true; //实施删除
// assert: _hot某一孩子刚被删除，且被r所指节点（可能是NULL）接替。以下检查是否失衡，并做必要调整
   if ( ! _hot ) //若刚被删除的是根节点，则将其置黑，并更新黑高度
      { _root->color = RB_BLACK; updateHeight ( _root ); return true; }
// assert: 以下，原x（现r）必非根，_hot必非空
   if ( BlackHeightUpdated ( *_hot ) ) return true; //若所有祖先的黑深度依然平衡，则无需调整
   if ( IsRed ( r ) ) //否则，若r为红，则只需令其转黑
      { r->color = RB_BLACK; r->height++; return true; }
// assert: 以下，原x（现r）均为黑色
   //*DSA*/printBinTree(_hot, 0, 0);
   solveDoubleBlack ( r ); return true; //经双黑调整后返回
} //若目标节点存在且被删除，返回true；否则返回false

因随后的复衡调整位置可能逐层上升，故不妨等效地理解为：w系与r黑高度相等的子红黑树，且随其父亲x一并被摘除，如此可将x统一视作上分支节点，从而更为通用地描述以下算法。不难验证此时红黑树的前两个条件继续满足，但后两个条件却未必。

当然若x原为树根，则无论r颜色如何，只需将其置为黑色并更新黑高度即可，因此不妨假定x的父亲p存在。可分为下面三种情况：第一种只需进行普通的删除操作，即摘除子树w，并将x替换为r；第二种只需在删除操作之后将r转为黑色；第三种，x与r均为黑色，则在删除操作之后，局部子树的黑高度将会降低一个单位。

被删除节点x以其替代者r同为黑色的此类情况，称作“双黑”（double black），此时需调用solveDoubleBlack(r)算法予以修正。为此需考查原黑节点x的兄弟s（必然存在，但可能是外部节点），并视s和p颜色的不同组合，按四种情况分别处置。

3.2. 双黑修正

3.2.1. BB-1: s为黑，且至少有一个红孩子t

既然节点x的另一个孩子w = NULL，故从B-树角度看节点x被删除之后的情况，可等效理解为关键码x原所属的节点发生下溢。此时t和s必然属于B-树的同一节点，且该节点就是下溢节点的兄弟。故可参照B-树，下溢节点从父亲点借出一个关键码p，然后从父亲节点从下溢节点的兄弟节点借出一个关键s。

上述调整过程等效于，对节点t、s和p实施“3 + 4 重构”。若这三个节点按中序遍历次序重命名为a，b和c，则还需将a和c染成黑色，b则继承p此前的颜色。对上图的例子而言，就是将t和p染成黑色，s继承p此前的颜色，整个过程中节点r保持黑色不变。

经过以上处理之后，红黑树的所有条件，都在这一局部以及全局得到恢复，故删除操作遂高完成。

3.2.2. BB-2-R：s为黑，且两个孩子均为黑；p为红

与BB-1类似，在对应的B-树中，关键码x的删除导致其所属的节点下溢，但因此时关键码s所在节点只有两个分支，故下溢节点无法从父节点借出关键码p。同样按照B-树平衡算法，将关键码p取出并下降一层，再将原左、右孩子合并为一个节点，如图（b’）。从红黑树角度看，这一过程等效为将s和p颜色互换，如图（b）。

经过以上处理，红黑树的所有条件都在此局部得以恢复。另外，由于关键码p原为红色，故在关键码p所属节点中，其左或右必然还有一个黑色关键码（不可能左右都有），这意味着在关键码p从其中取出之后，不致引发新的下溢。至此，红黑树条件亦必在全局得以恢复，删除操作即告完成。

3.2.3. BB-2-B：s为黑，且两个孩子均为黑；p为黑

此时，与BB-2-R类似，在对应的B-树中，因关键码x的删除，导致其所属节点发生下溢。如图（b’）可将下溢节点与其兄弟合并，从红黑树的角度来看，这一过程可等效为将节点s转换为红色，如图（b）。

然后既然s和x在此之前均为黑色，故p原所属的B-树节点必然仅含p这一个关键码，于是在p被借出之后，该节点必将继而发生下溢，从而有待于后续的进一步修正。从红黑树的角度来看，此时的状态则可等效地理解为：节点p的（黑色）父亲刚被删除。

实际上这也是双黑修正过程中，需要再次迭代的唯一可能。而幸运的是，尽管此类情况可能持续发生，但下溢的位置必然会不断上升，故至多迭代$O(\log n)$次后必然终止。

3.2.4. BB-3：s为红（其孩子均为黑）

此时作为红节点s的父亲，节点p必为黑色，同时s的两个孩子也应均为黑色。从B-树的角度看，如图（b’）令关键码s与p互换颜色，即可得到一棵与之完全等价的B-树，而从红黑树的角度来看，如图（b），这一转换对应于以节点p为轴做一次旋转，并交换节点s与p的颜色。

虽然经过如此处理之后，双黑缺陷依然存在（子树r的黑高度并未复原），而且缺陷位置的高度也并未上升。然而实际上情况已经发生微妙而本质的变换，观察图（b）可以看到，转换之后的红黑树中，被删除节点x有了一个新的兄弟s'；另外现在的节点p，也已经由黑色转为红色。这就意味着接下来的修正调整只会转入前两种情况：BB-1或者BB-2-R，即接下来至多再做一次迭代调整，整个双黑修正的任务即可完成。

3.2.5. 复杂度

以上各情况的处理流程，可归纳为下图：

其中涉及的重构、染色等局部操作，均可在常数时间内完成，故为了估计整个双黑修正过程的时间复杂度，也只需统计这些操作各自的累计执行次数，具体归纳为下表：

可见，前两种情况各自只需做一轮修正，最后一种情况亦不过两轮。情况BB-2-B虽可能需要反复修正，但由于待修正位置的高度严格单调上升，累计也不致过$O(\log n)$轮，故双黑修正过程总共耗时不超过$O(\log n)$。即便计入此前的关键码查找和节点删除操作，红黑树的节点删除操作总是可在$O(\log n)$时间内完成。

从上面的分析可知，一旦在某步迭代中做过节点的旋转调整，整个修复过程便会随机完成。因此与双红修正一样，双黑修正的整个过程，也仅涉及常数次的拓扑结构调整操作。

这一特性也意味着，在每次删除操作之后，拓扑联接关系有所变化的节点绝不会超过常数个——这一点与AVL树的删除操作完成不同，也是二者之间最本质的一项差异。

3.2.6. 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/******************************************************************************
 * RedBlack双黑调整算法：解决节点x与被其替代的节点均为黑色的问题
 * 分为三大类共四种情况：
 *    BB-1 ：2次颜色翻转，2次黑高度更新，1~2次旋转，不再递归
 *    BB-2R：2次颜色翻转，2次黑高度更新，0次旋转，不再递归
 *    BB-2B：1次颜色翻转，1次黑高度更新，0次旋转，需要递归
 *    BB-3 ：2次颜色翻转，2次黑高度更新，1次旋转，转为BB-1或BB2R
 *****************************************************************************/
template <typename T> void RedBlack<T>::solveDoubleBlack ( BinNodePosi(T) r ) {
   BinNodePosi(T) p = r ? r->parent : _hot; if ( !p ) return; //r的父亲
   BinNodePosi(T) s = ( r == p->lc ) ? p->rc : p->lc; //r的兄弟
   if ( IsBlack ( s ) ) { //兄弟s为黑
      BinNodePosi(T) t = NULL; //s的红孩子（若左、右孩子皆红，左者优先；皆黑时为NULL）
      if ( IsRed ( s->rc ) ) t = s->rc; //右子
      if ( IsRed ( s->lc ) ) t = s->lc; //左子
      if ( t ) { //黑s有红孩子：BB-1
         //*DSA*/printf("  case BB-1: Child ("); print(s->lc); printf(") of BLACK sibling ("); print(s); printf(") is RED\n");
         RBColor oldColor = p->color; //备份原子树根节点p颜色，并对t及其父亲、祖父
      // 以下，通过旋转重平衡，并将新子树的左、右孩子染黑
         BinNodePosi(T) b = FromParentTo ( *p ) = rotateAt ( t ); //旋转
         if ( HasLChild ( *b ) ) { b->lc->color = RB_BLACK; updateHeight ( b->lc ); } //左子
         if ( HasRChild ( *b ) ) { b->rc->color = RB_BLACK; updateHeight ( b->rc ); } //右子
         b->color = oldColor; updateHeight ( b ); //新子树根节点继承原根节点的颜色
         //*DSA*/printBinTree(b, 0, 0);
      } else { //黑s无红孩子
         s->color = RB_RED; s->height--; //s转红
         if ( IsRed ( p ) ) { //BB-2R
            //*DSA*/printf("  case BB-2R: Both children ("); print(s->lc); printf(") and ("); print(s->rc); printf(") of BLACK sibling ("); print(s); printf(") are BLACK, and parent ("); print(p); printf(") is RED\n"); //s孩子均黑，p红
            p->color = RB_BLACK; //p转黑，但黑高度不变
            //*DSA*/printBinTree(p, 0, 0);
         } else { //BB-2B
            //*DSA*/printf("  case BB-2R: Both children ("); print(s->lc); printf(") and ("); print(s->rc); printf(") of BLACK sibling ("); print(s); printf(") are BLACK, and parent ("); print(p); printf(") is BLACK\n"); //s孩子均黑，p黑
            p->height--; //p保持黑，但黑高度下降
            //*DSA*/printBinTree(p, 0, 0);
            solveDoubleBlack ( p ); //递归上溯
         }
      }
   } else { //兄弟s为红：BB-3
      //*DSA*/printf("  case BB-3: sibling ("); print(s); printf(" is RED\n"); //s红（双子俱黑）
      s->color = RB_BLACK; p->color = RB_RED; //s转黑，p转红
      BinNodePosi(T) t = IsLChild ( *s ) ? s->lc : s->rc; //取t与其父s同侧
      _hot = p; FromParentTo ( *p ) = rotateAt ( t ); //对t及其父亲、祖父做平衡调整
      //*DSA*/printBinTree<T>(s, 0, 0);
      solveDoubleBlack ( r ); //继续修正r处双黑——此时的p已转红，故后续只能是BB-1或BB-2R
   }
}