二叉树删除结点找替代结点有3种情情景：
- 情景1：若删除结点无子结点，直接删除
- 情景2：若删除结点只有一个子结点，用子结点替换删除结点
- 情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点
文章插图
图16 二叉树投射x轴后有序
接下来，讲一个重要的思路：删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点！话很苍白，我们看图17 。在不看键值对的情况下，图17的红黑树最终结果是删除了Q所在位置的结点！这种思路非常重要，大大简化了后文讲解红黑树删除的情景！
文章插图
图17 删除结点换位思路
基于此，上面所说的3种二叉树的删除情景可以相互转换并且最终都是转换为情景1！
- 情景2：删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，那么相当于转换为情景3，一直自顶向下转换，总是能转换为情景1 。（对于红黑树来说，根据性质5.1，只存在一个子结点的结点肯定在树末了）
- 情景3：删除结点用后继结点（肯定不存在左结点），如果后继结点有右子结点，那么相当于转换为情景2，否则转为为情景1 。
文章插图
图18 二叉树删除情景转换
综上所述，删除操作删除的结点可以看作删除替代结点，而替代结点最后总是在树末 。有了这结论，我们讨论的删除红黑树的情景就少了很多，因为我们只考虑删除树末结点的情景了 。
同样的，我们也是先来总体看下删除操作的所有情景，如图19所示 。
文章插图
图19 红黑树删除情景
哈哈，是的，即使简化了还是有9种情景！但跟插入操作一样，存在左右对称的情景，只是方向变了，没有本质区别 。同样的，我们还是来约定下，如图20所示 。
文章插图
图20 删除操作结点的叫法约定
图20的字母并不代表结点Key的大小 。R表示替代结点，P表示替代结点的父结点，S表示替代结点的兄弟结点，SL表示兄弟结点的左子结点，SR表示兄弟结点的右子结点 。灰色结点表示它可以是红色也可以是黑色 。
值得特别提醒的是，R是即将被替换到删除结点的位置的替代结点，在删除前，它还在原来所在位置参与树的子平衡，平衡后再替换到删除结点的位置，才算删除完成 。
万事具备，我们进入最后的也是最难的讲解 。
删除情景1：替换结点是红色结点我们把替换结点换到了删除结点的位置时，由于替换结点时红色，删除也了不会影响红黑树的平衡，只要把替换结点的颜色设为删除的结点的颜色即可重新平衡 。
处理：颜色变为删除结点的颜色
删除情景2：替换结点是黑结点当替换结点是黑色时，我们就不得不进行自平衡处理了 。我们必须还得考虑替换结点是其父结点的左子结点还是右子结点，来做不同的旋转操作，使树重新平衡 。
删除情景2.1：替换结点是其父结点的左子结点
删除情景2.1.1：替换结点的兄弟结点是红结点
若兄弟结点是红结点，那么根据性质4，兄弟结点的父结点和子结点肯定为黑色，不会有其他子情景，我们按图21处理，得到删除情景2.1.2.3（后续讲解，这里先记住，此时R仍然是替代结点，它的新的兄弟结点SL和兄弟结点的子结点都是黑色） 。
处理：
