547.删除

第一步：将红黑树当作一颗二叉查找树，将节点删除。

这和"删除常规二叉查找树中删除节点的方法是一样的"。分 3 种情况：

1. 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就 OK 了。
2. 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
3. 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。

第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。

因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。

选择重着色 3 种情况。

1. 情况说明：x 是“红+黑”节点。
   处理方法：直接把 x 设为黑色，结束。此时红黑树性质全部恢复。

2. 情况说明：x 是“黑+黑”节点，且 x 是根。
   处理方法：什么都不做，结束。此时红黑树性质全部恢复。

3. 情况说明：x 是“黑+黑”节点，且 x 不是根。
   处理方法：这种情况又可以划分为 4 种子情况。这 4 种子情况如下表所示：

参考：https://www.jianshu.com/p/038585421b73
代码实现：https://www.cnblogs.com/skywang12345/p/3624343.html