删除两子节点节点时，须用其右子树中最小后继替代，交换指针而非值；后继至多一个子节点，删之触发双黑修复，依兄弟节点颜色及子节点情况分四类处理，需严格更新指针与颜色。
删除节点时如何正确找到后继并完成替换
红黑树删除必须保证二叉搜索树性质不被破坏，所以当待删节点有两个子节点时，必须用它的后继（右子树中最小节点）或前驱（左子树中最大节点）来替代。标准做法是统一用后继——它一定至多有一个子节点（否则还能往下找更小的），这简化了后续修复逻辑。
关键点在于：后继节点可能本身是红色或黑色，且它的父节点、子节点颜色和连接关系会直接影响后续的平衡修复。不能直接交换值（比如 key 和 value），而应交换指针引用，否则会破坏红黑树结构中对“节点身份”的依赖（例如迭代器失效、自定义比较逻辑异常）。
- 后继一定在待删节点的右子树中，通过不断向左走得到：
successor = node->right; while (successor->left) successor = successor->left; - 若后继不是
node->right本身，需先将后继从原位置摘下，并用其唯一子节点（successor->right）补位；注意此时不改变颜色，只调整指针 - 再把后继的
left、right、color、parent全部复制给原node的位置，相当于“移动节点”而非“交换值” - 真正要删除的物理节点变成后继，它必然只有 0 或 1 个子节点，进入下一步修复流程
删除后双黑问题与修复的四种情况判断依据
红黑树删除的核心难点不是“删”，而是“删完颜色失衡”。当一个黑色节点被删，而它唯一的子节点（或替代它的子节点）也是黑色时，该子节点就承载了“双重黑色”语义——即它既要算作自己原本的颜色，又要代偿被删黑色节点的计数。这个“双黑”必须沿树向上推，直到遇到红节点（染黑即可）、根节点（直接去掉一层黑），或能通过旋转+变色消解。
修复过程围绕“当前双黑节点 x”及其兄弟 w 展开，所有情况均由 w 的颜色、子节点颜色组合决定，不是凭感觉选旋转方向。
- 情况1：
w是红色 → 必须先转为黑色：对parent(x)左旋（若x是左孩子），交换parent(x)和w颜色，再进入情况2/3/4 - 情况2：
w是黑色，且两子均为黑 → 将w染红，把双黑上推至parent(x)，递归处理 - 情况3：
w是黑色，w->left红、w->right黑（且x是左孩子）→ 对w右旋，交换w和w->left颜色，转为情况4 - 情况4：
w是黑色，w->right红 → 对parent(x)左旋，w染成parent(x)原色，parent(x)和w->right染黑，双黑消除
注意：所有旋转后必须更新 parent 指针，尤其是根节点变更时要重置 root；w 的左右子节点为空时，视作黑色节点（NIL），避免空指针访问。
实际编码中容易崩掉的三个细节
很多实现跑不过测试用例，不是算法错，而是边界没兜住。最常出问题的是指针野访问、颜色误判、以及根节点特殊处理遗漏。
-
nullptr节点必须视为黑色，但不能对其调用color字段——应在访问前加保护，如：auto sibling = x == x->parent->left ? x->parent->right : x->parent->left; if (!sibling) { /* treat as black, then continue */ } - 旋转后父子关系未同步更新：比如左旋
p，新根是p->right，但p->right->left的parent还指向旧节点，必须显式赋值 - 删除根节点且根为黑色时，若根唯一子节点是红色，删完后需将其染黑并设为新根；若根无子节点，新根为
nullptr，此时整棵树为空，别忘了清空root
要不要用模板参数控制是否存储父指针
标准红黑树实现里，每个节点都存 parent 指针，这是为了在删除后能快速回溯、做旋转和颜色更新。但如果你追求极致内存节省（比如嵌入式场景），可以去掉 parent，改用栈记录路径。代价是删除时需额外 O(log n) 空间，且代码复杂度陡增——每次旋转都要重新定位父节点，successor 查找也要带路径栈。
除非明确受限于 RAM，否则不要省这个字段。现代 C++ 编译器对 parent 指针的访问优化很好，且调试时能直接打印完整路径，比靠栈模拟直观得多。
真正值得权衡的是：是否让节点结构体包含 color 字段，还是用地址最低位（LSB）隐式编码（如奇地址=红，偶地址=黑）。后者省 1 字节，但要求所有节点地址对齐到 2 字节以上，且增加位运算负担，可读性差。普通项目直接用 bool color 更稳妥。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
