C++ STL详解 红黑树（一）：从基本性质到高度证明与插入调整
C++ STL详解 红黑树（一）：从基本性质到高度证明与插入调整
文章目录
前言：为什么需要红黑树
普通二叉搜索树的问题
在学习红黑树之前，我们首先需要知道它到底解决了什么问题。
对于一棵普通的二叉搜索树 BST，如果树的结构比较理想，例如：
4
/ \
2 6
/ \ / \
1 3 5 7
树的高度大约为：
log₂N
因此查找、插入等操作的时间复杂度大约为：
O(logN)
但是普通二叉搜索树并不会主动维护自己的结构。
如果按照：
1 2 3 4 5 6 7
依次插入，那么最终可能退化成：
1
\
2
\
3
\
4
\
5
此时二叉搜索树实际上已经接近链表，树高变成：
O(N)
查找、插入等操作最坏也会退化为：
O(N)
所以我们需要一种能够自动控制高度的二叉搜索树。
AVL 树是一种解决方法，而红黑树则是另一种非常经典的解决方案。
红黑树并不像 AVL 树那样严格要求左右子树高度差不超过 1，而是通过一些颜色规则间接约束树的高度，因此红黑树是一种近似平衡的二叉搜索树。原资料也强调，颜色约束能够保证任意路径不会比其他路径长出两倍以上。
一、什么是红黑树
1. 红黑树本质上仍然是 BST
首先一定要明确：
红黑树首先是一棵二叉搜索树，其次才是一棵红黑树。
假设结点保存的是 key-value：
key < 当前结点key → 去左子树
key > 当前结点key → 去右子树
红黑树在普通 BST 结点的基础上增加了一个属性：
颜色
每个结点只能是：
RED
或者：
BLACK
因此一个红黑树结点大致可以表示为：
enum Colour
{
RED,
BLACK
};
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;
};
其中 _parent 非常重要，因为插入之后需要不断向父结点、祖父结点方向调整。原资料中的结点设计同样包含 left/right/parent/color 四类结构信息。
二、红黑树必须满足哪些规则
1. 每个结点不是红色就是黑色
这是最基础的规则：
Node ∈ { RED, BLACK }
在代码中可以直接使用枚举：
enum Colour
{
RED,
BLACK
};
这样从数据结构层面就保证结点不会出现第三种颜色。
2. 根结点必须是黑色
例如：
10(B)
/ \
5(R) 15(R)
这是合法的。
但是：
10(R)
作为最终红黑树是不合法的。
实际插入过程中根可能暂时变红，因此通常在插入修复结束之后统一执行：
_root->_col = BLACK;
3. 红色结点不能拥有红色孩子
也就是说：
RED
|
RED
这种结构是不允许出现的。
因此：
红 → 红
不能连续出现。
但是：
黑 → 黑
完全可以。
例如：
10(B)
/
6(R)
/
3(R)
就违反了红黑树规则。
这一条性质非常重要，因为它限制了红色结点的数量，也是后面证明树高上界的关键。
4. 从任意结点到所有 NIL 的路径包含相同数量的黑色结点
例如：
10(B)
/ \
5(R) 15(B)
/
3(B)
我们不能仅仅观察：
10 → 5 → 3
10 → 15
而应该一直走到空结点 NIL。
在理论定义中，所有空孩子通常看作黑色的 NIL 结点。
因此更准确地说：
从任意结点出发，到它所有后代 NIL 结点的路径上，黑色结点数量必须相同。
这个性质是红黑树维持“近似平衡”的核心。
Cornell 的课程材料同样将“所有路径拥有相同黑高度”和“不允许红红相连”作为红黑树最核心的不变量。
5. NIL 结点认为是黑色
在很多 C++ 实现中，我们并不会真的创建：
NIL
结点，而是直接使用：
nullptr
但理论分析时，可以认为这些 nullptr 都对应黑色 NIL 结点。
因此：
10(B)
/ \
nullptr nullptr
实际上可以理解成：
10(B)
/ \
NIL(B) NIL(B)
这主要是为了方便统一描述红黑树路径。
三、什么叫黑高度
1. black height
理解红黑树最重要的概念之一就是：
Black Height
简称：
bh
由于红黑树规定：
从同一个结点到任意 NIL 的路径拥有相同数量的黑色结点。
因此我们可以用这个黑色结点数量描述一棵子树。
例如：
10(B)
/ \
5(R) 15(B)
/ \
3(B) 7(B)
如果从根到 NIL 的每条路径都经过相同数量的黑结点，那么这个数量就是树对应的黑高度。
注意：
不同教材对于“是否计算当前结点”和“NIL 是否计入 bh”的定义可能略有不同。
但是这些定义只会造成常数级差异，并不会影响：
h = O(logN)
这个核心结论。
四、为什么最长路径不会超过最短路径的两倍
1. 先观察最短路径
假设从根到 NIL 的每条路径都有：
bh
个黑色结点。
理论上最短的一种情况可以全部由黑结点组成：
B
|
B
|
B
|
B
路径长度大约就是：
bh
2. 再观察最长路径
因为红色结点不能连续，因此最长路径理论上只能做到：
B
|
R
|
B
|
R
|
B
|
R
|
B
也就是：
黑 红 黑 红 黑 红……
在两个黑结点之间最多插入一个红结点。
于是路径长度最多约为：
2 × bh
因此：
最短路径 >= bh
最长路径 <= 2bh
最终得到：
最长路径 <= 2 × 最短路径
这就是为什么红黑树虽然不是像 AVL 那样严格平衡，但不会发生严重倾斜。原资料也是通过“相同黑结点数量 + 不允许连续红结点”得到这一结论。
五、为什么红黑树高度不超过 2log₂(n+1)
这一部分非常重要。
很多资料会直接告诉我们：
红黑树高度为 O(logN)
但是为什么？
下面给出一个比较完整的推导。
1. 第一步：证明拥有黑高度 bh 的子树至少有多少结点
假设某棵红黑子树的黑高度为：
bh
我们考虑在满足红黑树性质的情况下，让它包含的内部结点尽可能少。
为了让结点数量最少，我们可以认为每下降一个黑高度，只保留最必要的结构。
可以证明：
n >= 2^bh - 1
其中：
n = 子树内部结点数量
bh = 黑高度
可以用数学归纳法理解。
bh = 0
此时：
n >= 0
而：
2^0 - 1 = 0
成立。
假设 bh = k 时成立
即：
n >= 2^k - 1
当黑高度增加为：
k + 1
根的左右两棵子树都至少拥有：
2^k - 1
个内部结点。
加上根：
n >= 1 + 2(2^k - 1)
整理：
n >= 2^(k+1) - 1
所以结论成立。
因此：
n >= 2^bh - 1
于是：
n + 1 >= 2^bh
两边取以 2 为底的对数：
bh <= log₂(n + 1)
2. 第二步：树高最多是黑高度的两倍
由于：
不存在连续两个红结点
所以一条根到 NIL 的路径上，红结点数量不可能超过黑结点数量太多。
极端情况下就是：
B → R → B → R → B → R
因此：
h <= 2bh
再结合：
bh <= log₂(n + 1)
得到：
h <= 2log₂(n + 1)
这就是红黑树经典的高度上界。
六、红黑树为什么能做到 O(logN)
1. 查找
红黑树仍然是 BST。
查找过程中每比较一次都会进入：
左子树
或者：
右子树
因此最多访问一条根到叶子的路径。
而：
h <= 2log₂(n + 1)
所以：
Find = O(logN)
2. 插入
首先按照 BST 规则找到插入位置：
O(logN)
之后执行变色或者旋转修复红黑树性质。
因此整体仍然为：
O(logN)
3. 删除
删除首先要找到结点，然后再修复红黑树性质，因此最坏时间复杂度同样为：
O(logN)
所以红黑树的：
查找
插入
删除
都能够保持：
O(logN)
这也是红黑树最重要的价值之一。
七、为什么新插入的结点通常要设成红色
这是红黑树插入算法中一个非常关键的设计。
假设现在有：
10(B)
/ \
5(B) 15(B)
如果我们插入一个新的黑结点：
10(B)
/ \
5(B) 15(B)
/
3(B)
左边路径立刻多了一个黑结点。
这会直接破坏：
每条路径黑色结点数量相同
这个性质。
而这个性质一旦被破坏，恢复起来比较麻烦。
如果新结点默认插成红色：
10(B)
/ \
5(B) 15(B)
/
3(R)
路径上的黑结点数量没有发生变化。
我们唯一可能破坏的是：
不能有连续红结点
而“红红冲突”可以通过：
变色
旋转
比较容易地解决。
所以：
非空红黑树插入新结点时，一般首先将新结点设为红色。
如果插入的是整棵树第一个结点，则直接把它设置为黑色根。
八、插入之后什么时候不需要调整
1. 父结点是黑色
假设插入：
10(B)
/
5(B)
/
3(R)
因为父结点：
5
是黑色，因此：
5(B) → 3(R)
没有发生红红冲突。
与此同时，新插入的是红结点，并没有改变路径上的黑结点数量。
所以：
不需要任何调整
2. 父结点是红色
如果出现：
g(B)
/
p(R)
/
c(R)
那么：
p(R) → c(R)
产生连续红色结点。
此时必须调整。
由于 p 是红色，而根最终必须是黑色，所以 p 不可能是根。
因此一定存在：
g = grandfather
同时 g 必然是黑色。
于是后面的插入修复就可以统一围绕：
c：当前结点
p：父结点
g：祖父结点
u：叔叔结点
来分析。
九、情况一：叔叔是红色——变色
1. 初始结构
假设：
g(B)
/ \
p(R) u(R)
/
c(R)
此时：
c 和 p 连续为红色
违反规则。
2. 处理方式
执行：
p → BLACK
u → BLACK
g → RED
于是：
g(R)
/ \
p(B) u(B)
/
c(R)
3. 为什么这样处理
原来经过：
g → p
和：
g → u
的路径中都有一个黑色的 g。
现在：
g
变红，而：
p
u
变黑。
因此两边路径的黑结点数量仍然保持一致。
同时：
p(R) → c(R)
的红红冲突消失。
4. 为什么还要继续向上处理
因为：
g
刚刚被变成红色。
如果：
g 的父结点也是红色
就会出现新的红红冲突。
所以需要：
cur = grandfather;
parent = cur->_parent;
把 g 当成新的 cur，继续向上处理。
这也是红黑树插入过程中唯一可能不断向根方向传播的情况。原资料对此给出的核心操作就是父亲、叔叔变黑，祖父变红，再令祖父成为新的当前结点继续向上检查。
十、情况二：叔叔为黑或不存在——单旋
此时简单变色已经不能解决问题，必须：
旋转 + 变色
1. LL 型
结构为：
g(B)
/
p(R)
/
c(R)
也就是：
p 是 g 的左孩子
c 是 p 的左孩子
形成：
LL
此时以：
g
为旋转点执行：
右单旋
得到：
p
/ \
c g
然后调整颜色：
p → BLACK
g → RED
最终：
p(B)
/ \
c(R) g(R)
红红冲突消失，黑高度保持不变。
2. RR 型
如果结构为：
g(B)
\
p(R)
\
c(R)
形成：
RR
则以：
g
执行左单旋：
p(B)
/ \
g(R) c(R)
同样执行：
p → BLACK
g → RED
即可。
十一、情况三：叔叔为黑或不存在——双旋
1. LR 型
结构为：
g(B)
/
p(R)
\
c(R)
即：
p 是 g 的左孩子
c 是 p 的右孩子
属于：
LR
首先：
以 p 为旋转点左旋
将结构转成 LL：
g
/
c
/
p
然后：
以 g 为旋转点右旋
得到：
c
/ \
p g
最后：
c → BLACK
g → RED
即：
c(B)
/ \
p(R) g(R)
原资料中的双旋处理也是先把折线结构旋成直线，再进行第二次旋转，最终让原来的 c 成为这一小棵子树的新根。
2. RL 型
结构：
g(B)
\
p(R)
/
c(R)
属于：
RL
先：
右旋 p
再：
左旋 g
最后：
c → BLACK
g → RED
即可。
十二、四种旋转情况如何快速记忆
可以归纳成下面这张表：
| 结构 | 当前结点位置 | 调整方式 | 变黑结点 |
|---|---|---|---|
| LL | 左左 | g 右旋 | p |
| RR | 右右 | g 左旋 | p |
| LR | 左右 | p 左旋 + g 右旋 | c |
| RL | 右左 | p 右旋 + g 左旋 | c |
真正写代码时不要死记四大段。
可以先判断：
parent 在 grandfather 左边还是右边？
然后再判断：
cur 在 parent 左边还是右边？
整个结构就会清楚很多。
十三、红黑树和 AVL 树有什么区别
1. AVL 树更加严格平衡
AVL 要求：
|左子树高度 - 右子树高度| <= 1
所以它的树高控制得更加严格。
2. 红黑树只保证近似平衡
红黑树不直接限制左右子树高度差，而是利用：
颜色
+
黑高度
+
禁止红红相连
间接保证：
h = O(logN)
Cornell 的课程资料也把红黑树描述为通过表示不变量保证对数级高度的平衡树。
3. 红黑树通常调整得更宽松
由于 AVL 对平衡要求更严格，插入或删除后更容易发生结构调整。
而红黑树允许一定程度的不平衡：
最长路径 <= 2 × 最短路径
因此在很多动态更新较频繁的场景下，红黑树是一种非常实用的折中方案。
十四、红黑树插入的整体思维框架
第一步：按照 BST 规则插入
小 → 左
大 → 右
第二步：新结点染红
newNode → RED
第三步：看父结点
如果：
parent == BLACK
结束。
如果：
parent == RED
发生红红冲突。
第四步：看叔叔
如果：
uncle == RED
那么：
变色
+
向上继续处理
如果：
uncle == BLACK / nullptr
那么：
旋转
+
变色
+
结束
第五步：保证根为黑
最后：
_root->_col = BLACK;
总结
红黑树真正难的地方并不是代码，而是理解它为什么能够只依靠颜色就控制树的高度。
核心只有四件事情：
1. 每条路径拥有相同数量的黑色结点
2. 红结点不能连续
3. 新结点默认插成红色
4. 红红冲突通过变色和旋转解决
其中前两条共同保证：
最长路径 <= 2 × 最短路径
进一步又可以证明：
n >= 2^bh - 1
因此：
bh <= log₂(n + 1)
而：
h <= 2bh
最终得到红黑树最重要的高度结论：
h <= 2log₂(n + 1)
也正因为如此，红黑树能够保证查找、插入、删除的最坏时间复杂度保持在：
O(logN)
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
29
0- 0
已为社区贡献27条内容
所有评论(0)