C++ 实现红黑树节点的删除平滑平衡修正之六种情形逻辑深度分析【源码】-C++-PHP中文网

红黑树删除后fixup的六种情形是兄弟节点及其子节点颜色组合的自然推导结果，非独立分支；核心是处理“双重黑”缺陷，通过旋转与变色将额外黑向上推或消解。

c++ 实现红黑树节点的删除平滑平衡修正之六种情形逻辑深度分析【源码】

红黑树删除后 `fixup` 的六种情形不是独立分支，而是父子叔颜色+结构组合的自然推导结果

很多人卡在“记不住六种 case”，其实根本不需要硬背。C++ 实现中 rb_delete_fixup 的逻辑本质是：当被删节点的替代节点（replacement）为黑色、且不等于根时，它会留下一个“双重黑”缺陷；修复过程就是不断把这层额外的黑向上推或通过旋转+ recolor 消解。六种情形只是 replacement 的兄弟节点（sibling）及其子节点颜色和结构的所有合法组合——共 2³ = 8 种可能，排除掉两种不可能出现的状态（比如兄弟为红时其子必黑，但此时父必黑，违反红黑树性质），剩下六种。

实操建议：

不要从“case 1 到 case 6”顺序写，先写主干循环：while (x != root && !is_red(x))，再根据 x 是左孩子还是右孩子分两支，每支内统一处理 sibling 颜色
sibling 为红时（即 case 1 / case 4），必须先旋转+变色，把它转成黑兄弟，才能进入后续判断——这是唯一能改变兄弟颜色的入口，漏掉这步，后续所有 case 都不会触发
真正需要区分“兄弟黑，远侄黑，近侄红”还是“兄弟黑，远侄红”等细节，只发生在 sibling 已为黑之后；此时旋转方向由 x 位置决定，recolor 节点由侄子颜色决定

`is_red()` 宏或函数必须能安全处理空指针，否则 `nullptr` 的子节点访问直接崩溃

标准实现中，叶子节点用 nullptr 表示（而非哨兵节点），那么 sibling->left 或 sibling->right 就可能是 nullptr。若 is_red(p) 写成 p->color == RED，遇到 p == nullptr 就段错误。

实操建议：

定义 #define is_red(p) ((p) != nullptr && (p)->color == RED)，强制短路求值
或者用 inline 函数封装，内部判空，避免宏展开副作用
所有对 sibling->left、sibling->right 的颜色检查前，必须先确认 sibling 非空；而 sibling 本身在 fixup 循环中一定非空（因为 x 不是根，父存在，兄弟必存在）

删除后替换节点为 `nullptr` 时，`fixup` 的入口参数 `x` 是父节点对应子指针的地址，不是 `nullptr`

常见错误：删掉一个无孩子的黑节点后，用 nullptr 替代它，然后直接传 nullptr 给 fixup。这会导致循环条件 x != root 立刻失效，跳过修复——但此时父节点少了一个黑，已破坏性质。

正确做法是：让 x 指向被删位置的父节点中那个“本该存子指针”的字段，即 &parent->left 或 &parent->right，并在 fixup 内部用 *x 访问当前节点。这样即使 *x == nullptr，也能继续向上追溯黑高不平衡。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

实操建议：

在 rb_delete 中，确定 replacement 后，记录其父节点 replacement_parent 和它是左/右孩子，然后构造引用：Node*& x = (replacement == replacement_parent->left) ? replacement_parent->left : replacement_parent->right;
fixup 函数签名应为 void fixup(Node*& x)，而非 void fixup(Node* x)，否则无法更新父指针
循环体内所有对 x 的重赋值，如 x = x->parent，实际是 x = (*x)->parent，注意解引用层级

旋转操作必须同步更新父指针，且新父节点的颜色继承旧父节点，否则颜色链断裂

左旋/右旋代码如果只改子指针，不更新 new_parent->parent 和原父节点对它的引用，会导致树结构断裂；更隐蔽的问题是：旋转后，原父节点的颜色必须完整交给新父节点，否则 fixup 向上回溯时，会误判黑高变化。

实操示例（右旋片段）：

void right_rotate(Node*& root, Node* x) {
    Node* y = x->left;
    x->left = y->right;
    if (y->right != nullptr) y->right->parent = x;
    y->parent = x->parent;
    if (x->parent == nullptr) {
        root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->right = x;
    x->parent = y;
    // 关键：颜色不能动！y 继承 x 的颜色，x 设为红色（仅限此场景）
    swap(y->color, x->color); // 常见简化写法，等价于 y->color = x->color; x->color = RED;
}

注意：swap 这一步不是为了“保持红黑性质”，而是确保旋转后，以 y 为根的子树黑高不变——因为 y 替换了 x 的位置，必须携带相同的颜色语义。

真正难的不是写出六种 case，而是理解每次旋转后，哪一层的黑高发生了变化、谁该承担这层“缺失的黑”。只要盯着 x 所指位置的黑高 deficit，所有 case 都是被迫推出的。