Chapter 16: Red-Black Tree Foundations
核心问题与阅读主线
std::map、std::set、std::multimap、std::multiset 必须在动态插删下同时兑现按键有序遍历与对数级查找、更新复杂度。标准库通常以红黑树落地这一契约:BST 偏序保证查找与中序遍历正确,节点颜色规则与局部旋转将树高锁死在对数上界。
全章共用代码样本(下文各节持续拆解)
全章以 std::map 索引构造与更新作贯穿材料:乱序插入 key、查 lower_bound(16),再删去内部节点 20。
#include <initializer_list>
#include <map>
#include <string>
std::map<int, std::string> index;
for (int key : {10, 5, 20, 15, 30, 25}) {
index.emplace(key, "node");
}
auto first_not_less_than_16 = index.lower_bound(16);
index.erase(20);
该样本集中验证三项底层诉求:乱序插入后按 key 升序遍历、lower_bound(16) 返回首个不小于 16 的 20,以及删去内部节点 20 后不破坏有序性与对数查找。
标准语义与复杂度基线对照 cppreference 的 std::map 页面。
16.1 BST、有序关系与平衡需求
BST 按 左 < 根 < 右 落位 key(multi 容器结合等价键放置规则)。贯穿示例插入 10, 5, 20, 15, 30, 25 后形成如下拓扑:
其中序遍历为升序 5 → 10 → 15 → 20 → 25 → 30,lower_bound(16) 也只走单条根到叶路径。但普通 BST 不约束树高——若按 1, 2, 3, 4, 5, 6 递增插入,树会退化为单链:
| 树结构 | 查找与遍历依据 | 更新后树高约束 | 最坏查找 / 更新成本 |
|---|---|---|---|
| 普通 BST | comparator 偏序分支 | 无高度不变量,有序输入退化为单链 | $O(N)$ |
| 红黑树 | 同上(保留 BST 拓扑) | 颜色规则限制最长路径不超过最短路径两倍 | $O(\log N)$ |
核心判断
评估树结构能否支撑有序关联容器:1. comparator 是否给出稳定偏序;2. 查找是否仅沿单路径推进;3. 更新后树高是否受不变量限制。普通 BST 缺第三条,红黑树补齐。
16.2 红黑树性质、节点颜色与 tree height
红黑树在 BST 节点上增加非业务状态 color,用五条不变量锁定树高:
- 二色约束:节点非红即黑。
- 根黑约束:根节点为黑。
- 叶哨兵约束:空叶子哨兵视为黑。
- 红不相邻:红节点的子节点必为黑。
- 黑高一致(black height):任一节点到其所有后代空叶子的黑节点数量相等。
最小节点形状如下(真实标准库还在外围封装 header 哨兵、allocator 节点基类、颜色位压缩存储与迭代器辅助逻辑):
enum class Color { Red, Black };
struct Node {
int key{};
Color color{Color::Red};
Node* parent{};
Node* left{};
Node* right{};
};
设节点到空叶子的黑高为 $bh$:最短路全由黑节点构成(长 $bh$),因红节点不可连续,最长路只能黑红交替(至多接近 $2 \cdot bh$),树高由此被压在 $O(\log N)$。贯穿示例插入 25 形成 20 → 30 → 25 时,允许新节点临时染红,再通过变色与旋转恢复规则。
核心判断
读源码时把节点字段拆成两层:key、value 与 parent/left/right 决定拓扑与 BST 顺序;color 对容器外部不可见,仅控制修复分支以守住高度上界。
关键事实
节点独立分配使插入删除只需重连指针与改色,无需像 std::vector 扩容那样整体搬移已有元素——这正是 map/set 迭代器稳定性的结构基础(将在后续章节展开)。
16.3 左旋、右旋与局部结构修复
左旋围绕 x 及其非空右孩子 y 展开:y 升至 x 位,x 降为 y->left,y->left 过继为 x->right;右旋为其镜像对称操作。旋转前后 A < x < B < y < C 的中序序列始终为 A, x, B, y, C,改变的只是局部高度与父子挂接关系。
rotate_left 最小实现(前提为 x != nullptr && x->right != nullptr):
void rotate_left(Node*& root, Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left) {
y->left->parent = x;
}
y->parent = x->parent;
if (!x->parent) {
root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
核查旋转源码按四组边的闭合顺序推进:
x->right = y->left(转移子树B)。- 若
y->left非空,置y->left->parent = x(回填B父指针)。 y->parent = x->parent,并将原父节点(或root)的子指针改指向y。y->left = x、x->parent = y(闭合x/y双向指针)。
贯穿示例 20 → 30 → 25 失衡时,先右旋 30 再左旋 20,将 25 提为局部根而保持 20, 25, 30 中序序列不变。
关键事实
旋转只重塑拓扑不修复颜色规则;读到 rotate_left / rotate_right 时,先核对四边重连是否保序闭合,再看调用点如何配合改色完成修复。
16.4 插入修复与删除修复
插入固定分两步:按 BST 规则将新节点 z 挂入叶子并默认染红(不改变任何路径的 black height),仅当父节点 p 同为红时,依叔父节点 u 的颜色与 z 的内外侧位置进入修复:
对照贯穿示例:插入 15(10 → 20 → 15)若父节点 20 为黑即结束;插入 25(10 → 20 → 30 → 25)若父节点 30 为红,则依叔父与内外侧分流变色或旋转。
删除分“BST 位置替换”与“黑高修复”两层:两孩子节点先用中序后继逻辑替位,再实际摘除至多只有一个非空孩子的节点(erase(20) 选后继 25 替位,物理摘除原 25 节点)。若摘除黑节点,替代位进入“少一黑高”状态,按兄弟 s 与近/远侄子颜色分三类处理:
- 兄弟
s为红:绕父旋转并交换父与s颜色,规约为黑兄弟情形。 - 兄弟
s为黑且两侄皆黑:s染红,少黑状态向父节点上推。 - 兄弟
s为黑且有红侄:一次或两次旋转加换色,局部补回黑高并终止。
| 维度 | 插入修复(双红冲突) | 删除修复(黑高缺失) |
|---|---|---|
| 触发前提 | 染红新节点 z 且父节点 p 为红 | 实际物理摘除的节点为黑色 |
| 观察角色 | 当前位 z、父节点 p、叔父 u | 当前位、兄弟 s、近侄子与远侄子 |
| 上推条件 | u 为红:父叔染黑、祖父染红上移 | s 黑且双侄黑:s 染红上移 |
| 旋转终结 | u 为黑:内侧转外侧后绕祖父旋并换色 | s 黑且有红侄:单/双旋借黑并换色 |
边界与误区
决定是否触发删除修复的不是逻辑 key(erase(20) 的 20),而是物理摘除节点(原 25)的颜色:摘红不减 black height、无需修复;把“BST 替位”与“黑高修复”拆开看,源码分支就会一一对应到 s 与侄子颜色。
16.5 lower_bound、in-order traversal 与复杂度来源
lower_bound 沿单路径下降并维护候选:遇 node->key < q 进右子树;遇 node->key >= q 记为候选,再进左子树寻找更紧凑的合格键。
对贯穿示例执行 lower_bound(16) 的搜索路径如下:
关联容器的定位接口共用同一条下降骨架,差异仅在命中判定与候选更新:
| 接口 | 目标语义 | 命中 / 候选更新条件 | 未命中返回值 |
|---|---|---|---|
find / contains | 精确匹配等价 key | 键等价即命中停止(contains 返回 bool) | end() / false |
lower_bound(k) | 首个 key >= k | node->key >= k 更新候选并向左 | end() |
upper_bound(k) | 首个 key > k | node->key > k 更新候选并向左 | end() |
有序升序遍历由中序后继驱动。next(current) 按两条路径步进(前提 current != nullptr;越过最大节点返回 nullptr,对应 end() 哨兵):有右子树取右子树最左节点;否则沿 parent 上行至首次从父节点的左孩子返回:
Node* next(Node* current) {
if (current->right) {
current = current->right;
while (current->left) {
current = current->left;
}
return current;
}
Node* parent = current->parent;
while (parent && current == parent->right) {
current = parent;
parent = parent->parent;
}
return parent;
}
next 说明迭代器只需持有 Node* 即可沿拓扑指针跳转,无需连续内存;只要节点本身未被删除,局部重连在常见实现中不会使指向它的迭代器失效(精确标准语义见后续容器章)。
核心判断
有序关联容器的正确性与复杂度来自三层协同:接口层决定候选与后继语义,BST 层每步排除半边子树,红黑颜色层将树高锁死在 $O(\log N)$。缺第三层时结果仍对,但复杂度退化为线性。
16.6 mini red-black tree 实现路径
搭建 mini 红黑树应先通“节点 → 旋转 → 插入修复 → 查找与迭代器”主干,稳定后再加入分支较多的删除修复以降低调试成本。最小实现可用黑色 nil 哨兵消除空指针分支;真实标准库常改用 header 节点保存根、最左与最右节点,支撑 begin()、end() 与反向迭代:
struct RBNode {
int key{};
Color color{Color::Red};
RBNode* parent{};
RBNode* left{};
RBNode* right{};
};
struct RBTree {
RBNode* root{};
RBNode* nil{};
};
按以下可验证顺序逐步落地:
- BST 插入:实现搜索与挂接,验证中序输出严格升序。
- 局部旋转:实现
rotate_left/rotate_right,用 3~4 节点样本验证旋转前后中序不变且父指针闭合。 - 插入修复:接入颜色与修复,插入递增序列
1, 2, 3, 4, 5, 6,确认树高非线性增长。 lower_bound:测试查询键落于已有节点之间的场景,验证候选回退。- 迭代器
next:从最小节点完整遍历至结束哨兵。
check_black_height 将颜色规则转为可执行断言,递归校验红不相邻与左右子树黑高相等(非法返回 -1):
int check_black_height(RBNode* node, RBNode* nil) {
if (node == nil) {
return 1;
}
if (node->color == Color::Red) {
if (node->left->color == Color::Red || node->right->color == Color::Red) {
return -1;
}
}
int left_height = check_black_height(node->left, nil);
int right_height = check_black_height(node->right, nil);
if (left_height < 0 || right_height < 0 || left_height != right_height) {
return -1;
}
return left_height + (node->color == Color::Black ? 1 : 0);
}
边界与误区
check_black_height 要求所有空孩子指向同一个黑色 nil 哨兵,且入口需额外断言 root == nil || root->color == Color::Black。本路径仅构建红黑树本体;comparator、重复键策略、allocator 生命周期、异常安全与 end() 哨兵将在 map / set 章节接入。
排查顺序
读标准库红黑树源码按五步剥离封装:
- 查 comparator 如何决定左右分支与等价判定;
- 查节点字段与
header哨兵如何表示颜色与begin()/end(); - 核对旋转是否保序且四组指针闭合;
- 将插入/删除修复分支映射回叔父
u或兄弟s/侄子颜色; - 将
lower_bound与operator++对应到候选下降与中序后继。
最小自检任务
基于操作序列“依次插入 10, 5, 20, 15, 30, 25 → 执行 lower_bound(16) → 删除 20”,独立回答以下三题:
- 为什么普通 BST 能返回正确的
lower_bound(16),却无法稳定承诺对数复杂度? - 左旋或右旋为什么不会改变中序遍历顺序?
- 删除
20时,为什么必须区分“BST 替换路径”与“红黑树颜色修复路径”?
本章知识点总结
- BST 偏序与遍历
左小右大的局部有序关系决定了
find、lower_bound搜索方向及中序升序遍历的正确性。 - 黑高与树高上界
红节点不可连续且任一节点到后代空叶子的 black height 一致,使最长路径至多约为最短路径两倍,树高维持 $O(\log N)$。
- 节点双层字段
key、value与parent/left/right负责拓扑定位及迭代器稳定性,color仅作为维护高度的内部修复状态。 - 旋转不变量
rotate_left/rotate_right通过四组指针重连改变局部高度,并严格保持A < x < B < y < C的中序顺序。 - 插入修复策略
新节点默认染红以保持黑高不变,仅当父节点同为红时依叔父颜色与内外侧位置执行变色上推或旋转。
- 删除修复策略
先按 BST 替位并摘除至多一子的节点,仅当物理摘除黑节点时依兄弟与侄子颜色补回缺失黑高。
- 实现与排查主线
按“节点与
nil哨兵 → 旋转(验中序)→ 插入修复(用check_black_height断言)→lower_bound/next→ 删除修复”顺序落地与读码。