红黑树 - 删除

首先，再提一遍红黑树的性质：
    节点是红色或黑色；
    根是黑色；
    所有叶子都是黑色（叶子是NIL节点）；
    每个红色节点的父子节点都不能为红色；
    从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点；

红黑树中删除一个节点，遇到的各种情形就是其子节点的状态和颜色的组合，子节点状态共有3种：无子节点、有一个子节点、有两个子节点，颜色有红色和黑色两种，所以共会有6种组合；（注意，本文子节点和叶节点区分，不是同一个）

组合1：被删节点无子节点，且被删结点为红色
这是最简单的一种情况，直接将节点删除即可，不破坏任何红黑树的性质

组合2：被删结点无子结点，且被删结点为黑色
这是最复杂的情况，我们稍后再讨论

组合3：被删结点有一个子结点，且被删结点为红色

这是一种不可能的情况，此时不符合性质5

组合4：被删结点有一个子结点，且被删结点为黑色
这种组合下，被删结点node的子结点value必然为红色，此时直接将node删掉，用value代替node的位置，并将value着黑即可。

组合5&6：被删结点有两个子结点，且被删结点为黑色或红色

当被删结点node有两个子结点时，我们先找到这个被删结点的后继结点successor（前驱节点也可以），然后用successor替换node的值，不用改变颜色，此时转换为删除node的后继节点successor。

这里使用node的后继节点替换node，必然是下图两种形态中的一种（后继节点的情况）:

若是(a)的情形，用successor代替node后，转换为successor被删，若successor为红色，则变成了组合1（s没有子节点）；若successor为黑色，则变成了组合2（s没有子节点）。

若是(b)的情形，用successor代替node后，转换为successor被删，若successor为红色，则变成了组合1（s没有子节点）（组合3是不可能的）；若successor为黑色，则变成了组合2或4（s没有子节点、或有一个子节点）。

综上所述：组合5 6被转换为前面几种组合，我们真正要进行删除的只有组合1 2 4，对于组合1和4，删除操作相当简单，这里不再多讲，接下来再逐一分析组合2可能的几种情形。

组合2：

因为删除黑色结点会破坏红黑树的性质5，所以为了不破坏性质5，将node删除后用一个拥有额外黑色的null替代它（可以想象是将node删除后，在这个位置放了一个黑色的权值），剩下的就是调平的过程，最终这个游离的黑色权值被扔掉，整个删除操作完成。

然后再结合node的父结点father和其兄弟结点brother来分析。
组合2情形一：brother为黑色，且brother有一个与其方向一致的红色子结点son；（有同方向、黑兄、红侄儿）
所谓方向一致，是指brother为father的左子结点，son也为brother的左子结点；或者brother为father的右子结点，son也为brother的右子结点。

图(c )中，白色代表随便是黑或是红，方形结点存储的是一个游离的黑色权值。将brother和father旋转（是左旋还是右旋自己根据情景体会，下同），并重新上色后，变成了图(d)，将游离的黑色权值扔掉，此时不违背任何红黑树的性质，删除操作完成。（f、b进行左旋）

图(c )中的情形颠倒过来，也是一样的操作（f、b进行右旋）。

组合2情形二：brother为黑色，且brother有一个与其方向不一致的红色子结点son（有方向与黑兄不一致的、红侄儿）；

图(e)中，将son和brother旋转（叔、侄儿之间进行旋转），重新上色后，变成了图(f)，转化为情形一。

图(e)中的情形颠倒过来，也是一样的操作。

组合2情形三：brother为黑色，且brother无红色子结点
此时若father为红，则重新着色即可，删除操作完成。如图下图(g)和(h)

此时若father为黑，则重新着色，将游离的黑色权值存到father（此时father的黑色权重为2），将father作为新的结点进行情形判断，遇到情形一、情形二，则进行相应的调整，完成删除操作；如果没有，则结点一直上溯，直到根结点存储额外的黑色，此时将该额外的黑色扔掉，即完成了删除操作。

注意： 这里第二种情况有点不好理解，之所以要加一个游离的黑色是因为删除node后造成node子树和brother子树的黑节点个数不平衡，这里的操作实际是将brother子树中黑节点个数减少一个，而将father黑色权重设为2，这样father左右两边的子树不用加游离的权值都是平衡的了。接下来将问题转移到了father、father的father、father的brother三个之间，这样向上递归，如果一直是这种情况，最终必定转化为root的左子节点或者右子节点权重为2，同样的将root黑色权重设为2，将另外一边的黑色权重减小1，再将root的黑色权重扔掉一个，此时整棵树重回平衡，只是root到叶节点路径的黑节点少了一个。

组合2情形四：brother为红色，则father必为黑色。（b、f之间进行左旋或右旋）

图(i)中，将brother和father旋转，重新上色后，变成了图(j)，新的brother（原来的son）变成了黑色，这样就成了情形一、二、三中的一种。如果将son和brother旋转，无论怎么重新上色，都会破坏红黑树的性质4或5，例如图(k)。
图(i)中的情形颠倒过来，也是一样的操作。

参考：

红黑树删除节点——这一篇就够了：https://blog.csdn.net/qq_40843865/article/details/102498310