RB-DELETE：红黑树删除操作

参考文章

1、没有子节点

1）红色

直接删除。

2）黑色

删除，之后进行自平衡。由于这个节点是黑色的，那么必然存在黑色兄弟节点或者在兄弟节点的位置的子树的黑高为一。

2、有一个子节点

将这个节点沿着唯一的子节点方向向下交换移动，直到：

1）移动到没有子节点

参考1进行操作。

2）移动到拥有两个子节点

参考3进行操作。

3、有两个子节点

将这个节点的后继节点与这个节点交换值，但颜色不变。

然后在原先后继节点的位置删除原本要删除的节点，首先，这个节点必然是其父节点的左子节点。

然后按照情况1处理。

4、自平衡

1）要删除的节点是其父节点的左子节点

1> 兄弟节点为红色

在这种情况下，兄弟节点在的父节点和子节点都一定是黑色，且兄弟节点必然拥有两个黑色节点。需要做的事删除目标节点，并将兄弟节点设置为黑色、左子节点设置为红色，然后以兄弟节点的父节点为支点进行左旋。

2> 兄弟节点为黑色，其父节点的颜色任意

a) 兄弟节点拥有一个红色的右子节点

将其兄弟节点的颜色设置为其父节点的颜色，然后将其父节点和兄弟节点的左子节点的颜色设置为黑色，然后已其父节点为支点进行左旋；最后直接删除要删除的节点。

b) 兄弟节点拥有一个红色的左子节点

以兄弟节点为支点右旋，然后交换右旋后兄弟节点和其右子节点的颜色，转化为4.1.2.a情况处理。

c) 兄弟节点拥有两个红色的节点

直接参照4.1.2.a情况处理。

d) 兄弟节点没有子节点

以要删除的节点为当前结点，将兄弟节点的颜色设置为红色，将当前节点设置为当前节点的父节点，递归地调用这个过程知道当前节点为根节点或颜色为红色。

最后删除要删除的节点，并将当前节点的颜色设置为红色。

2）要删除的节点是其父节点的右子节点

对称操作即可获得相对应的结果。

3）对于4.1.2.d的理解

可以想象一个节点，他有左右两棵子树，黑高相差为一，便于讨论，假设右边的子树是较矮的一棵。为了满足红黑数的性质，需要进行自平衡，即通过降低另一棵子树的黑高来使得这两棵子树高度相等，然后再看能否通过修改父节点颜色的方式使得父节点对应的这棵子树高度正常。

为了使得左子树的高度减去一，考虑改变兄弟节点的颜色为红色，这样就减少了左子树的黑高。这样操作之后，如果父节点的颜色为红色，那么只要通过更改父节点的颜色为黑色就可以使得父节点对应的子树整体的黑高不变，同时内部又实现了平衡，自此自平衡完毕；但是如果父节点的颜色为黑色，则上面这个方法便没用了，但是，通过更改兄弟节点的颜色，左右子树的黑高一致了，当下的问题转变为了父节点对应的子树与父节点的兄弟节点对应的子树黑高矮一的问题，但是这个问题和原有问题的结构是相同的，所以只要递归地进行这个操作就可以了。

而抵达根结点的时候，由于根结点对应整棵红黑树，所以不存在和其兄弟节点对应的子树不平衡的问题，自此自平衡完毕。