删除处理

1 被删除的节点没有儿子

根据节点颜色处理有不同。

1.1 如果是红色节点

那么直接删除就可以了，因为删除红色节点，不影响路径上黑色节点的个数。也不会违反约束4.

1.2 如果是黑色节点

删除后，路径上黑色节点的个数少1，如果是根节点，那么删除完成了，如果不是，那么树就不平衡了，需要重新上色和旋转，见下面的旋转处理。

那么只要把自己删除，然后儿子坐自己的位置即可。颜色处理如下：

2.1 自己和儿子，其中一个是红色

这种情况好办，因为原路径只有一个黑色，那么删除后，儿子为黑色就可以了。

2.2 自己和儿子，都是黑色

原路径上有2个黑色节点，删除一个，路径黑色节点减少了1，需要根1.2一样，重新上色和旋转。

动作被拆解成一个替换和一个删除。

3a. 将右边路径上的leftmost节点替换自己即可，颜色和自己保持一致，那么被删除位置路径还是原来的状态。

leftmost节点比左边路径的任何节点都大，又比右边路径上的所有节点都小，所以是它替换被删除的节点。

3b. 按照1,2 处理leftmost被删除的情况

如果leftmost没有儿子，那么按照1处理，如果leftmost有一个右儿子，那么按照2处理。leftmost不可能有左儿子。

上述1.2和2.2处理完毕后，被删除位置路径上的黑色节点个数减了一个。

如果是根节点，那么所有路径度减少了1个，没关系，删除完成，如果不是根节点，需要进行旋转和重新着色处理。

旋转和重新着色与被删除位置的兄弟节点的颜色相关，各种情况如下：

a) sibling is black and at least one of sibling’s children is red

兄弟是黑色，且兄弟有一个红色的儿子，这种情况比较好办，可以把旋转匀一个过来，把红色放到这边变成黑色。

a.1) Left Left / Right right case

如下图是RR情况，LL情况是对称的。RR情况，往左旋转一下。

1 兄弟变父亲，父亲变兄弟的左儿子，而兄弟的左儿子变成父亲的右儿子，兄弟的右儿子位置不动。

2 兄弟变成父亲的颜色，父亲变成黑色。右儿子变成黑色，左儿子不变。

上述动作既保证了二叉搜索树左小右大的性质，也保证了黑色节点数不变，因此完成后，删除就结束了。

a.2) Left right / Right left case

下图是RL情况，

和RR情况不同，兄弟的左儿子坐父亲的位置，兄弟不变，其实下图中，兄弟的儿子的儿子没有标出来。但是很容易推算出来。

颜色情况，兄弟的左儿子变成父亲的颜色，父亲变成黑色。删除结束

b) If sibling is black and its both children are black

把兄弟变成红色，这样，左右两边路径上的黑色节点就相同了，但是都少了一个。此时有两种情况：

i. 如果父亲是红色，那么把父亲变成黑色。这样黑色节点数就不变了，删除完成。

ii. 如果父亲是黑色，那么把父亲变成u，继续往上冒泡，进行旋转和重新着色处理。

c) If sibling is red

父亲是黑色，先进行旋转，这里也右Right和Left两种情况。兄弟坐父亲的位置，且变成黑色，父亲变成兄弟的儿子，且变成兄弟的颜色红色。这样变换成了兄弟是黑色的情况，如下图，新的兄弟是25，是老兄弟的左儿子，按照上述兄弟是黑色（a/b)的情况继续处理。

参考