红黑树删除操作详解 红黑树是一种自平衡的二叉搜索树，它在插入和删除操作中通过旋转和重新着色来维持平衡，确保最坏情况下的时间复杂度为 O(log n)。删除操作比插入更复杂，因为可能需要处理多种情况以恢复红黑树的性质。 1. 红黑树的基本性质 在讲解删除前，先回顾红黑树的五个性质： 每个节点是红色或黑色。 根节点是黑色。 每个叶子节点（NIL 节点）是黑色。 红色节点的子节点必须是黑色（即不能有两个连续的红色节点）。 从任意节点到其所有叶子节点的路径包含相同数量的黑色节点（黑色高度相同）。 2. 删除操作的基本步骤 删除操作分为两部分： 标准二叉搜索树删除 ：找到待删除节点，根据其子节点数量分情况处理。 红黑树平衡修复 ：若删除的节点是黑色，可能破坏性质4或5，需通过旋转和重新着色修复。 2.1 标准二叉搜索树删除 设待删除节点为 z ，分三种情况： 情况1 ： z 无子节点（或只有 NIL 子节点）→ 直接删除，将其父节点的对应指针设为 NIL。 情况2 ： z 只有一个非 NIL 子节点 → 用子节点替换 z ，并继承 z 的颜色。 情况3 ： z 有两个非 NIL 子节点 → 找到 z 的后继节点 y （右子树的最小节点），将 y 的值复制到 z ，然后删除 y （此时 y 最多有一个非 NIL 子节点，转化为情况1或2）。 注意 ：实际删除的节点可能是 z 或其后继 y ，若该节点是黑色，需进入平衡修复流程。 2.2 平衡修复（删除后） 设实际被删除的节点为 y ，其替代节点为 x （即 y 的子节点或 NIL）。若 y 是黑色，删除后会导致： 路径上黑色节点减少（破坏性质5）。 可能使 x 和其父节点均为红色（破坏性质4）。 修复过程以 x 为焦点，通过区分以下情况处理： 情况1： x 是红色节点 直接将 x 染黑即可恢复黑色高度（因为删除的 y 是黑色， x 替换后需增加一个黑色）。 修复完成 。 情况2： x 是黑色节点 此时需进一步分情况处理（设 x 的兄弟节点为 w ，父节点为 p ）： 情况2.1： w 是红色 此时 p 必须是黑色（性质4）， w 的子节点均为黑色。 操作 ： 将 w 染黑， p 染红。 对 p 执行左旋（若 x 是左子节点）或右旋（若 x 是右子节点）。 更新 w 为 x 的新兄弟节点（此时 w 必为黑色，转化为情况2.2、2.3或2.4）。 情况2.2： w 是黑色，且 w 的两个子节点均为黑色 操作 ： 将 w 染红。 将 x 上移为 p （递归处理 p ，因为以 p 为根的子树黑色高度仍少1）。 情况2.3： w 是黑色，且 w 的近侄子节点（与 x 同侧的侄子）为红色，远侄子为黑色 近侄子：若 x 是左子节点，则 w 的左子节点为近侄子。 操作 ： 将远侄子染黑， w 染红。 对 w 执行右旋（若 x 是左子节点）或左旋（若 x 是右子节点）。 更新 w 为 x 的新兄弟节点（转化为情况2.4）。 情况2.4： w 是黑色，且 w 的远侄子节点为红色 操作 ： 将 w 的颜色设为 p 的颜色，将 p 和远侄子染黑。 对 p 执行左旋（若 x 是左子节点）或右旋（若 x 是右子节点）。 将根节点（旋转后可能变化）染黑（保证性质2）。 修复完成 。 3. 实例演示 假设删除根节点的右子节点（黑色），其替代节点 x 为黑色，兄弟 w 为红色： 进入情况2.1：将 w 染黑， p 染红，左旋 p 。 进入情况2.4：将 w 继承 p 的颜色，远侄子染黑，右旋 p ，根染黑。 所有性质恢复。 4. 时间复杂度分析 删除操作中，最多沿树向上递归修复 O(log n) 次，每次修复需常数时间（旋转不超过3次）。 总时间复杂度： O(log n) 。 5. 总结 红黑树删除的核心在于通过分类讨论和局部调整（旋转+染色）保持平衡。重点掌握： 识别实际删除的节点及其颜色。 根据兄弟节点的颜色和子节点情况选择修复策略。 理解旋转和染色如何恢复黑色高度与红色节点约束。