C++ 实现红黑树节点的删除与后继节点替换逻辑算法及其动态平衡调整【源码】-C++-PHP中文网

安全删除需先判右子树非空再找后继，后继颜色继承原节点以保黑高，修复时须处理兄弟为空或无子等边界，delete_node与fixup职责分离。

c++ 实现红黑树节点的删除与后继节点替换逻辑算法及其动态平衡调整【源码】

删除节点时如何安全找到后继并避免空指针崩溃

红黑树删除中，真正被移除的往往不是目标节点本身，而是它的后继（或前驱）——尤其当目标节点有两个子节点时。直接调用 successor() 而不检查右子树是否存在，会导致对空指针取 left 或无限循环遍历。

必须先判断 node->right != nullptr，再进入后继查找；否则跳过整个逻辑，改用前驱（但标准实现通常统一用后继）

后继一定位于右子树的最左节点，查找过程不能递归，应使用 while 循环：

Node* successor(Node* node) {
    if (!node || !node->right) return nullptr;
    Node* s = node->right;
    while (s->left) s = s->left;
    return s;
}

若后继节点是目标节点的直接右孩子，替换后需特别处理父指针——此时后继的父指针仍指向原节点，但原节点即将被删，必须提前修正

用后继替换后，为什么必须把后继的颜色设为原节点颜色

红黑树的黑色高度约束要求：任一节点到其所有叶子路径上的黑色节点数相同。如果简单用后继覆盖原节点值，却不继承颜色，可能瞬间破坏该性质。

后继节点被“提拔”到原位置后，它承担了原节点在树结构中的角色，包括其颜色语义
若原节点是黑色，而后继是红色，则替换后该路径少了一个黑节点 → 必须保持后继为黑，并触发后续修复（fixup_after_delete()）
若原节点是红色，后继必为黑色（红黑树性质：红节点子节点必黑），此时直接设后继为红即可，不会引发双红冲突，也无需修复
代码中这一步不可省略：successor->color = node->color;

删除后修复（`fixup_after_delete`）中最易漏掉的两种双黑场景

修复函数本质是把“双黑”缺陷沿路径向上推，直到遇到红节点（染黑即可）或根（直接消掉一个黑）。但两个边界情况常被忽略：

C++14

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

下载

兄弟节点为 null：即当前节点是唯一子节点，父节点另一侧为空。此时不能访问 brother->color，应视作“黑兄弟”，且无远侄子（far_nephew 为 null），只能靠旋转+ recolor 向上转移双黑
兄弟为黑，且两个侄子都黑，但兄弟本身没有子树：此时 brother->left == nullptr && brother->right == nullptr，等价于双侄子黑，仍适用 case 2（父变黑、兄弟变红），但若误判为有红侄子而进 case 3/4，会触发空指针解引用
所有分支最后都要检查 node != root，否则对根节点执行 node = node->parent 后继续循环，将越界访问

实际编码时 `delete_node` 和 `fixup` 的职责必须严格分离

很多人把颜色调整、旋转、指针重连全塞进一个函数，导致逻辑耦合、难以调试。真实可维护的实现必须分层：

delete_node(Node* z) 只做三件事：定位真正要删的节点（后继）、交换值与颜色、卸下该节点（更新父/子指针），然后把“悬空”的双黑节点传给修复函数
fixup_after_delete(Node* x) 只接收一个双黑节点 x，不关心它从哪来，只根据其父、兄弟、侄子状态做局部修正，返回条件只有 x == root || x->color == RED
旋转函数（rotate_left/rotate_right）必须接受 Node** root 或显式传入祖父指针，否则无法更新顶层链接 —— 这是 C++ 中最容易因指针传递方式出错的地方

C++ 实现红黑树删除最难的不是旋转本身，而是双黑状态在空子树、单边缺失、颜色继承之间的精确传导；稍有不慎，segmentation fault 就发生在第 7 次插入后的第一次删除里。