Skip to main content

Chapter 16: Red-Black Tree Foundations

核心问题与阅读主线

本章导读6 个核心小节 · 附自检与总结

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 递增插入,树会退化为单链:

树结构查找与遍历依据更新后树高约束最坏查找 / 更新成本
普通 BSTcomparator 偏序分支无高度不变量,有序输入退化为单链$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;
}

核查旋转源码按四组边的闭合顺序推进:

  1. x->right = y->left(转移子树 B)。
  2. 若 y->left 非空,置 y->left->parent = x(回填 B 父指针)。
  3. y->parent = x->parent,并将原父节点(或 root)的子指针改指向 y。
  4. 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 >= knode->key >= k 更新候选并向左end()
upper_bound(k)首个 key > knode->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{};
};

按以下可验证顺序逐步落地:

  1. BST 插入:实现搜索与挂接,验证中序输出严格升序。
  2. 局部旋转:实现 rotate_left / rotate_right,用 3~4 节点样本验证旋转前后中序不变且父指针闭合。
  3. 插入修复:接入颜色与修复,插入递增序列 1, 2, 3, 4, 5, 6,确认树高非线性增长。
  4. lower_bound:测试查询键落于已有节点之间的场景,验证候选回退。
  5. 迭代器 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 章节接入。

排查顺序

读标准库红黑树源码按五步剥离封装:

  1. 查 comparator 如何决定左右分支与等价判定;
  2. 查节点字段与 header 哨兵如何表示颜色与 begin() / end();
  3. 核对旋转是否保序且四组指针闭合;
  4. 将插入/删除修复分支映射回叔父 u 或兄弟 s/侄子颜色;
  5. 将 lower_bound 与 operator++ 对应到候选下降与中序后继。

最小自检任务​

动手自检先独立判断

基于操作序列“依次插入 10, 5, 20, 15, 30, 25 → 执行 lower_bound(16) → 删除 20”,独立回答以下三题:

  1. 为什么普通 BST 能返回正确的 lower_bound(16),却无法稳定承诺对数复杂度?
  2. 左旋或右旋为什么不会改变中序遍历顺序?
  3. 删除 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 → 删除修复”顺序落地与读码。