红黑树的删除操作_红黑树删除

红黑树定义：
　1. 红黑树的节点不是黑色的就是红色的

2. 红黑树的根节点一定是黑色的

3. 红黑树的所有叶子节点都是黑色的（注意：红黑树的叶子节点指Nil节点）

4. 红黑树任何路径上不允许出现相邻两个红色节点

5. 从红黑树的任一节点开始向下到任意叶子节点所经过的黑色节点数目相同
删除一个新的节点有以下四种情况：

1. 删除的节点是叶子节点（非Nil）

2. 删除的节点只有左子树

3. 删除的节点只有右子树

*4. 删除的节点同时拥有左子树和右子树

其实只有上面前三种情况，对于第四种
　　情况，可以找到待删除节点的直接后继节点，用这个节点的值代替待删除节点，接着情况转变为删除这个直接后继节点，情况也变为前三种之一。
约定删除结点为D，父节点为P，兄弟节点为S，兄弟节点的左右子结点分别为DL和DR。
情况1：
父节点P是红色结点
或者
处理过程：
这两种情况是一样的，我们讨论第一个图就好，当把D删去后，从P的左子树下来的黑色节点数目少了一，对应的调整做法为，把P染成黑色，此时P左子树的黑色结点数目恢复，但此时右子树黑色结点数目多了一，再把S对应染成红色即可。如下图：

情况2：兄弟结点S为红色结点
或者
处理过程：
只能是这两种情形，做法是把P染成红色，S染成黑色，然后以P为轴做相应的旋转操作（如果D为P的左子树节点则以P为轴做左旋操作，如果D为P的右子树节点则以P为轴做右旋操作）。
如下图：

此时转化成了情况1。
情况3：删除结点的兄弟节点的右子结点为红色结点，左子结点为nil结点或者红色结点

处理过程：
这种情况的调整做法是，交换P和S的颜色，然后把远侄子节点SR/SL设置为黑色，再以P为轴做相应的旋转操作（如果D为P的左子树则左旋，如果D为P的右子树则右旋）。
如下图：

情况4：删除结点的兄弟节点的左子结点为红色，右子结点为nil结点。

处理过程：
这种情况的调整方式是，把S染成红色，把近侄子节点SR/SL染成黑色，然后以节点S为轴做相应的旋转操作（如果D为P的左子树则以S为轴做右旋操作，如果D为P的右子树则以S为轴做左旋操作）。
如下图：

转化成了情况3。
情况5：结点D、P、S均为黑色结点

处理过程：这种情况做法就是把D删去，然后把节点S染成红色，这样一来节点P的左右子树路径的黑色节点路径就一样了，但导致节点P整棵子树的任意路径的黑色节点数比其他路径少了一，此时我们再从P开始（即把P当成D），但不再删除P，向上继续调整，直到根节点（一直是情况5）或者遇到情况1~4并调整后结束。
从结点P往上依然是全黑的情况：

从结点P往上是其他情况：

无论是变成情况1~4的哪种，经过调整之后都无需再继续上溯，因为此时黑色节点数目已经恢复。
情况6：待删除的结点是红色叶子结点
处理过程：直接删除
情况7：待删除的结点只有左子树或者右子树

这两种情况放在一起讨论，处理过程是直接替换
情况8：待删除结点同时包含左子树和右子树
均可通过寻找后继结点的方法化为情况1~8中的一种。