红黑树的删除操作

红黑树是一种自平衡的二叉搜索树，在删除节点时需要通过复杂的调整来维持红黑树的五个性质。删除操作比插入更加复杂，因为可能涉及多种情况的转换。

基本删除流程

1. 标准BST删除：首先按照普通二叉搜索树的方式删除节点

   • 如果被删节点没有子节点：直接删除
   • 如果被删节点有一个子节点：用子节点替代
   • 如果被删节点有两个子节点：找到后继节点（右子树的最小节点），用后继节点的值替换被删节点的值，然后删除后继节点

2. 颜色标记：记录被实际删除的节点颜色

   • 如果删除的是红色节点，通常不需要调整
   • 如果删除的是黑色节点，会破坏黑高性质，需要修复

删除后的修复情况分析

设x为替代被删节点位置的节点（可能是NIL叶子），需要根据x的兄弟节点和侄子的颜色进行不同处理：

情况1：x是根节点

• 直接将x染黑即可

情况2：x的兄弟节点是红色

• 将兄弟节点染黑，父节点染红
• 对父节点进行左旋/右旋
• 重新设置兄弟节点，转入其他情况

情况3：x的兄弟节点是黑色，且兄弟的两个子节点都是黑色

• 将兄弟节点染红
• x上移到父节点位置，继续处理

情况4：x的兄弟节点是黑色，兄弟的近侄子节点是红色，远侄子节点是黑色

• 将兄弟节点染红，近侄子节点染黑
• 对兄弟节点进行旋转
• 转入情况5

情况5：x的兄弟节点是黑色，远侄子节点是红色

• 交换父节点和兄弟节点的颜色
• 将远侄子节点染黑
• 对父节点进行旋转
• 调整完成

具体示例说明

假设要删除节点15（黑色）：

1. 15有两个子节点，找到后继节点17
2. 用17的值替换15，实际删除节点17
3. 删除后，原17位置由它的右子节点（可能是NIL）替代
4. 由于删除的是黑色节点，开始修复过程
5. 根据兄弟节点和侄子节点的颜色，按上述5种情况进行相应处理

时间复杂度分析

• 删除操作：O(log n)
• 修复操作：最多需要O(log n)次旋转
• 总体时间复杂度：O(log n)

红黑树的删除操作虽然复杂，但通过系统性的情况分析和相应的旋转、染色操作，能够有效维持树的平衡性，保证各种操作的高效执行。