高级数据结构-04：红黑树

红黑树

约束

红黑树是一类带颜色标记的二叉搜索树。它将外部节点（代码中的 NULL 引用）视为叶子节点，使整棵树在逻辑上成为真二叉树。合法红黑树满足以下约束：

1. 树根约束：根节点为黑色。
2. 外部节点约束：所有外部节点，即叶子末端的 NULL 空节点，均被显式或隐式定义为黑色。
3. 红色节点约束：如果内部节点为红色，则其父节点和孩子节点都必须为黑色，因此任意根到叶路径上不能出现连续红节点。
4. 黑深度约束：从任意节点到其所有后代外部节点的简单路径上，经过的黑色节点数相等。该数量称为该节点或子树的黑高度。

红黑树可以视为四阶 B-树（即 2-3-4 树）在二叉树形态下的一种等价实现。通过拓扑变换，每一棵红黑树都可以被映射为一棵四阶 B-树。

将红黑树中的红色节点在逻辑上向上提升，使其与黑色父节点处于同一高度。由黑色父节点和红色孩子组成的局部分支，会被压缩为一个 B-树内部节点。规则 3 限制红色节点不能连续相邻，规则 4 保证各路径黑深度相等，因此这种合并结果对应一棵平衡的四阶 B-树。

根据黑节点与红孩子的数量、位置，红黑树局部结构可分为以下四类，并分别对应四阶 B-树中的内部节点状态：

红黑树局部形态	关键码数量	对应四阶 B-树节点	结构与等价性
单黑节点（无红孩子）	1 个	2-节点	孤立的黑节点，两侧的指针分别指向较小的子树。
黑节点 + 左侧单红孩子	2 个	3-节点	左倾的红黑节点对，在 B-树中被视为包含两个关键码的单体节点。
黑节点 + 右侧单红孩子	2 个	3-节点	右倾的红黑节点对，同样对应于 B-树中的 3-节点。
黑节点 + 左右双红孩子	3 个	4-节点	满载的超级节点，在四阶 B-树中达到容量上限，若再插入则会引发节点分裂（上溢）。

红黑树中的重染色与旋转，可以理解为 B-树动态更新中的节点分裂、合并与借用。红黑树用二叉结构表示多叉 B-树节点，同时保留对数级渐近复杂度。

树高边界

红黑树属于自平衡二叉搜索树（BBST），可以保证基本操作在最坏情况下仍保持对数级。包含 $n$ 个内部节点的红黑树 $T$，其高度 $h$ 被限制在 $\mathcal{O}(\log n)$。

插入算法

双红

执行插入时，算法先按普通二叉搜索树规则查找插入位置，并将新关键码 $e$ 挂到底层成为新叶子节点，记为 $x$。为了不改变各路径黑高度，新插入节点默认染为红色。

节点染红后，规则 1、2、4 仍能保持。但如果新节点 $x$ 的父节点 $p = x\text{->parent}$ 也是红色，就出现连续红节点，违反规则 3。该状态称为双红，即 $p\text{->color} == x\text{->color} == \text{RED}$。

新节点默认染红，是因为红节点不会增加任何根到外部节点路径上的黑节点数量，因此不会破坏最难维护的黑高度约束。如果一开始把新节点染黑，那么只有经过该新叶子的路径黑高度增加，修复范围会更大。也就是说，插入算法选择先保住规则 4，再处理可能出现的规则 3 双红冲突。

双红发生后，需要沿路径向上执行修正。算法考察四个局部节点：冲突红节点 $x$、红父节点 $p$、祖父节点 $g = p\text{->parent}$（由于 $p$ 为红，$g$ 必然存在且为黑），以及叔父节点 $u = \text{uncle}(x) = \text{sibling}(p)$。根据叔父节点 $u$ 的颜色，双红修正分为两类。

以下为泛型面向对象层面的插入代码实现，展示了搜索、节点创建以及调用双红修正的过程。

// 插入 e，并返回树中保存 e 的节点位置。
template <typename T> BinNodePosi<T> RedBlack<T>::insert(const T & e) {
    // search 返回目标位置引用；若查找失败，_hot 会记录待插入位置的父节点。
    BinNodePosi<T> & x = search( e );
    // 若键已存在，红黑树集合语义下不重复插入。
    if ( x ) return x;

    // 创建红色新节点：红节点不会增加任一路径的黑高度。
    x = new BinNode<T>(e, _hot, NULL, NULL, 0 );
    // 维护节点总数。
    _size++;

    // x 可能会在修复中旋转换位，因此先保存插入节点地址。
    BinNodePosi<T> xOld = x;
    // 若出现父子连续红节点，由 solveDoubleRed 恢复红黑树性质。
    solveDoubleRed ( x );
    // 返回最初插入的节点，而不是旋转后的局部根。
    return xOld;
} // 返回时树中一定包含关键码 e。

叔父节点为黑（RR-1）

当叔父节点 $u$ 为黑色时（外部 NULL 节点也视为黑色），即 $u\text{->color} == \text{BLACK}$，可以通过 Zig-Zig 或 Zig-Zag 方式处理。

映射到四阶 B-树模型中，该情形等价于在已有 3-节点中插入新的红关键码，使原黑关键码不再位于节点中央，形成 RRB 或 BRR 结构。

此时执行局部 3+4 重构。无论 $x, p, g$ 当前形成 zig-zig 还是 zig-zag，重构都按中序顺序重新排列三个关键码，并将颜色调整为“红-黑-红”。

在指针调整上，居中并提升为局部子树新根的节点 $b$ 染为黑色，其左右孩子 $a$ 与 $c$ 染为红色。从 B-树视角看，该过程将偏向一侧的三个关键码重组为居中分布。调整后双红被消除，局部最高点为黑色，黑高度不变，因此缺陷不会继续向上传播。该分支只需 $\mathcal{O}(1)$ 次旋转和重染色。

RR-1 可以局部终止，是因为旋转后的局部根为黑色，且这一小块子树对外呈现出的黑高度与修复前保持一致。外层祖先只看到“这棵子树还是同样黑高度的一棵合法红黑子树”，因此不需要继续向上调整。

叔父节点为红（RR-2）

当叔父节点 $u$ 为红色时，即 $u\text{->color} == \text{RED}$，在 B-树模型中表示原超级节点已经包含两个红关键码和一个黑关键码。新的红关键码 $x$ 插入后，该超级节点将包含 $g$、$p$、$u$、$x$ 四个关键码，超过四阶 B-树单节点最多 3 个关键码的容量，等价于触发上溢。

算法通过模拟 B-树节点分裂处理该上溢：

1. 将发生冲突的父节点 $p$ 与红叔父节点 $u$ 同时由红色翻转为黑色。在 B-树中，这等价于将原节点分裂为两个低层节点。

2. 将居中的祖父节点 $g$ 由黑色翻转为红色。等价模型中，这表示将居中关键码 $g$ 向上进位，并合并到父层节点。

操作后，祖父节点 $g$ 变为红色。若 $g$ 的父节点也为红色，则分裂产生的新关键码在上一层继续引发冲突，即上溢向上传递。此时只需将 $g$ 视为新插入的红色节点，通过尾递归或迭代继续执行双红修正。

该过程持续到双红冲突被消除，或上升到树根。若节点 $g$ 到达根位置，按照规则 1 需要将其转回黑色。这对应 B-树根节点分裂，也是红黑树全局黑高度增加一层的唯一途径。

以下为 solveDoubleRed 方法源码。

RR-2 的本质不是“旋转”，而是“颜色翻转”。父亲和叔父变黑，相当于 B-树中分裂出的两个低层节点；祖父变红，相当于把中间关键码向父层上送。由于这个上送动作可能让上一层也装不下，所以 RR-2 才有可能继续向上传播。

// 修复由节点 x 引发的双红冲突。
template <typename T> void RedBlack<T>::solveDoubleRed(BinNodePosi<T> x) {
    if (IsRoot(*x)) {
        // 若冲突传播到根，将根染黑即可满足根节点规则。
        _root->color = RB_BLACK;
        // 根由红转黑时，整棵树黑高度增加一。
        _root->height++;
        return;
    }
    // p 是 x 的父节点；x 非根时 p 必然存在。
    BinNodePosi<T> p = x->parent;
    // 父节点为黑时不存在连续红节点，修复结束。
    if (IsBlack(p)) return;

    // 父节点为红，必然需要检查祖父 g 与叔父 u。
    BinNodePosi<T> g = p->parent;
    // u 是 p 的兄弟节点；空外部节点按黑色处理。
    BinNodePosi<T> u = uncle(x);

    if (IsBlack(u)) {
        /* === RR-1: 叔父 u 为黑（或 NULL）=== */
        // x 与 p 同侧时，p 会成为局部重构后的根。
        if (IsLChild(*x) == IsLChild(*p))
            p->color = RB_BLACK;
        else
            // x 与 p 异侧时，x 会成为局部重构后的根。
            x->color = RB_BLACK;

        // 原祖父 g 下沉为红节点，保持局部黑高度不变。
        g->color = RB_RED;

        // gg 是局部子树旋转前的父节点，用于重接局部新根。
        BinNodePosi<T> gg = g->parent;
        // rotateAt 统一处理 zig-zig、zig-zag、zag-zig、zag-zag 四类局部形态。
        BinNodePosi<T> r = FromParentTo(*g) = rotateAt(x);
        // 局部新根 r 的父指针恢复为原曾祖父 gg。
        r->parent = gg;
    } else {
        /* === RR-2: 叔父 u 为红 === */
        // 父节点与叔父节点同时转黑，等价于 B-树节点分裂出的两个低层节点。
        p->color = RB_BLACK; p->height++;
        u->color = RB_BLACK; u->height++;

        // 非根祖父转红，表示中间关键码向上一层传递。
        if (!IsRoot(*g)) g->color = RB_RED;

        // g 转红后可能与其父节点继续构成双红，因此递归向上修复。
        solveDoubleRed(g);
    }
}

算法复杂度

执行时间开销的评估，详见下表：

节点状态条件	局部旋转次数	节点染色次数	后续系统状态与调整走向
u 为黑	1~2 次	2 次	重构消除冲突，黑高度不变，整个红黑树调整随即完成。
u 为红	0 次	3 次	无旋转操作；可能在祖父处再次出现双红冲突，但必然向上攀升两层。

重构与染色均为常数时间，向上递进层数受树高 $h$ 限制。因此，RedBlack::insert() 的整体运行时间为 $\mathcal{O}(\log n)$。插入过程中最多发生一次局部重构，即 1 到 2 次旋转，其余为自底向上的常数级染色迭代。

构建实例

下面将数值 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 按升序插入一棵初始为空的红黑树。该序列会使普通二叉搜索树退化为链表，但红黑树可通过旋转与染色维持树高约束。

1. Insert 1：节点被作为叶子插入并染红。系统立即意识到它是全树的 root，因此根据规则 1 将其翻转回黑色。

   

2. Insert 2：作为节点 1 的右孩子插入并染红。其父节点（1）是黑色，不存在双红冲突，操作完成。

   

3. Insert 3：作为节点 2 的右孩子插入并染红。此时引发双红（3 的父节点 2 是红色）。检查叔父节点（NULL，故为黑色）。此时判定为同侧的 zig-zig 情况。算法进行单旋（Rotate P around G，即节点 2 绕节点 1 左旋），并将父节点 2 染黑，祖父节点 1 染红。至此，节点 2 成为根，1 和 3 分别为其左右红孩子。

   

4. Insert 4：由于示例采取特定的自顶向下遍历调优策略，在向下遍历寻找插入点时，提前发现节点 2 带有一对红孩子（1 和 3）。为避免随后的上溢，系统实施预发性翻转：将节点 2 染红，将 1 和 3 染黑。接着发现 2 是树根，立刻将其转回黑色。随后节点 4 顺利作为 3 的右红孩子插入，其父节点（3）为黑色，无冲突产生。

   

5. Insert 5：作为 4 的红孩子插入。父节点 4 为红，产生双红。节点 5 相对于祖父（3）处于外侧。叔父（节点 1 的右侧空孩子）为黑。系统执行父辈和祖父辈之间的旋转（节点 4 绕节点 3 左旋），并重新染色，最终 4 成为子树新根且为黑色，3 和 5 为其左右红孩子。

   

6. Insert 6：向下遍历路径中发现节点 4 带有双红孩子（3 和 5）。触发向下途中的预染：节点 4 转红，3 和 5 转黑。节点 4 的父节点（2）是黑色，不引发上层问题。随后节点 6 作为 5 的红孩子插入，父节点（5）已黑，直接完成插入。

   

7. Insert 7：作为 6 的红孩子插入。引发双红。执行旋转（6 绕 5 左旋）和染色。节点 6 成为黑色子树根，5 和 7 为其左右红孩子。

   

   

8. Insert 8：下探途经节点 6，发现其拥有双红孩子（5 和 7）。预染：6 变红，5 和 7 变黑。然而，节点 6 的父节点（4）此时也是红色的。系统必须针对这起在更高中层爆发的双红执行旋转。此时节点 6 位于祖父节点 2 的右树外侧，通过将 4 绕 2 进行左旋，并配合染色，完成全树结构的修复。随后节点 8 顺利在底端作为 7 的红孩子插入，无冲突。

   

   

9. Insert 9：下探时发现节点 4 拥有双红孩子（2 和 6）。预染：4 变红，2 和 6 变黑。由于 4 此刻是树的根节点，系统随即将其转回黑色。9 被作为 8 的红孩子插入，引发底层双红，经过常规旋转与染色修正。

   

   

10. Insert 10：下探发现 8 有双红孩子（7 和 9），执行预染（8 变红，7 和 9 变黑）。此时 8 的父节点（6）为黑，无异常。10 作为 9 的红孩子插入，父节点（9）为黑，操作完成。

    

11. Insert 11：作为 10 的红孩子插入，引发底层双红。通过单次旋转与染色完成修正。

    

通过这 11 步递增序列测试可以看到，红黑树能够持续维持高度约束，并通过节点颜色翻转（预染机制）减少向上传递的连续旋转。与追求高度差不超过 1 的 AVL 树相比，红黑树允许局部路径长度比达到 1:2，从而换取更低的结构维护成本。

重构与实现

“3+4”重构

处理 RR-1 双红冲突时，算法依赖局部 3+4 重构。该机制统一处理二叉树旋转的四类基础对称情况（Left-Left, Left-Right, Right-Left, Right-Right）。当红黑树局部违规时，涉及三个节点 $x$、$p$、$g$，以及与它们相连的四棵内部子树 $T_0$ 到 $T_3$。

所谓“非法”，指的是在某个 3-节点中插入红关键码后，原黑关键码不再处于居中位置。无论经过单次旋转（如 zig-zig）还是双次旋转（如 zig-zag），最终目标都是按中序顺序将三个节点分配为局部根及其左右孩子，再统一套用颜色规则。

C++ STL 红黑树

C++ 的标准模板库 STL 中的红黑树实现采取了较扁平的指针操作。以下提取自 STL 的 _Rb_tree_rebalance 源码片段，它印证了上述理论，并在细节上做出了性能层面的权衡：

inline void _Rb_tree_rebalance(_Rb_tree_node_base* _x, _Rb_tree_node_base*& _root) {
    _x->_M_color = _S_rb_tree_red; // 新插入节点强制标红

    // 只要尚未触及树根，且父节点依然为红色，则持续循环处理（对应双红向上递归）
    while (_x!= _root && _x->_M_parent->_M_color == _S_rb_tree_red) {

        // 分支 A：父节点是祖父节点的左孩子
        if (_x->_M_parent == _x->_M_parent->_M_parent->_M_left) {
            // 获取叔父节点 _y
            _Rb_tree_node_base* _y = _x->_M_parent->_M_parent->_M_right;

            if (_y && _y->_M_color == _S_rb_tree_red) {
                // 【情况 RR-2：叔父为红色】 -> 等效于 B-树节点上溢
                _x->_M_parent->_M_color = _S_rb_tree_black; // 父节点转黑
                _y->_M_color = _S_rb_tree_black;            // 叔父节点转黑
                _x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; // 祖父节点转红，模拟向上进位
                _x = _x->_M_parent->_M_parent; // 游标上溯至祖父节点，继续下一轮 while 检查
            } else {
                // 【情况 RR-1：叔父为黑色或为空】

                // 子情况：若当前节点是右孩子（形成了异侧的 zig-zag 之字形）
                if (_x == _x->_M_parent->_M_right) {
                    _x = _x->_M_parent; // 游标上移至父节点
                    _Rb_tree_rotate_left(_x, _root); // 左旋，将其拉直为同侧的 zig-zig 结构
                }

                // 处理同侧情况（通过单次旋转和染色解决）
                _x->_M_parent->_M_color = _S_rb_tree_black; // 父节点染黑，准备升级为局部新根
                _x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; // 祖父节点染红，准备降级为孩子
                _Rb_tree_rotate_right(_x->_M_parent->_M_parent, _root); // 针对祖父节点执行右旋
            }
        } else {
            // 分支 B：父节点是祖父节点的右孩子
            // 执行与分支 A 完全对称的镜像操作逻辑，代码省略以自洽...
        }
    }

    // 退出循环后，无论执行了何种操作，最终强制确保根节点为黑色，满足根节点约束
    _root->_M_color = _S_rb_tree_black;
}

这段 STL 源码没有额外封装 3+4 重构函数，而是先判断节点是否为 zig-zag（异侧）形态；若是，则先执行一次单旋，将其转换为 zig-zig，再通过一次反向单旋完成修正。这种内联式写法减少了跨函数调用开销。

删除算法

目标节点摘除与双黑

相比插入，删除更容易破坏红黑树的黑高度约束。算法先按普通二叉搜索树逻辑执行 removeAt(x, _hot)，定位并摘除目标节点 $x$。如果实际被摘除节点为红色，整树黑高度不变，规则 3 和规则 4 均保持成立，删除可以直接结束。

若被删除节点与其直接接替者 $r$ 构成一红一黑配对，只需将接替者 $r$ 染为黑色，用新增黑色补足被删除的黑高度。

更复杂的情况是：被摘除节点 $x$ 及其接替者 $r$ 均为黑色，此时对应路径的黑高度下降一阶。在 B-树模型中，这对应内部节点下溢。由于路径黑高度出现缺口，该状态称为双黑。

双黑修复的目标，是从兄弟节点或父节点重新分配黑高度。算法关注接替者 $r$（即使为 NULL，也视为具有颜色语义的外部子树）、父节点 $p$、兄弟节点 $s$。根据 $s$ 及其孩子的颜色分布，删除修复分为四类。

双黑不是一种真实的节点颜色，而是一个“这条路径少了一个黑高度”的记账标记。删除修复的所有分支，都可以理解为三种动作之一：从兄弟那里借一个黑高度、把兄弟和父节点合并后把亏空向上推，或者先旋转把红兄弟转换成黑兄弟情形再处理。

兄弟为黑且含红儿子 (BB-1)

当兄弟节点 $s$ 为黑色，且它至少拥有一个红色的孩子节点 $t$ 时。在四阶 B-树的等价模型中，这代表着 $r$ 所在的节点发生下溢，但相邻兄弟节点内部仍有多个关键码（由红节点表征）。依据 B-树的法则，此时应当发起关键码借用。

在二叉树表示中，算法通过 3+4 局部重构，将红孩子 $t$、兄弟 $s$ 以及父节点 $p$ 重新组织。重构后的局部新根继承原父节点 $p$ 的颜色，而它的两个孩子全部染为黑色。这两个黑色节点补足了 $r$ 所在分支此前缺失的黑高度。删除操作在这一轮重构后结束。

兄弟为黑且全黑儿子 (BB-2R & BB-2B)

当兄弟节点 $s$ 为黑色，但其左右两个孩子均不为红时，说明兄弟节点也无法借出关键码，只能将下溢节点与兄弟节点进行合并。这种合并意味着需要将父节点 $p$ 降入新的超级节点中。在二叉树的操作中，这等价于将兄弟 $s$ 染红。

然而，根据父节点 $p$ 原本颜色的不同，处理方式分为两个分支：

• BB-2R 分支（$p$ 原本为红）：这代表 $p$ 在 B-树中归属于更高层级且仍可提供关键码的超级节点。合并后，将 $p$ 翻转为黑色，直接在局部补足黑高度缺口。下溢解除，调整完成。

• BB-2B 分支（$p$ 原本为黑）：这表示 $p$ 在 B-树中原本就是单关键码节点。节点 $s$ 转红可以修复底层合并后的局部结构，但会把下溢向上传递。在代码中，$p$ 被视为新的双黑位置 $r$，系统需要继续尾递归（或迭代）处理，最坏情况下需要 $\mathcal{O}(\log n)$ 步。

兄弟为红 (BB-3)

最后一种情况是兄弟节点 $s$ 为红色。由红黑树规则可知，$p$ 必为黑，$s$ 的孩子必全为黑。此时系统围绕 $p$ 执行一次单旋，并交换颜色：$s$ 染黑，$p$ 染红。

旋转后，目标 $r$ 获得一个新的黑色兄弟 $s'$。尽管此时包含 $r$ 的分支仍然处于双黑状态，但由于 $p$ 已经染成红色，下一步处理不可能进入 BB-2B，只会进入 BB-1（兄弟有红子）或 BB-2R（兄弟无红子且父为红）这两类可在常数时间内结束的分支。该转换保证了全树性质最终恢复。

删除平衡

下面的代码展示了这四类情况的处理逻辑：

// 删除关键码 e，并在需要时修复双黑缺陷。
template <typename T> bool RedBlack<T>::remove(const T& e) {
    // search 返回待删除位置引用。
    BinNodePosi<T> & x = search(e);
    // 未找到目标节点，删除失败。
    if (!x) return false;

    // 执行 BST 标准删除，r 是物理删除后接替原位置的节点。
    BinNodePosi<T> r = removeAt(x, _hot);
    // 删除后若树为空，无需再修复。
    if (!(--_size)) return true;

    // _hot 为空表示被删除节点原本是根节点。
    if (!_hot) {
        // 新根必须染黑以满足根节点约束。
        _root->color = RB_BLACK;
        // 根颜色改变后刷新高度信息。
        updateHeight(_root);
        return true;
    }

    // 若父节点的黑高度已经满足红黑树约束，则无需继续修复
    if (BlackHeightUpdated(*_hot)) return true;

    // 若替代者 r 为红色，将其染黑即可补回被删除黑节点的黑高度。
    if (IsRed(r)) {
        r->color = RB_BLACK;
        r->height++;
        return true;
    }

    // 被删除节点与替代者都为黑色时，当前路径少一个黑高度。
    solveDoubleBlack(r);
    return true;
}

// 修复以 r 为当前位置的双黑缺陷。
template <typename T> void RedBlack<T>::solveDoubleBlack(BinNodePosi<T> r) {
    // r 为空时用 _hot 找到其父节点；若没有父节点，说明修复已到根。
    BinNodePosi<T> p = r? r->parent : _hot; if (!p) return;
    // s 是 r 的兄弟子树，后续根据 s 的颜色和孩子颜色分类处理。
    BinNodePosi<T> s = (r == p->lc)? p->rc : p->lc;

    // 情况一：兄弟 s 为黑色。
    if (IsBlack(s)) {
        // t 用于记录 s 的某个红色孩子；存在时可通过旋转借黑高度。
        BinNodePosi<T> t = NULL;
        if (IsRed(s->rc)) t = s->rc;
        // 优先获取同侧孩子，以简化 rotateAt 的局部重构。
        if (IsRed(s->lc)) t = s->lc;

        // BB-1：黑兄弟含红孩子，可从兄弟侧借一个黑高度。
        if (t) {
            // 局部新根需要继承父节点原来的颜色。
            RBColor oldColor = p->color;
            // 通过 3+4 重构调整 p、s、t 的相对位置。
            BinNodePosi<T> b = FromParentTo(*p) = rotateAt(t);
            // 新根左右孩子染黑，用于补足缺失的黑高度。
            if (HasLChild(*b)) { b->lc->color = RB_BLACK; updateHeight(b->lc); }
            if (HasRChild(*b)) { b->rc->color = RB_BLACK; updateHeight(b->rc); }
            // 局部新根继承原父节点颜色并更新高度。
            b->color = oldColor; updateHeight(b);
        } else {
            // BB-2：黑兄弟没有红孩子，只能与父节点合并。
            s->color = RB_RED; s->height--;
            if (IsRed(p)) {
                // BB-2R：父节点为红，将其染黑即可补足当前路径。
                p->color = RB_BLACK;
            } else {
                // BB-2B：父节点为黑，合并后双黑继续向上传播。
                p->height--;
                solveDoubleBlack(p);
            }
        }
    } else {
        // BB-3：兄弟节点为红，先旋转转化为黑兄弟情形。
        s->color = RB_BLACK; p->color = RB_RED;
        // 选择红兄弟靠内侧的孩子作为 rotateAt 的参考节点。
        BinNodePosi<T> t = IsLChild(*s)? s->lc : s->rc;
        // 单旋后 r 会获得一个黑兄弟。
        _hot = p; FromParentTo(*p) = rotateAt(t);
        // 继续处理同一个 r；此时不会再停留在红兄弟分支。
        solveDoubleBlack(r);
    }
}

复杂度指标

节点摘除后的修复成本可归纳如下：

双黑缺陷状态判定	涉及旋转最大频次	重染色最大频次	修复结果
黑兄弟有红子 (BB-1)	1~2 次	3 次	局部重构后调整完成。
黑兄弟无红子且父红 (BB-2R)	0 次	2 次	通过重染色完成调整。
黑兄弟无红子且父黑 (BB-2B)	0 次	1 次	必定引发递归，双黑向上攀升，至多波及 $\mathcal{O}(\log n)$ 层。
兄弟为红 (BB-3)	1 次	2 次	先转换为黑兄弟情形，后续流程必然进入 (BB-1) 或 (BB-2R)。

无论删除触发何种局部失衡，红黑树删除修复中的旋转次数最多不超过 3 次：一次来自 BB-3 转换，随后衔接 BB-1 时至多两次局部重构。主要维护开销集中在节点重染色阶段，因此红黑树可以用较小的常数旋转代价维持 $\mathcal{O}(\log n)$ 的最坏情况复杂度。