Chapter 16: Red-Black Tree Foundations

有序关联容器要同时交付三个能力：按 key 查找、按 key 插入删除、按 key 从小到大遍历。std::map、std::set、std::multimap、std::multiset 的公开接口暴露的是 key ordering 和对数复杂度；常见实现形状会使用红黑树这类自平衡二叉搜索树来支撑这些承诺。std::map 的接口说明可以从 cppreference 的 std::map 页面 回溯：它是按比较函数排序的关联容器，查找、插入和删除具有对数复杂度，常见实现是红黑树。

本章要建立的判断能力是：看到一个有序关联容器操作时，能把它还原成树上的搜索路径、局部旋转、颜色修复和中序遍历。这样读 map / set 源码时，lower_bound、迭代器递增、插入修复和删除修复就有了共同的结构入口。

贯穿本章的材料是一段小型索引构造过程。我们把整数 key 插入一个有序索引，然后查询第一个不小于 16 的元素，再删除一个内部节点。示例使用 std::map 表达接口现象，正文用红黑树解释背后的常见实现形状。

#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);

这段代码的关键现象有三个。插入顺序是 10, 5, 20, 15, 30, 25，遍历顺序会按 key 升序输出。lower_bound(16) 要返回 key 为 20 的位置。删除 key 为 20 的节点后，其余节点仍保持升序遍历，并继续支持后续对数查找。红黑树的工作就是把这些接口现象压缩成稳定的局部不变量。

16.1 BST、有序关系与平衡需求

二叉搜索树（Binary Search Tree, BST）先解决“有序 key 如何落到树形结构里”的问题。对任意节点 x，左子树所有 key 小于 x.key，右子树所有 key 大于 x.key；在 multi 容器里，等价 key 的放置策略还要结合重复键规则，本章先使用唯一 key 建立主干。

在贯穿示例中，插入 10, 5, 20, 15, 30, 25 时，普通 BST 可以得到这样的形状：

这棵树已经满足有序关系。对它做中序遍历，访问顺序是 5 → 10 → 15 → 20 → 25 → 30，这正对应有序关联容器迭代器的升序遍历语义。查找 key 16 时，从根节点 10 开始，16 大于 10，进入右子树；16 小于 20，记录 20 作为候选，再进入左子树；16 大于 15，继续向右，最后空路径结束，候选 20 就是 lower_bound(16) 的返回位置。

BST 的问题出现在高度。查找、插入、删除都沿根到叶子的路径推进，成本受树高控制。若 key 按 1, 2, 3, 4, 5, 6 依次插入，普通 BST 会退化成单链：

这时查找 6 需要走过所有节点，复杂度退化为线性。STL 有序关联容器的接口要求是对数级查找、插入和删除，因此底层结构需要在每次更新后维护高度约束。红黑树把“高度受控”拆成颜色规则和局部修复，使插入删除仍然只沿一条搜索路径加少量旋转完成。

判断一个树结构能否支撑有序容器复杂度，可以按三个问题检查：第一，key 是否通过 comparator 形成稳定顺序；第二，查找路径是否只依赖左右子树大小关系；第三，更新后树高是否被某种不变量限制。普通 BST 只回答前两个问题，红黑树补上第三个问题。

16.2 红黑树性质、节点颜色与 tree height

红黑树在 BST 节点上增加一个颜色字段。颜色不是业务数据，它是维护高度的实现状态。常见教学表达会使用五条规则：节点为红或黑；根节点为黑；空叶子哨兵视为黑；红节点的子节点为黑；从任意节点到其所有后代空叶子的黑节点数量相同。最后一条中的黑节点数量通常称为 black height。

最小节点形状可以写成下面的简化代码。真实标准库实现还会把 header 哨兵、allocator 节点基类、压缩存储、迭代器辅助逻辑放在周围；本段代码只表达红黑树需要的对象关系。

enum class Color { Red, Black };

struct Node {
    int key{};
    Color color{Color::Red};
    Node* parent{};
    Node* left{};
    Node* right{};
};

颜色规则限制树高的方式可以从一条根到叶子的路径看出。红节点不能连续出现，所以任意一条路径上，红节点数量至多接近黑节点数量。又因为从同一节点到所有空叶子的黑节点数量相同，最短路径也有同样数量的黑节点。于是最长路径最多约为最短路径的两倍。这个约束足以把树高限制在对数级范围内。

回到贯穿示例，插入 25 后，如果普通 BST 的局部形状是 20 → 30 → 25，这条路径右侧变深。红黑树允许临时出现红色新节点，然后通过重新染色和旋转恢复规则。关键点是：颜色规则不改变 key 的中序顺序，只限制结构倾斜程度。红黑树保持的主不变量可以概括为“BST 顺序负责查找正确性，颜色规则负责高度上界”。

源码阅读时要把红黑树节点分成两类字段。key、value、左右指针和父指针决定树的拓扑与数据位置；color 决定修复逻辑该进入哪条分支。map / set 的标准语义看不到颜色字段；颜色字段只存在于实现内部，用来兑现复杂度承诺。

红黑树的高度约束也解释了为什么它适合节点式容器。节点独立分配后，插入删除主要重连指针和修改颜色，已有元素对象无需像 vector 扩容那样整体搬移。这个性质会在下一章解释 map / set 的迭代器稳定性时继续使用。

16.3 左旋、右旋与局部结构修复

旋转是红黑树修复结构倾斜的基本动作。左旋围绕某个节点 x 和它的右孩子 y 展开：y 上升到 x 原来的位置，x 变成 y 的左孩子，y 原来的左子树转移为 x 的右子树。右旋是对称动作。

左旋的核心约束是保持中序顺序。假设局部结构中 A < x < B < y < C，左旋前后中序遍历都仍然是 A, x, B, y, C。改变的是局部高度和父子关系。

简化左旋代码如下。代码省略 allocator、哨兵 header 和边界封装，只保留需要读懂源码的指针关系。

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 改成 y->left，这是子树 B 的转移。第二条边是 B 的父指针改回 x。第三条边是 y 接到 x 原来的父节点下面。第四条边是 x 接到 y->left。四条边全部更新后，局部 BST 顺序保持，父指针闭合。

在贯穿示例中，若插入 25 造成 20 的右子树左侧变深，修复过程可能先对 30 做右旋，再对 20 做左旋。两次旋转合起来把中间 key 25 提升到局部根位置。中序顺序仍然是 20, 25, 30，局部高度分布被重新平衡。

旋转本身不负责所有红黑规则。它只改变形状；颜色变化决定规则是否恢复。源码中看到 rotate_left 或 rotate_right 时，应先确认它有没有破坏中序顺序，再看调用点如何配合颜色修改完成插入或删除修复。

16.4 插入修复与删除修复

红黑树插入分成两步：先按 BST 规则把新节点插到叶子位置，再把新节点标红并修复颜色规则。新节点使用红色有一个直接好处：插入红节点不会增加任何根到空叶路径上的黑节点数量，因此 black height 先保持稳定。真正需要修复的主要情况是父节点也为红，导致红节点连续。

插入修复的判断对象有三个：新节点 z、父节点 p、叔父节点 u。若 p 为黑，修复结束。若 p 为红，祖父节点必然存在，修复根据 u 的颜色和 z 的内外侧位置进入不同动作。

这个流程解释了贯穿示例中的插入路径。插入 15 时，搜索路径是 10 → 20 → 15。如果新节点父节点 20 为黑，插入结束。插入 25 时，搜索路径是 10 → 20 → 30 → 25。若父节点 30 为红，就需要看叔父节点和内外侧位置。叔父为红时优先重新染色，把问题向上推；叔父为黑时使用旋转把局部结构调平。

删除修复比插入修复更难读，因为删除黑节点可能减少某条路径上的 black height。实现通常先按 BST 删除规则处理节点位置：若目标节点有两个子节点，先用中序后继替换目标位置，再实际删除至多只有一个非空孩子的节点。之后若被移走的颜色是黑色，就进入删除修复。

删除修复的核心状态可以称为“当前位置缺少一个黑高度”。修复时观察兄弟节点 s、兄弟的近侄子和远侄子。若兄弟为红，先旋转并换色，把兄弟转成黑色兄弟情形。若兄弟为黑且两个侄子都为黑，兄弟染红，缺失向父节点上移。若至少一个侄子为红，通过一次或两次旋转加重新染色，把缺失在当前局部消除。

贯穿示例中删除 key 20 时，20 有左右子树。常见 BST 删除会选取中序后继 25，把 25 对应节点挪到 20 的逻辑位置，然后实际删除原来的 25 节点位置。红黑树关心的是“实际从树上摘掉的节点颜色”。若摘掉红节点，black height 没有变化；若摘掉黑节点，删除修复必须补回这个黑高度。

读删除源码时，先把“选择替换节点”和“修复红黑规则”分开。前者服务 BST 顺序，保证遍历结果仍然升序；后者服务高度约束，保证后续查找仍然是对数级。混在一起读会让删除修复显得像随机分支，拆成这两层后，每个分支都能对应到兄弟颜色和侄子颜色。

16.5 lower_bound、in-order traversal 与复杂度来源

lower_bound 的语义是返回第一个 key 不小于查询 key 的位置。树形实现不需要完整遍历；它在从根向下搜索的过程中维护一个候选答案。遇到当前节点 key 小于查询 key 时，答案一定在右子树；遇到当前节点 key 大于或等于查询 key 时，当前节点可以成为候选，然后继续去左子树寻找更小的合格节点。

对贯穿示例执行 lower_bound(16) 的路径如下：

这个过程只走一条根到叶子的路径，因此复杂度来自树高。红黑树把树高控制在对数级，lower_bound 才能获得对数复杂度。find、contains、upper_bound 也都使用类似的路径判断，只是候选更新规则不同。

中序遍历负责把树结构转成迭代器顺序。对唯一 key 有序树，中序遍历顺序就是从小到大。迭代器的 ++ 操作可以用“当前节点的后继”解释：若当前节点有右子树，后继是右子树中最左节点；若没有右子树，就沿父指针向上，直到第一次从某个父节点的左子树返回，该父节点就是后继。

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 展示了节点式有序容器迭代器的一个重要来源：迭代器通常可以保存节点指针，然后通过父指针、左指针和右指针移动。它无需知道容器中元素的物理连续位置。插入和删除通过局部指针重连维护树结构，只要某个节点未被删除，指向它的迭代器在常见有序容器实现中就可以继续定位同一元素；具体标准语义会在 map / set 章节中展开。

复杂度判断应分成三层。第一层是接口层：lower_bound 返回有序范围中的第一个合格位置。第二层是结构层：BST 搜索路径每一层排除半边子树。第三层是不变量层：红黑规则限制路径长度。缺少第三层时，接口仍能返回正确结果，但复杂度无法稳定成立。

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，用一个固定三节点或四节点局部结构验证旋转前后中序结果相同。第三步加入颜色字段和插入修复，插入递增序列 1, 2, 3, 4, 5, 6，确认树高没有线性增长。第四步实现 lower_bound，用查询 key 落在节点之间的场景验证候选更新。第五步实现迭代器 next，确认它能输出完整升序序列。

mini 实现的核心检查函数应直接验证红黑规则。检查函数返回当前子树 black height；若左右子树 black height 不同，报告错误；若红节点拥有红孩子，报告错误；若根节点为红，报告错误。这个检查函数比单纯打印树形更可靠，因为它把颜色规则变成了可执行断言。

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);
}

这段检查代码是教学简化版本。它假设 nil 哨兵存在，并且所有叶子指针都指向同一个 nil。真实实现还要处理 allocator 分配、节点构造析构、异常安全、比较器、重复键策略和迭代器 end 哨兵。本章 mini 路径只负责建立红黑树本体；到 map / set 章节时，再把 key/value、comparator、allocator 和容器接口接上。

从源码阅读角度看，mini red-black tree 的可迁移判断顺序是：先确认 comparator 如何决定左右分支，再确认节点字段如何表达父子关系和颜色，再检查旋转是否保持中序顺序，再读插入删除修复如何恢复颜色规则，最后把 lower_bound 和迭代器递增映射到搜索路径与中序后继。按这个顺序读，源码中的模板封装和 allocator 细节就不会遮住树结构主线。

最小自检任务

给定下面这组操作：按顺序插入 key 10, 5, 20, 15, 30, 25，然后执行 lower_bound(16)，最后删除 key 20。请回答三个问题：

• 为什么普通 BST 能返回正确的 lower_bound(16)，但无法稳定承诺对数复杂度？
• 左旋或右旋为什么不会改变中序遍历顺序？
• 删除 key 20 时，为什么需要先区分 BST 替换路径和红黑树颜色修复路径？

答案要点

普通 BST 的左右子树有序关系足以支持 lower_bound(16)：搜索到 10 时进入右子树，搜索到 20 时记录候选，搜索到 15 时继续向右，空路径结束后返回候选 20。复杂度受树高控制；普通 BST 在有序插入等输入下可能退化成单链，路径长度变成线性。红黑树通过颜色规则限制最长路径和最短路径的比例，使查找路径保持对数级。

旋转只改变局部父子关系，不改变局部 key 的相对大小。以左旋为例，旋转前局部中序是 A, x, B, y, C，旋转后仍然是 A, x, B, y, C。因此旋转可以调整高度和局部根位置，同时保持 BST 搜索语义。

删除 key 20 时，若节点有两个子节点，BST 层通常先找中序后继 25 来维持有序关系。真正从树上摘掉的节点可能是原后继位置的节点。红黑树层随后根据被摘掉节点的颜色决定是否进入删除修复；红色节点摘除不会减少 black height，黑色节点摘除会触发兄弟、侄子和父节点参与的颜色与旋转修复。

本章知识点总结

• BST 顺序：左子树、当前节点、右子树的 key 顺序决定查找和中序遍历的正确性。
• 高度成本：树形查找、插入和删除的成本受根到叶子的路径长度控制。
• 平衡需求：有序关联容器的对数复杂度需要树高约束支撑。
• 节点颜色：红黑树用颜色字段维护高度不变量，颜色不属于业务数据。
• 黑高约束：从同一节点到后代空叶子的黑节点数量一致，使最长路径受到限制。
• 旋转动作：左旋和右旋通过局部指针重连调整高度，并保持中序顺序。
• 插入修复：新节点先按 BST 规则插入为红色，再根据父节点、叔父节点和内外侧位置修复颜色规则。
• 删除修复：删除先处理 BST 替换位置，再根据实际摘除节点的颜色恢复 black height。
• lower_bound：树形 lower_bound 在搜索路径上维护候选节点，返回第一个不小于查询 key 的位置。
• 中序后继：迭代器递增可以通过右子树最左节点或沿父指针上行找到后继。
• 复杂度来源：接口语义来自有序关系，对数复杂度来自红黑树高度约束。
• 实现顺序：mini 红黑树应先实现 BST 搜索、旋转和插入修复，再补查找接口、迭代器和删除修复。
• 源码阅读：阅读有序容器实现时，应按 comparator、节点字段、旋转、修复、查找和迭代器的顺序定位主线。