回顾：上一篇我们结束了 AVLTree 的相关介绍，接下来这篇文章让我们进入到 红黑树 的学习，体会新的设计思路吧~

前言

摘要：红黑树是一种自平衡的二叉搜索树，通过为每个结点增加颜色属性并施加约束，确保树的高度始终保持在 O(logN) 级别。本文首先介绍红黑树的基本概念与四条核心规则，分析其如何保证最长路径不超过最短路径的 2 倍，并推导其增删查改的时间复杂度为 O(logN)；随后以 C++ 为例，从定义结点结构开始，逐步实现红黑树的插入（变色、单旋＋变色、双旋＋变色三种特别处理）、验证、查找、删除与析构，并附上测试用例验证正确性。最后总结红黑树的核心要点，为后续封装红黑树实现 mymap 与 myset 容器打下基础。

一 红黑树的概念

1. 每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。
2. 通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

1.1 红黑树的规则

1. 每个结点不是红色就是黑色。
2. 根结点是黑色的。
3. 如果⼀个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点。（但可以有连续的黑色节点）
4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点。
   下面来个动图演示一颗红黑树的形成：
   

上图网址：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

1.2 红黑树如何确保最长路径不超过最短路径的2倍？

1. 从根到NULL结点的每条路径都有相同数量的黑色结点。
2. 极端场景下，最短路径就就是全是黑色结点的路径，长度设为bh(black height)。
3. 最长的路径就是⼀黑⼀红间隔组成，长度设为2*bh。
4. 理论上的最短路径和最长路径并不是在每棵红黑树都存在的。
5. 假设任意⼀条从根到NULL结点路径的长度为h，那么bh <= h <= 2*bh。

1.3 红黑树的效率

1. 假设N是红黑树树中结点数量，h最短路径的长度，那么2^h - 1 <= N < 2^(2*h) - 1，由此推出h ≈ logN。

   关于N < 2^(2*h) - 1为什么取不到等号？

   • 存在最短路径最长路径的同时，二叉树不可能是满二叉树。
     假设h = 1：
     

   最短路径为1，最长路径为2。
   N 取不到2^(2*h) - 1，即3。
   最多只能取到如图所示2个结点。

2. 也就是意味着红黑树增删查改最坏也就是走最长路径2*logN，那么时间复杂度还是O(logN)。

二 红黑树的实现

2.1 定义红黑树

2.1.1 枚举类：Colour

enumColour{RED,BLACK};

• 没啥好说的，红黑树就红色或者黑色两种结点。

2.1.2 定义结点结构体

template<classK,classV>structRBTreeNode{pair<K,V>_kv;RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;Colour _col;RBTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};

• 跟AVL树类似，只是多了个_col记录颜色。
• 这里和AVL树一样记录了_parent，方便后续旋转。

2.2 红黑树的插入

为了保证每条路径上的黑色结点数量相等，没有特殊情况的话，新插入结点都为红。

1. 红黑树为空，插入结点为黑。
2. 插入结点的parent为黑，插入结点为红。
3. 插入结点的parent为红，插入结点为红，不符合规则，特别处理。

假设插入结点为cur，插入结点的父母为parent，parent的父母为grandparent，parent的兄弟为uncle（后面都以首字母简称）。

部分代码

boolInsert(constpair<K,V>&kv){if(_root==nullptr){_root=newNode(kv);_root->_col=BLACK;returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}elseif(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(kv);if(parent->_kv.first>kv.first){parent->_left=cur;}else{parent->_right=cur;}cur->_parent=parent;while(parent&&parent->_col==RED){Node*gparent=parent->_parent;Node*uncle=nullptr;// change colour ...}}

• 这部分逻辑跟AVLTree是一样的（除了处理_col的部分）：
• 处理红黑树（_root为空）的情况。
• 用cur找到新结点应当插入位置，parent记录cur的_parent.
• 最后构造新结点，把新结点赋值给cur，让其根据情况成为parent的左孩子或右孩子。
• 其次若parent为红需要特殊处理，进入循环。
• 先定义gparent和uncle。
• 注：由于parent为红，而_root一定为黑，所以gparent一定存在。极端情况为gparent恰好就是_root。

2.2.1 特别处理1：变色

u存在且为红，只变色。

（1）简单举例

画个栗图：

插入cur后存在连续的红色结点。
则要实现的效果：

变色后cur更新为g，向上检查变色。

（2）推广到所有情况

①来个抽象图

1. 上图的c可能不是新增结点，而是从g变到c的
2. 设a、b是每条路径拥有hb-1个黑色结点的，根为红色结点的子树。
3. 设d、e、f是每条路径拥有hb个黑色结点的子树。

②情况1：hb = 0

1.介绍所处情况

• a、b、d、e、f都是空子树。
  如图：
  
• c还可以是下面白色结点位置之一：
  
  c就是新插入结点，上面的（1）简单举例就属于这种情况。

2.采取操作

• 直接变色到：
  

③情况2：hb = 1

1.介绍所处情况

c是由g变上来的

Ⅰ则a、b是根结点为红色的hb = 0的子树：

这样。
Ⅱ新增结点
新增结点可能出现在4个位置（即4个白色结点）之一：

Ⅲd、e、f是根结点为黑色的hb = 1的子树：

四种情况。
Ⅳ总结
一共444*4 = 256种情况，都是只需要变色就行。

2.采取措施

取其中一种情况分析：

明显有连续的红色结点，不符合规则3，需变色。
最终效果：

再往上检查：

④情况3：hb = 2

1.介绍所处情况

Ⅰ则a、b是根结点为红色的hb = 1的子树：

如图4个位置的红色结点可能存在（或不存在）。

C(4,4) + C(3,4) + … + C(0,4) = 16

所以子树共有16种可能形态。

Ⅱ新增结点
16种形态，一种形态下可新增结点的位置也很多，是否会触发变色也不一定。
拿一个极端例子分析：

直接新增，不触发变色：

Ⅲd、e、f是根结点为黑色的hb = 2的子树：

• 子树可以是3层或4层。
• 3层：C(4,4) + C(3,4) + … + C(0,4) = 16
• 4层：C(8,8) + C(7,8) + … + C(0,8) = 256
  所以一共16+256 = 272 种可能形态。
  Ⅲ总结
  总共可能的情况数有百亿往上。

2.采取措施

取其中一种情况分析：

变色，c向上更新：

g变到c，再继续向上更新。

（3）代码实现

//省略给uncle赋值部分代码if(uncle&&uncle->_col==RED){parent->_col=BLACK;uncle->_col=BLACK;gparent->_col=RED;}else{//特别处理2}

2.2.2 特别处理2：单旋＋变色

有两种情况：u不存在 或 存在且为黑。采取操作：单旋（下面举例为需要右单旋的情况，左单旋本质上也是一样的）＋变色。

（1） u不存在

①介绍所处情况

u不存在，则c一定是新增结点。

• 因为如果c更新上来的，c原来就得是黑的。
• c是黑的，下图中g的左子树和右子树黑色结点数量就不相同了。
• 不符合规则4，因此c不可能是更新上来的。

②采取操作

先以g为旋转点右单旋：

再变色：

（2）u存在且为黑

①介绍所处情况

u存在且为黑，则c一定是更新上来的。

同样反推：

• 如果c是新增节点，a b子树肯定为空。
• 我们看新增前的树，p的右子树为空，d子树也肯定为空子树。
• 先不论 e f 子树是什么形态，g的右子树已经比左子树多了u这个黑色结点，不符合规则4。
• 因此c不可能是新增节点。

在此基础上，我们先来看新增前的情况：

• 为保证规则4，a b e f 四棵子树黑色结点为hb-1个，d子树为hb个。
• a b是两棵根结点为红色的子树。
  再来看新增后：
  
  从新增结点更新上去，a b子树的根结点就变成了黑色：
  
• 上图 a b d 子树黑色结点为hb个，e f子树为hb-1个。

②采取措施

同样先以g为旋转点右单旋：

再变色：

（3）代码实现

//同样省略给uncle赋值部分代码if(uncle&&uncle->_col==RED){//特别处理1}else{if(gparent->_left==parent&&parent->_left==cur){_RotateR(gparent);parent->_col=BLACK;gparent->_col=RED;}elseif(gparent->_right==parent&&parent->_right==cur){_RotateL(gparent);parent->_col=BLACK;gparent->_col=RED;}else{//特别处理3}}

2.2.3 特别处理3：双旋＋变色

也是两种情况：u不存在 或 存在且为黑。采取操作：双旋（这里同样只举例先左单旋再右单旋，另一种情况本质上一样）＋变色。

（1）u不存在

①介绍所处情况

c一定是新增结点（这个推论跟单旋的情况一样）。

②采取措施

先以p为旋转点左单旋：

变色：

再以g为旋转点右单旋：

（2）u存在且为黑

①介绍所处情况

c同样一定是更新上来的。
新增结点前的树：

• 为保证规则4，d子树黑色结点数量为hb， a b e f 子树为hb-1
• a b 子树根结点为红色。
  新增后：
  
• 假设新增结点在a子树。
• 更新上去到c变为红色，a b子树变为根节点为黑色的子树。
• 则现在 a b d 子树黑色结点为hb个，e f不变还是hb-1个。

②采取措施

先以p为旋转点左单旋：

变色：

再以g为旋转点右单旋：

最后的树显然符合规则4，搞定。

（3）代码实现

if(uncle&&uncle->_col==RED){//特别处理1}else{if(gparent->_left==parent&&parent->_left==cur){//特别处理2}elseif(gparent->_right==parent&&parent->_right==cur){//特别处理2}elseif(gparent->_left==parent&&parent->_right==cur){_RotateL(parent);cur->_col=BLACK;gparent->_col=RED;_RotateR(gparent);}else{_RotateR(parent);cur->_col=BLACK;gparent->_col=RED;_RotateL(gparent);}}

2.2.4 整体代码

boolInsert(constpair<K,V>&kv){if(_root==nullptr){_root=newNode(kv);_root->_col=BLACK;returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}elseif(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(kv);if(parent->_kv.first>kv.first){parent->_left=cur;}else{parent->_right=cur;}cur->_parent=parent;// change colourwhile(parent&&parent->_col==RED){Node*gparent=parent->_parent;Node*uncle=nullptr;//给uncle赋值if(gparent->_left==parent){uncle=gparent->_right;}else{uncle=gparent->_left;}//分情况特殊处理if(uncle&&uncle->_col==RED){parent->_col=BLACK;uncle->_col=BLACK;gparent->_col=RED;}else{if(gparent->_left==parent&&parent->_left==cur){_RotateR(gparent);parent->_col=BLACK;gparent->_col=RED;}elseif(gparent->_right==parent&&parent->_right==cur){_RotateL(gparent);parent->_col=BLACK;gparent->_col=RED;}elseif(gparent->_left==parent&&parent->_right==cur){_RotateL(parent);cur->_col=BLACK;gparent->_col=RED;_RotateR(gparent);}else{_RotateR(parent);cur->_col=BLACK;gparent->_col=RED;_RotateL(gparent);}}//循环继续的要点：cur跟parent需要更新cur=gparent;parent=cur->_parent;}_root->_col=BLACK;returntrue;}

• 为了保证_root是黑的，最后可以直接不管三七二十一给它赋值一下。

2.3 红黑树的验证

分别检查4条规则。

boolIsRBTree(){if(_root==nullptr){returntrue;}if(_root->_col!=BLACK){returnfalse;}intrefNum=0;Node*cur=_root;while(cur){if(cur->_col==BLACK){refNum++;}cur=cur->_left;}return_check(_root,refNum,0);}

1. 先处理树为空（_root为空）的情况。
2. 规则①检查_root是否为黑。
3. 用refNum记录一条路径（从_root到空结点）的黑色结点备用。
4. 进入_check函数。

bool_check(Node*root,constintrefNum,intblackNum){if(root==nullptr){if(blackNum!=refNum){cout<<"refNum:"<<refNum<<"; blackNum:"<<blackNum<<endl;returnfalse;}returntrue;}if(root->_col==BLACK){blackNum++;}elseif(root->_col==RED){if(root->_parent->_col==RED){cout<<"red node has red parent"<<endl;returnfalse;}}else{cout<<"illegal colour"<<endl;returnfalse;}return_check(root->_left,refNum,blackNum)&&_check(root->_right,refNum,blackNum);}

5. 进入函数，先检查root是否为空。
6. 规则④：若为空则结束一条路径，需要检查这条路径的黑色结点数量blackNum是否与参考数量refNum相等。
7. 若不相等，则违反规则④，返回false；相等则返回true。
8. root不为空，则判断当前root是否为黑。
9. root为黑则blackNum++。
10. 规则③：root为红，则判断其parent是否为红，为红违反规则③，返回false。
11. 规则②：若root既不为黑也不为红，违反规则②，返回false。
12. 再递归检查root->_left跟root->_right。

2.4 红黑树的查找

跟AVL树一样。

Node*Find(constK&key){Node*cur=_root;while(cur){if(cur->_kv.first<key){cur=cur->_right;}elseif(cur->_kv.first>key){cur=cur->_left;}else{returncur;}}returnnullptr;}

直接照搬过来。

2.5 红黑树的删除

2.5.1 删除指定节点

不细究（比较复杂），可以放一份思路：

2.5.2 析构

加一个析构函数防止内存泄漏：

public://...~RBTree(){_Destroy(_root);_root=nullptr;}private:void_Destroy(Node*root){if(root==nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);deleteroot;}//...

辅助函数_Destroy写在private区域，以便递归销毁。

2.6 测试

voidTestRBTree01(void){wyzy::RBTree<int,int>t;//（1）测试用例不涉及双旋//int a[] = { 18, 10, 6, 15, 30, 25, 40 };//（2）测试用例涉及双旋inta[]={18,10,6,15,30,25,40,27};for(autoe:a){t.Insert({e,e});}t.inOrder();t.preOrder();cout<<t.IsRBTree()<<endl;}

测试代码仅供参考。

• 这里我写了inOrder跟preOrder，方便打印观察。
• 颜色打印出来0代表红，1代表黑。

• 最终测试结果符合预期。

红黑树的学习就到这里，下一篇我们要 封装红黑树 实现容器mymap跟myset ，很快会更出来~