红黑树删除需先定位后继节点并迁移数据，若后继为黑且无子则触发双黑修复：分四情形通过染色与旋转恢复性质，全程须确保指针安全与内存正确释放。
一、红黑树节点删除的基本前提与约束条件
当从红黑树中删除一个节点时，若该节点为红色，则直接移除不会破坏红黑性质；若为黑色，则必然导致其所在路径的黑高减少，从而引发颜色失衡。因此，删除操作的核心在于：定位待删节点、执行物理删除（或用后继/前驱替代）、再通过颜色调整与旋转恢复红黑性质。以下步骤严格遵循CLRS算法规范，聚焦于后继节点替换及后续修复逻辑。
1、若待删节点有两个非空子节点，则查找其**中序后继节点**（右子树中最左节点），该后继必至多有一个子节点；
2、将后继节点的键值与卫星数据复制到待删节点位置，实际删除目标转为该后继节点；
3、若后继节点为红色，则直接删除且无需修复；
立即学习“C++免费学习笔记（深入）”；
4、若后继节点为黑色且存在唯一非空子节点，则该子节点必为红色，将其染黑并上移填补空缺；
5、若后继节点为黑色且无子节点，则产生“双黑”缺陷，需进入删除修复流程。
二、后继节点定位与数据迁移实现细节
后继节点必须满足中序遍历顺序紧邻待删节点的下一个元素，其实质是右子树的最左叶节点或最左内部节点。定位过程不涉及颜色判断，仅依赖结构比较，但迁移后需谨慎处理父指针与子指针的重绑定关系，避免悬挂指针或环引用。
1、定义辅助函数 findSuccessor(Node* node)：从 node->right 开始，持续向 left 下降直至 left 为 nullptr；
2、调用该函数获取 successor 指针，并保存其原始 parent 和 color；
3、将 successor->key、successor->value 等字段逐字节拷贝至待删节点对应字段；
4、若 successor 有右子节点（不可能有左子节点），则将其 right 设为 successor->parent 的 left 或 right 子节点，具体取决于 successor 是其父节点的左还是右孩子；
5、更新 successor->parent->left 或 ->right 指针指向 successor->right，并置 successor->right->parent 为 successor->parent。
三、双黑缺陷触发的四种删除修复情形
当被删除的黑色节点无子节点时，其位置被置为空（nullptr），导致父节点某一支路径黑高减1，形成“双黑”状态。修复过程以 x 表示该空节点在树中的逻辑位置，依据 x 的兄弟节点 s 的颜色及其子节点构型，划分为四类情形，每类均通过染色与旋转组合消除双黑。
1、情形1：s 为红色 → 必有黑色子节点 → 对 x->parent 左旋（若 s 是右孩子）或右旋（若 s 是左孩子），交换 parent 与 s 颜色，转为情形2/3/4；
2、情形2：s 为黑色，且 s 的两个子节点均为黑色 → 将 s 染红，x 上移至 x->parent，递归处理新 x；
3、情形3：s 为黑色，s 的近子节点为红色、远子节点为黑色 → 对 s 执行反向旋转（如 s 是右孩子则右旋），交换 s 与近子节点颜色，转为情形4；
4、情形4：s 为黑色，s 的远子节点为红色 → 以 x->parent 为轴旋转，将 s 染为 x->parent 颜色，x->parent 染黑，s->right 染黑，x 置为 root 并终止修复。
四、关键指针重绑定与内存安全控制
红黑树删除过程中极易出现野指针或提前释放问题，尤其在多线程环境或自定义分配器下。必须确保所有指针更新原子完成，且仅在确认无引用后再调用 delete。Node 结构体中 parent 指针不可省略，否则无法向上回溯进行修复操作。
1、在执行 successor 替换前，记录 original_node->parent、original_node->left、original_node->right 的原始值；
2、所有指针赋值操作（如 parent->left = child）必须成对出现，即同时更新 child->parent = parent；
3、仅当 successor 节点确定不再被任何路径引用后，才调用 delete successor；
4、若使用智能指针（如 std::unique_ptr），需确保 move 语义正确，禁止裸指针与智能指针混用；
5、在修复函数入口处断言 x != nullptr 且 x->color == BLACK，防止非法输入导致未定义行为。
五、典型测试用例覆盖与边界验证
为验证删除与后继替换逻辑的完备性，需构造包含单节点、完全平衡、左倾链、右倾链、含重复键（按标准红黑树定义不允许，但实现中需明确拒绝）、根节点删除、叶子节点删除等场景的测试集。每个测试必须校验：中序遍历有序性、黑高一致性、无连续红节点、根与叶节点颜色合规性。
1、插入序列 {10, 20, 30, 15, 25} 后删除 20 → 后继为 25，替换后检查 25 是否位于原 20 位置且子树结构完整；
2、插入 {5} 后删除 5 → 根变为空，root 指针置为 nullptr，修复函数不应被调用；
3、插入 {1, 2, 3, 4, 5} 构成右链，删除 1 → 后继为 2，替换后需触发多次旋转使树重新平衡；
4、插入 {10, 5, 15, 3, 7, 12, 17} 后删除 10 → 后继为 12，验证 12 上移后其原父节点 15 的 left 指针是否正确重定向；
5、对同一节点连续两次 delete 调用 → 第二次应触发断言失败或抛出 invalid_argument 异常，禁止静默崩溃。
