红黑树的删除

---

前言

    在之前我们已经学习了红黑树的插入插入操作, 现在我们来学习删除操作, 删除操作比起插入操作更复杂

---

一.删除的节点左子树右子树都有

    根据二叉搜索树的删除, 找到删除节点的前驱和后继替代删除即可, 替代后就可以转化为后面两种情况, 这里不再详细介绍了

二.删除的节点只有左/右子树

    根据红黑树的特性, 每条路径的黑色节点相同, 不存在连续的红色节点, 所以对于红黑树, 这种删除情况只可能是这样几种, 并且只有一个孩子

删除调整操作

    只需让孩子节点替代删除节点, 再变黑即可
比如上图删除后

三.删除的节点没有孩子

1.删除的节点为红色

    直接删除即可, 不会破坏红黑树的规则

删除后

2.删除的节点为黑色

    删除一个黑色节点, 那么经过这条路径的黑色节点都会少一个, 破坏了黑路同的规则, 这时需要进行调整, 我们需要补上一个黑色节点, 假设当前删除位置有一个黑色节点, 那么现在这棵树还是满足红黑树的规则, 现在我们需要考虑将这个"借"的黑色节点调整
比如

1).兄弟节点为黑色

(1).兄弟节点至少有一个红色的孩子节点

    让兄弟节点的孩子的颜色变成兄弟节点的颜色, 兄弟节点的颜色变成父节点的颜色, 父节点变黑, 再根据兄弟节点的位置进行旋转操作

LL型

比如

删除后"借"一个

变色

右旋并归还"借"节点

RR型

删除后"借"节点

变色旋转

RL型

将兄弟节点的孩子和父节点变色旋转

LR型

变色旋转

(2).兄弟节点没有孩子或所有孩子为黑色

    直接将兄弟节点变红, 然后之前"借"的节点的位置向上移动
比如

兄弟节点变红, "借"节点上移

因为"借"节点为根节点, 直接归还

2).兄弟节点为红色

    兄弟节点为红色, 将兄弟节点和父节点的颜色交换, 相当于向父节点借一个黑色节点, 然后向之前"借"的节点方向旋转

比如
删除后, "借"一个黑色节点保持红黑树规则

变色

向"借"的节点方向旋转

继续调整

完整删除示例

以下面这颗红黑树举例

1. 删除25 是黑色节点, "借"一个节点
   
   发现兄弟节点是黑色并且有一个孩子, 变色旋转调整

2. 删除15 转化为删除它的直接后继

删除一个黑色节点, 它的兄弟节点为红色, 兄弟节点和父节点变色, 向删除节点方向旋转

此时"借"节点兄弟为黑色, 且没有孩子, 变红色, 然后将"节点"向上移

"借"节点遇到红色节点直接变黑

3. 删除6

兄弟节点为黑, 并且有孩子, 变色调整

4. 删除13

兄弟节点为黑, 且没有孩子 变色,"借"节点向上调整

"借"节点兄弟节点为黑,且孩子都为黑色, 变色并调整"借"节点

归还"借"节点

5. 删除37
兄弟节点为黑, 且有红色孩子节点

6. 删除27 转化为删除后继

"借"节点直接变黑

7. 删除17 转化为删除后继

直接删除

8. 删除34 兄弟节点为黑, 且有红色孩子节点
变色旋转

9. 删除9
   兄弟节点为黑色, 且无孩子
   
10. 删除10
    孩子节点顶上