《一文吃透红黑树：性质、插入、旋转与代码实现》

一、为什么需要红黑树

1.1 一切的起点：二叉搜索树（BST）

二叉搜索树（Binary Search Tree）的思想非常朴素：左子树的所有值都比根小，右子树的所有值都比根大。借助这个性质，查找一个元素时，我们每比较一次就能"砍掉"一半的候选范围，因此理想情况下，一棵有 n 个节点的 BST，查找、插入、删除的时间复杂度都是*O(log n)*。
听起来很美好，但关键在于"理想情况"这四个字——BST 的形态完全取决于插入顺序。

1.2 BST 的致命伤：退化

假设我们按 1, 2, 3, 4, 5 的顺序依次插入这棵 BST：

• 插入 1，它成为根；
• 插入 2，2 > 1，挂到 1 的右边；
• 插入 3，3 > 1，3 > 2，挂到 2 的右边；
• ……
  最终得到的不是一棵"树"，而是一条向右倾斜的链表：
  

此时查找 5 需要比较 5 次，和从头遍历链表没有任何区别，时间复杂度直接退化到O(n)。对于有序数据（或近似有序的数据），BST 会彻底失去意义。

1.3 第一个解法：AVL 树

为了给 BST 加上"平衡保险"，人们提出了AVL 树。它要求任意节点的左右子树高度差不超过 1，是一棵严格平衡的树。
AVL 树通过旋转，把树高牢牢控制在 O(log n)，查找性能非常稳定。但代价也随之而来：

• 由于平衡条件极其严格，插入和删除稍微打破高度差，就要立即旋转修复；
• 在频繁插入/删除的场景下，旋转次数多、维护成本高，写起来也更复杂。

也就是说，AVL 树把"查询"做到了极致，却让"修改"付出了不小的代价。

1.4 红黑树：换个思路，近似平衡

既然"高度严格平衡"太累，那能不能放松一点要求，换来实现简单、修改高效？红黑树的回答是：可以。
红黑树不再直接用"高度"来约束平衡，而是给每个节点染上红或黑两种颜色，通过一组颜色规则（也就是后面要讲的五大性质）来间接限制树高。它的平衡标准放宽为：

• 最长路径不超过最短路径的 2 倍，即树高被控制在 O(log n) 量级（近似平衡）。

1.5 红黑树就在你身边

你可能没写过红黑树，但你几乎一定用过它：

• C++ STL的 std::map、std::set（以及multimap、multiset）底层就是红黑树；
• Java的TreeMap、TreeSet，以及HashMap在链表过长时转成的红黑树；
• Linux 内核用它管理进程调度、虚拟内存区域（VMA）等大量需要有序且频繁增删的结构；
• 许多数据库和文件系统的索引也用到了红黑树的变体。

二、红黑树的五大性质

红黑树的全部"魔法"，都建立在五条看似简单的规则之上。理解了这五条，后面插入修复的每一种情况，其实都是在"想尽办法把被破坏的规则修回来"。
先把它们列出来：

1. 每个节点非红即黑；
2. 根节点是黑色；
3. 每个叶子节点（NIL / 空节点）是黑色；
4. 红色节点的子节点必须是黑色（即不能出现连续的红节点）；
5. 从任一节点出发，到它所有叶子节点的路径上，黑色节点的数目相同。

2.1 逐条理解：每条规则到底在管什么

性质 1（非红即黑）
最基础的一条，给每个节点一个二元状态。它是后面所有"变色"操作的前提。

性质 2（根为黑）
可以看成"人为规定"。它不影响平衡，只是让"黑高"这个概念有统一的起点，方便后面推导。注意：这条规则也是为什么每次插入结束后，都要把根节点强制设成黑色（对应代码 RBTree.h:181）。

性质 3（叶子 NIL 为黑）
这里的"叶子"不是我们平常说的"没有孩子的节点"，而是指所有的空指针位置。教科书里通常画成一个个黑色的 NIL 哨兵节点。把它们统一视为黑色，是为了让"每条路径黑色节点数相同"这条性质能够对所有路径成立（否则路径在真实节点处就结束了，无法统一比较）。
工程实现里我们为了省空间，一般直接用 nullptr 表示 NIL，而不真的创建哨兵节点——这是"理论定义"与"代码实现"的一个常见差异，不影响正确性。

性质 4（不能有连续红节点）
这是控制树高上界的关键。它保证了红节点不能扎堆出现，一条路径上红节点的数量必然被黑节点"夹住"，从而限制路径长度。这条规则一旦被破坏（出现"红父红子"），就是插入需要修复的信号。

性质 5（黑节点数目相同，即"黑高一致"）
这是控制树高下界、保证平衡的关键。它保证了从根到各个叶子的路径不会有的特别长、有的特别短——所有路径的"黑色骨架"长度完全一样。

性质 4 管"最长不能太长"，性质 5 管"最短不能太短"，两者一配合，就锁死了整棵树的高度范围。下面就来量化这个结论。

2.2 定义"黑高"

为了精确描述，我们引入一个概念：
黑高（black-height，记作 bh）：从某个节点出发，到任意一个 NIL 叶子节点的路径上，黑色节点的数目（不包含 NIL 本身）。
由性质 5 可知：从根节点出发，任意一条根到 NIL 的路径，黑节点数目都相等，所以整棵树的黑高 bh 是唯一确定的。

2.3 关键结论：为什么最长路径 ≤ 2 × 最短路径

现在我们分两步，分别求出路径长度的下界和上界。

第一步：最短路径有多短

一棵红黑树里，肯定存在一条全部由黑节点构成的路径（把红节点都绕开即可）。这条路上有且只有 bh 个节点，而且它不可能比这更短了——因为任何路径都至少包含 bh 个黑节点。
所以：
最短路径长度 = bh

第二步：最长路径有多长

考虑任意一条根到 NIL 的路径。它上面有 bh 个黑节点。红节点能插在哪儿？只能夹在相邻两个黑节点之间，而且根据性质 4，每两个黑节点之间最多只能放 1 个红节点（不能连续红）。
于是：

• bh 个黑节点之间，一共有 bh − 1 个空隙；
• 每个空隙最多塞 1 个红节点，所以红节点最多 bh − 1 个；
• 路径上节点总数最多为 bh + (bh − 1) = 2bh − 1。
  所以：
  最长路径长度 ≤ 2bh − 1 < 2 × bh = 2 × 最短路径长度
  这就得到了本节最重要的结论：
  最长路径 < 2 × 最短路径，我们通常宽松地写作 最长路径 ≤ 2 × 最短路径。
  也就是说，红黑树允许"最长路径差不多是最短路径的两倍"这种程度的不平衡——比 AVL 树宽松得多，但已经足够让树高保持在对数级别。

小注：这里推导出的是 2bh − 1，严谨来说是最长 < 2×最短。有些资料为了叙述简洁，直接说"红节点数最多等于黑节点数，所以最长 = 2bh"，那是把 NIL 也算进去后的近似说法，结论方向一致，不影响复杂度分析。

第三步：树高到底是多少

有了上面的结论，再补一个引理，就能把树高和节点数 n 关联起来。
引理：以任意节点 x 为根、黑高为 bh(x) 的子树，至少包含 2^bh(x) − 1 个内部节点。

把它用到整棵树（根的黑高就是 bh，节点数为 n）：
n ≥ 2^bh − 1
移项取对数，得到根到叶路径上黑节点数的上界：
bh ≤ log₂(n + 1)
而树高 h 与 bh 的关系是 h < 2bh（最长路径不超过 2 倍最短），代入得：
h < 2 · log₂(n + 1)
树高是 O(log n)！ 于是红黑树上的一切操作，都能顺理成章地达到对数级别。

2.4 结论：红黑树的复杂度

综合前面的推导：

• 树高h < 2·log₂(n+1)，即*O(log n)*；
• 因此查找、插入、删除的平均与最坏时间复杂度均为 O(log n)。
  这意味着红黑树既有 BST 的查找效率，又不会像普通 BST 那样在有序数据下退化成 O(n) 的链表。而且由于平衡要求不像 AVL 那么严格，它在插入、删除时需要的旋转次数更少——这正是它在工程中被大量采用的原因。

三、节点结构设计

红黑树的节点本质上是一个"带颜色、带父指针的二叉链表"，包含五个要素：

enumColour{RED,BLACK};template<classK,classV>structRBTreeNode{pair<K,V>_kv;// 数据：键值对RBTreeNode<K,V>*_left;// 左孩子RBTreeNode<K,V>*_right;// 右孩子RBTreeNode<K,V>*_parent;// 父节点Colour _col;// 颜色};

-pair<K,V>：存键值对而非单个值，一套代码即可同时支撑 map（用 key 排序、value 存数据）和 set，这也是 STL 中 map/set 共用底层红黑树的原因。

• _left / _right：维持 BST"左小右大"性质，是查找的基础。
• _parent：红黑树实现的关键。插入修复时要向上找祖父和叔叔，变色后还可能继续向上回溯；旋转时也要把新根重新挂回父节点。没有父指针，这些向上操作会非常麻烦。
  -_col：记录颜色，是插入修复时判断"是否需要调整"的直接依据。
  整棵树只需维护一个根指针：
  Node* _root = nullptr;

四、插入操作（核心）

这一节是整个红黑树最核心、也最烧脑的部分。不过：插入的整体思路非常朴素——先老老实实按二叉搜索树的规则把节点插进去，插完之后如果破坏了红黑树的规则，再想办法"补颜色、转树"把它修回来。
整个插入过程可以拆成三步：

1. 按 BST 规则找到位置并挂上去；
2. 把新节点的颜色设为红色；
3. 从新节点开始，向上检查并修复颜色冲突。
   我们一步步来。

4.1 第一步：按 BST 规则找位置

红黑树首先是一棵二叉搜索树，所以插入的第一步和普通 BST 完全一样：

• 如果树是空的，新节点直接当根；
• 否则从根开始比较：比当前节点小就往左走，大就往右走；
• 走到空位置，这就是新节点的归宿；
• 如果发现 key 已经存在，说明是重复插入，直接返回失败。
  这一步没有任何特殊性，唯一要注意的是：行走过程中要用一个变量记录"落点"的父节点，因为最后要把新节点挂到它下面。

4.2 第二步：新节点为什么必须染成红色

这是初学者最常问的问题：新节点明明是新的，怎么一进来就是红的？
答案藏在两条性质里：

• 如果新节点染黑：从根到它的路径上会凭空多出一个黑节点，而其他路径没变，性质 5（各路径黑节点数相同）当场被破坏。而且这种破坏往往需要大范围调整，很难修。
• 如果新节点染红：黑节点数目不变，性质 5 安全。唯一可能出问题的是性质 4——万一它的父节点也是红的，就出现了"红红相连"。
  两害相权取其轻：染红最多破坏一条局部规则，修复代价小得多。所以红黑树的约定是——新节点一律先染红。
  （顺便说一句，这也是为什么根节点要单独处理：如果新节点恰好是根，它染红就违反了"根必须黑"，所以在插入的最后会强制把根设黑。）

4.3 第三步：什么时候需要修复

插入完成后，我们从新节点开始向上检查。判断标准很简单：
只要当前节点的父节点是红色的，就说明出现了"红红相连"，需要修复。
这里有一个非常重要的前提结论：
父节点是红的，那么祖父节点必然是黑的。
为什么？因为在插入之前，这棵树是合法的红黑树。如果父节点是红的，根据性质 4，父节点的父节点（祖父）就不可能是红的，只能是黑的。有了这个结论，后面所有分析才站得住脚。
在修复过程中，我们主要关注三个角色：

• cur：当前出问题的节点（初始是新节点，后续可能上移）；
• parent：cur的父亲；
• grandfather：cur的祖父（一定存在且为黑）；
• uncle：grandfather的另一个孩子，也就是 parent 的兄弟。
  叔叔的颜色，是决定如何修复的关键分水岭。 下面分两种情况。

4.4 工具准备：左旋与右旋

在讲情况二之前，得介绍一下旋转，因为情况二要靠它来修。
旋转的本质是在不破坏 BST 性质（中序遍历顺序不变）的前提下，改变局部子树的高度和形状.它分两种：

右旋（以节点 P 为中心）

当 P 有左孩子 L 时，把 L"提"上来当新根，P 降为 L 的右孩子：

左旋（以节点 P 为中心）

当 P 有右孩子 R 时，把 R"提"上来当新根，P 降为 R 的左孩子：

你只需要记住：左旋就是把右孩子提上去，右旋就是把左孩子提上去，原来的"中间子树"（右旋里的 b、左旋里的 b）顺势接到降下来的节点上。
代码里旋转最容易出错的地方，是父指针的维护：旋转后新根要接回原来的父节点；如果 P 原本就是根，新根直接成为整棵树的根。这部分一定要仔细处理。
有了旋转这个工具，我们就能应对情况二了。

4.5 情况一：叔叔是红色 —— 只变色，不旋转

这是相对简单的情况。此时 parent 和 uncle 都是红色，grandfather 是黑色。
处理方式：

1. 把parent和uncle都改成黑色；
2. 把grandfather改成红色。

为什么这样可行？
我们把"红红冲突"从parent-cur这一层，向上转移到了grandfather和曾祖父那一层。改完之后：
- 子树内部不再有连续红；
- 各路径的黑节点数没有变化（parent、uncle变黑补充了一个黑，grandfather变红减少了一个黑，一增一减抵消）。

但麻烦在于：祖父变红了，万一祖父的父亲（曾祖父）也是红的呢？ 新的冲突又出现了。
所以情况一处理完后，我们要把cur上移到grandfather，继续循环检查。如果一直往上处理，最后grandfather变成了整棵树的根，那就直接把根染黑，问题彻底解决。

4.6 情况二：叔叔是黑色或不存在 —— 旋转 + 变色

这时靠变色已经解决不了了，必须旋转。根据 cur 相对 parent 的位置，再细分成四种情况，其实就是大家常说的 LL、LR、RR、RL。
我们以 parent 是祖父的左孩子 为例：

LL 型：cur是parent的左孩子
形状是一条向左的直线。做法：

• 以grandfather为中心右旋；
• 把parent染黑，grandfather染红。
  

RL 型：cur是parent的左孩子
形状是先右后左的折线。做法：

• 先以parent右旋，
• 再以grandfather左旋，
• cur染黑、grandfather染红
  ![[Pasted image 20260927195056.png]]
  对称的 RR、LR 型
  如果parent是祖父的右孩子，就是上面两种情况的镜像：
• RR 型（cur是parent右孩子）：以grandfather左旋，parent染黑、grandfather染红；
• LR 型（cur是parent右孩子）：先以parent左旋，再以grandfather右旋，cur染黑、grandfather染红。
  记法：先看parent在祖父的哪边，决定最后往哪个方向旋（左孩子 → 右旋，右孩子 → 左旋）；再看cur在parent的哪边，决定要不要先"掰直"（和parent同向就是直线，反向就是折线，折线需要先转一次）。这样四种情况就不必死记硬背了。

一个重要结论：情况二处理完后，整棵子树的根变成了黑色，不会再和上层产生红红冲突，所以修复到此结束，可以直接跳出循环。这也是它和情况一的根本区别——情况一要接着往上查，情况二不用。

4.7 收尾：保证根是黑色

不管前面经历了多少轮变色和旋转，插入的最后都做一件事：
把根节点强制染成黑色。
这一步兜住了所有情况：无论是空树插入的第一个节点，还是情况一一路"甩锅"甩到根节点，都能被这一步统一修正。同时也保证了根节点永远是黑的。

4.8 四种情况速查表

五、正确性验证：怎么证明自己写对了

红黑树的插入逻辑分支多、旋转容易写错，光靠"我看起来是对的"远远不够。学数据结构时养成一个好习惯：写完核心操作，立刻写一个验证函数，用代码来判断这棵树到底是不是红黑树。

5.1 为什么要单独写验证函数

插入过程中，我们一边变色、一边旋转，很容易出现下面这些隐蔽的错误：

• 某次旋转之后，父指针没接对，树的结构已经悄悄坏了；
• 某条路径上黑节点数比另一条多了一个，性质 5 被破坏；
• 出现了一对相邻的红节点，性质 4 被破坏。
  这些问题肉眼几乎看不出来，用一个自动化的校验函数把它们查出来，是最省事的办法。

5.2 验证思路：只需要检查哪几条性质

回顾五大性质，逐一分析：

• 性质 1（非红即黑）：枚举天然保证，不用查；
• 性质 3（NIL 为黑）：用 nullptr 表示 NIL 时，逻辑上自动成立，不用查；
• 性质 2（根为黑）：单独判断；
• 性质 4（不能连续红）：递归时检查；
• 性质 5（各路径黑节点数相同）：递归时检查。
  所以验证函数真正要做的，就是检查性质 2、4、5。

5.3 第一步：求"参考黑高"

性质 5 要求"每条路径黑节点数相同"，可怎么比较呢？我们需要一个基准值。
最简单的做法：先随便找一条路径（比如从根一直向左走到 NIL），数一数经过了多少个黑节点，把它当作参考值 refNum。因为如果这棵树真的合法，所有路径的黑节点数都该等于它；如果有哪条路径不一样，就说明出问题了。

refNum=0cur=根while(cur 不为空):ifcur 是黑色:refNum+=1cur=cur->_left

同时别忘了先判断根：根是红色直接返回 false（性质 2）。

5.4 第二步：递归校验整棵树

有了参考值，就可以从根开始递归，一路往下比较：

bool_Check(Node*root,intblackNum,intrefNum){// 1. 走到 NIL，说明这条路径结束了if(root==nullptr){if(blackNum!=refNum)// 性质 5：黑节点数和参考值不符returnfalse;returntrue;}// 2. 性质 4：当前是红节点，且父节点也是红 → 连续红if(root->_col==RED&&root->_parent->_col==RED)returnfalse;// 3. 沿途统计黑节点if(root->_col==BLACK)++blackNum;// 4. 左右子树都要满足return_Check(root->_left,blackNum,refNum)&&_Check(root->_right,blackNum,refNum);}

配合一个对外接口：

boolIsBalance(){if(_root==nullptr)returntrue;if(_root->_col==RED)returnfalse;// 参考值intrefNum=0;Node*cur=_root;while(cur){if(cur->_col==BLACK){++refNum;}cur=cur->_left;}returnCheck(_root,0,refNum);}

思路很清晰：一边往下走，一边把"已经路过的黑节点数" blackNum 带着，走到 NIL 时和参考值一比较，就能判断每条路径的黑高是否一致。

# 结语

回过头看，我们这一路其实是在回答一个问题：怎样让二叉搜索树"永远别退化"？

• 普通 BST 把平衡交给了运气，有序数据一来就退化成链表；
• AVL 树用严格的"高度差 ≤ 1"强行平衡，代价是插入删除时频繁旋转；
• 红黑树则换了个思路——不直接管高度，而是给节点染色，用五条性质间接把树高压在 O(log n)。
  整篇文章的脉络，其实就是围绕这五条性质展开的：

1. 性质 4（不能连续红） 限制了最长路径；
2. 性质 5（各路径黑节点数相同） 限制了最短路径；
3. 两者一夹，就有了"最长路径 < 2 × 最短路径"这个核心结论，进而推出树高 O(log n)；
4. 插入时，新节点一律染红以减小破坏，再从下往上修复；
5. 修复只看叔叔的颜色：叔叔红就变色、把冲突上移，叔叔黑就旋转、一次解决；
6. 最后，永远别忘了把根染黑。
   谢谢大家观看, 感兴趣的朋友欢迎评论讨论!!!