【C++数据结构进阶】深度剖析红黑树：从底层原理到手撕代码
目录
引言
在C++的数据结构体系中，红黑树是一种极为重要且应用广泛的自平衡二叉搜索树。它是STL中map和set底层实现的核心数据结构。与AVL树相比，红黑树通过更宽松的平衡条件，在保证最坏情况下效率 O(log N) 的同时，显著减少了旋转操作的次数，从而在实际应用中展现出更优的性能表现。
一. 红黑树的概念
1.1 什么是红黑树
红黑树本质上是一棵二叉搜索树，但在每个节点上增加了一个颜色标记（红色或黑色）。通过巧妙地利用颜色约束，红黑树能够确保从根到任意叶子节点的路径长度差异不会超过2倍，从而实现了近似平衡。
1.2 红黑树的规则
- 颜色限制：每个结点不是红色就是黑色 。
- 根的颜色：根结点必须是黑色的 。
- 红色互斥：如果一个结点是红色的，则它的两个孩子结点必须是黑色的（即不能有连续的红色结点）。
- 黑色平衡：对于任意一个结点，从该结点到其所有空结点（NIL）的路径上，均包含相同数量的黑色结点 。
- (补充规则)：所有的叶子结点（NIL 结点）被视为黑色 。
说明：《算法导论》等书籍上补充了一条每个叶子结点(NIL)都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了方便便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道一下这个概念即可。
1.2 红黑树是如何保持平衡的
根据规则4，从根到空节点的每条路径都有相同数量的黑色节点。假设这个黑色节点数量为bh（black height）。
- 最短路径：极端情况下，路径全部由黑色节点组成，长度为
bh - 最长路径：根据规则3，不能有连续的红色节点，所以最长路径是黑红交替组成，长度为
2*bh
因此，对于任意路径长度h，有：bh ≤ h ≤ 2*bh
1.3 红黑树的效率
1.3.1 红黑树的时间复杂度
假设红黑树中有N个节点，最短路径长度为h，则：
2^h - 1 ≤ N < 2^(2*h) - 1
由此可推导出：h ≈ log₂N
即使走最长路径，也只需要 2*log₂N的时间，因此红黑树的增删查改操作时间复杂度都是O(log N)。
红黑树的表达相对AVL树要抽象⼀些，AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束，间接的实现了近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。
思考：相比 AVL 树，红黑树好在哪里？
红黑树对平衡的控制不如 AVL 树严格，这意味着在插入相同数量的结点时，红黑树引发的旋转次数更少。对于频繁进行插入和删除操作的场景，红黑树的综合性能略优于 AVL 树 。
1.3.2 红黑树 VS AVL树
| 对比维度 | AVL树 | 红黑树 |
| 平衡条件 | 左右子树高度差≤1（严格平衡） | 最长路径≤2×最短路径（近似平衡） |
| 平衡实现 | 通过高度差直观控制 | 通过颜色规则间接控制 |
| 旋转次数 | 插入时最多2次，删除时可能O(log N)次 | 插入和删除都最多3次旋转 |
| 查找效率 | O(log N)，常数稍优 | O(log N) |
| 插入效率 | O(log N)，调整较多 | O(log N)，调整较少 |
| 使用场景 | 查询密集型应用 | 插入删除频繁的应用（STL） |
总结：红黑树牺牲了一定的平衡性（但仍保证O(log N)），换取了更少的旋转操作，在实际应用中通常性能更优。
二. 红黑树的实现
2.1 红黑树的结构
为了方便后续的旋转和变色操作，我们的节点定义通常采用三叉链结构（包含指向父亲的指针），并显式定义颜色枚举。
// 枚举表示颜色
enum Color
{
RED,
BLACK
};
// 这⾥我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv; // 键值对
RBTreeNode<K, V>* _left; // 左子节点
RBTreeNode<K, V>* _right; // 右子节点
RBTreeNode<K, V>* _parent; // 父节点指针（用于向上调整）
Colour _col; // 节点颜色
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED) // 新节点默认是红色
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
private:
Node* _root = nullptr;
};
注意：构造函数中，新插入的节点默认是红色 。
原因：如果插入黑色节点，必然会违反“每条路径黑色节点数相同”（规则 4），这是全局性的破坏，极难修复。 * 而插入红色节点，可能只会违反“不能连续红”（规则 3），这只是局部性的问题，更容易通过变色或旋转修复 。
2.2 红黑树的插入
2.2.1 红黑树插入的过程
- 插入一个值按二叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的4条规则。
- 如果是空树插入，新增结点必是黑色结点。如果是非空树插入，新增结点必须红色结点，因为非空树插入，新增黑色结点就破坏了规则4，规则4是很难维护的。
- 非空树插入后，新增结点必须红色结点，如果父亲结点是黑色的，则没有违反任何规则，插入结束
- 非空树插入后，新增结点必须红色结点，如果父亲结点是红色的，则违反规则3。进一步分析，c是 红色，p为红，g必为黑，这三个颜色都固定了，关键的变化看u的情况，需要根据u分为以下几种情况分别处理。
注：下图中把新增结点标识为c(cur)，c的父亲标识为p(parent)，p的父亲标识为 g(grandfather)，p的兄弟标识为u（uncle）。
2.2.2 情况1：变色
条件：uncle存在且为红
c为红，p为红，g为黑，u存在且为红，则将p和u变黑，g变红。在把g当做新的c，继续往上更新
原理分析：
因为p和u都是红色，g是黑色，把p和u变黑，左边子树路径各增加一个黑色结点，g再变红，相当于保持g所在子树的黑色结点的数量不变，同时解决了c和p连续红色结点的问题，需要继续往上更新是因为，g是红色，如果g的父亲还是红色，那么就还需要继续处理；如果g的父亲是黑色，则处理结束了；如果g就是整棵树的根，再把g变回黑色。
情况1只变色，不旋转。所以无论c是p的左还是右，p是g的左还是右，都是上面的变色处理方式。
if (uncle && uncle->_col == RED) {
// 变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续向上处理
cur = grandfather;
parent = cur->_parent;
}跟AVL树类似，上图展示了一种具体情况，但是实际中需要这样处理的有很多种情况。
图1将以上类似的处理进行了抽象表达，d/e/f代表每条路径拥有hb个黑色结点的子树，a/b代表每 条路径拥有hb-1个黑色结点的根为红的子树，hb>=0。
下图分别展示了hb == 0/hb == 1/hb == 2的具体情况组合分析，当hb等于2时，这里组合情况上百亿种，但我们只需知道，不论情况多少种，多么复杂，处理方式一样的，变色再继续往上处理即可
2.2.3 情况2：单选+变色
条件：uncle不存在或uncle存在且为黑并且cur、parent、grandfather在同一侧
c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c一定是新增结点，u存在且为黑，则 c一定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。
原理分析：p必须变黑，才能解决，连续红色结点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转+变色。
g
p u
c
场景1：如果p是g的左，c是p的左，那么以g为旋转点进行右单旋，再把p变黑，g变红即可。p变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。
g
u p
c
场景2：如果p是g的右，c是p的右，那么以g为旋转点进行左单旋，再把p变黑，g变红即可。p变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。
2.2.4 情况3：双旋+变色
条件：uncle不存在或uncle为黑色，并且cur、parent、grandfather呈"之"字形，不在同一侧
c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c一定是新增结点，u存在且为黑，则c一定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。
原理分析：p必须变黑，才能解决，连续红色结点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转+变色。
g
p u
c
场景1：如果p是g的左，c是p的右，那么先以p为旋转点进行左单旋，再以g为旋转点进行右单旋，再把c变黑，g变红即可。c变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的父亲是黑色还是红色或者空都不违反规则。
g
u p
c
场景2：如果p是g的右，c是p的左，那么先以p为旋转点进行右单旋，再以g为旋转点进行左单旋，再把c变黑，g变红即可。c变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的逢亲是黑色还是红色或者空都不违反规则。
2.3 红黑树的插入完整代码实现
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
// BST的插入方法
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK; // 根节点必须为黑色
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
// 新增节点必须为红色
cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
// 父亲为爷爷的左子树
if (grandfather->_left == parent)
{
// g
// p u
//c
Node* uncle = grandfather->_right;
// 叔叔存在且为红
if (uncle && uncle->_col == RED)
{
// 变色+继续往上处理
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // 叔叔不存在或者叔叔存在且为黑
{
// g
// p u
//c
// 单旋+变色
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
// 双旋+变色
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
// 父亲为爷爷的右子树
else
{
// g
// p u
// c
Node* uncle = grandfather->_left;
// 叔叔存在且为红
if (uncle && uncle->_col == RED)
{
// 变色+继续往上处理
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // 叔叔不存在或者叔叔存在且为黑
{
// g
// p u
// c
// 单旋+变色
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
// 双旋+变色
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
// 无论最后根节点是否为黑，就直接置为黑
// 确保根节点是黑色
_root->_col = BLACK;
return true;
}
}2.4 红黑树的验证
这里获取最长路径和最短路径，检查最长路径不超过最短路径的2倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查4点规则，满足这4点规则，一定能保证最长路径不超过最短路径的2倍。
- 规则1枚举颜色类型，天然实现保证了颜色不是黑色就是红色。
- 规则2直接检查根即可
- 规则3前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲的颜色就方便多了。
- 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值，依次比较即可。
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool IsBalanceTree()
{
if (_root && _root->_col == RED)
return false;
// 最左路径黑色节点的数量作参考比较其他路径
int left_bn = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
left_bn++;
cur = cur->_left;
}
return _CheckColor(_root, 0, left_bn);
}
private:
// root_cur_bn 根节点到当前节点的黑色节点个数
// 前序递归
bool _CheckColor(Node* root, int root_cur_bn, const int left_bn)
{
if (root == nullptr)
{
// 检查每条路径黑色节点的数量
if (root_cur_bn != left_bn)
{
cout << "黑色节点的数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
root_cur_bn++;
}
// 检查是否有连续的红色节点
// 如果检查孩子的话，情况比较多，所以这里检查父亲
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << root->_kv.first << "存在连续红色节点" << endl;
return false;
}
return _CheckColor(root->_left, root_cur_bn, left_bn)
&& _CheckColor(root->_right, root_cur_bn, left_bn);
}
}2.5 红黑树的查找（同BST）
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
}总结
掌握红黑树不仅能帮助我们深入理解STL容器的底层原理，更能提升我们对数据结构设计思想的理解。在实际开发中，我们通常直接使用STL提供的容器，但了解其内部机制能帮助我们写出更高效的代码。
如有不足或改进之处，欢迎大家在评论区积极讨论，后续我也会持续更新C++相关的知识。文章制作不易，如果文章对你有帮助，就点赞收藏关注支持一下作者吧，让我们一起努力，共同进步！
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
39
0- 0
已为社区贡献7条内容
所有评论(0)