红黑树的删除操作 红黑树是一种自平衡的二叉搜索树，它通过特定的规则和旋转操作来维护平衡，确保最坏情况下的操作时间复杂度为O(log n)。删除操作是红黑树中最复杂的部分，因为它可能破坏红黑树的平衡性质，需要通过一系列调整来恢复平衡。 红黑树的性质 在讲解删除前，先回顾红黑树的五个性质： 每个节点是红色或黑色。 根节点是黑色。 每个叶子节点（NIL节点）是黑色。 红色节点的子节点必须是黑色（即不能有两个连续的红色节点）。 从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点（黑色高度相同）。 删除操作的基本步骤 删除操作分为两步： 执行标准二叉搜索树（BST）的删除 ：找到待删除节点，并根据其子节点数量处理。 平衡调整 ：如果删除的节点是黑色，可能违反性质5，需要通过旋转和重新着色来恢复平衡。 步骤1：BST删除 设待删除节点为 z ，分三种情况： 情况A ： z 没有子节点（或只有NIL叶子节点）。直接删除 z ，并将其父节点指向NIL。 情况B ： z 有一个子节点。用子节点替换 z ，并删除 z 。 情况C ： z 有两个子节点。找到 z 的后继节点 y （右子树中的最小节点），将 y 的值复制到 z ，然后删除 y （此时 y 最多有一个子节点，转化为情况A或B）。 注意 ：实际删除的节点可能是 z 或其后继 y 。记实际被删除的节点为 d （其子节点最多一个），替换 d 的子节点为 c （可能为NIL）。如果 d 是黑色，删除后需要调整。 步骤2：平衡调整 如果被删除的节点 d 是红色，直接删除不会破坏性质5（黑色高度不变）。但如果 d 是黑色，则经过 d 的路径黑色节点减少1，违反性质5。调整过程以 c （替换 d 的节点）为中心，通过迭代处理以下情况（假设 c 是左孩子，右孩子情况对称）： 情况1 ： c 是红色。 将 c 染黑即可（补偿丢失的黑色节点）。调整结束。 情况2 ： c 是黑色，且其兄弟节点 s 是红色。 此时父节点 p 必须是黑色（因 s 红）。通过左旋（若 c 是左孩子）或右旋（若 c 是右孩子）使 p 和 s 交换颜色： p 染红， s 染黑。旋转后， c 的新兄弟是原兄弟的子节点（黑色），转化为情况3、4或5。 情况3 ： c 是黑色，兄弟 s 是黑色，且 s 的两个子节点都是黑色。 将 s 染红，此时通过 p 的路径黑色高度统一减少1，但 p 可能为红或黑。若 p 原为红色，将 p 染黑即可补偿；若 p 原为黑色，则以 p 为新 c ，递归向上调整。 情况4 ： c 是黑色，兄弟 s 是黑色， s 的近侄子（与 c 同侧的侄子）是红色，远侄子黑色。 通过旋转使近侄子成为新兄弟：例如 c 是左孩子时，右旋 s 并交换 s 和近侄子颜色（ s 染红，近侄子染黑）。转化为情况5。 情况5 ： c 是黑色，兄弟 s 是黑色，远侄子红色。 通过旋转父节点 p ：例如 c 是左孩子时，左旋 p ，并交换 p 和 s 的颜色，将远侄子染黑。此时黑色高度恢复，调整结束。 示例说明 假设删除节点 d （黑色）后，其子节点 c （黑色）替换位置，且 c 的兄弟 s 为红色（情况2）。 左旋父节点 p ， p 染红， s 染黑。此时 c 的新兄弟是 s 的左孩子（黑色）。 若新兄弟的子节点全黑（情况3），将新兄弟染红， p 成新焦点。若 p 原为红，染黑结束；否则递归向上。 若遇到情况4或5，通过旋转直接恢复平衡。 关键点 调整过程最多遍历O(log n)次树高。 旋转操作（左旋/右旋）保持BST性质，重新着色修复红黑性质。 情况3可能引发递归，但每次递归向上移动，最终在根节点或红色节点终止。 通过以上步骤，红黑树在删除后仍能维持平衡，确保高效操作。