好了，讲完插入的所有情景了。可能有同学会想：上面的情景举例的都是第一次插入而不包含自底向上处理的情况，那么上面所说的情景都适合自底向上的情况吗?答案是肯定的。
理由很简单，只要每棵子树都能自平衡，那么整棵树最终总是平衡的。好吧，在出个习题，请大家拿出笔和纸画下试试(请务必动手画下，加深印象)。
习题 1：请画出图 15 的插入自平衡处理过程。(答案见文末)
图 15：习题 1
红黑树删除
红黑树插入已经够复杂了，但删除更复杂，也是红黑树最复杂的操作了。但稳住，胜利的曙光就在前面了!
红黑树的删除操作也包括两部分工作：一是查找目标结点;二是删除后自平衡。
查找目标结点显然可以复用查找操作，当不存在目标结点时，忽略本次操作;当存在目标结点时，删除后就得做自平衡处理了。
删除了结点后，我们还需要找结点来替代删除结点的位置，不然子树跟父辈结点断开了，除非删除结点刚好没子结点，那么就不需要替代。
二叉树删除结点找替代结点有 3 种情景：
若删除结点无子结点，直接删除。
若删除结点只有一个子结点，用子结点替换删除结点。
若删除结点有两个子结点，用后继结点(大于删除结点的最小结点)替换删除结点。
补充说明下，情景 3 的后继结点是大于删除结点的最小结点，也是删除结点的右子树中最右结点。
那么可以拿前继结点(删除结点的左子树最左结点)替代吗?可以的。但习惯上大多都是拿后继结点来替代，后文的讲解也是用后继结点来替代。
另外告诉大家一种找前继和后继结点的直观的方法(不知为何没人提过，大家都知道?)：把二叉树所有结点投射在X轴上，所有结点都是从左到右排好序的，所有目标结点的前后结点就是对应前继和后继结点。
如图 16 所示：
图 16：二叉树投射 x 轴后有序
接下来，讲一个重要的思路：删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点!话很苍白，我们看图 17。
图 17：删除结点换位思路
在不看键值对的情况下，图 17 的红黑树最终结果是删除了 Q 所在位置的结点!这种思路非常重要，大大简化了后文讲解红黑树删除的情景!
基于此，上面所说的 3 种二叉树的删除情景可以相互转换并且最终都是转换为情景 1。
情景 2：删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，那么相当于转换为情景 3，一直自顶向下转换，总是能转换为情景 1。(对于红黑树来说，根据性质 5.1，只存在一个子结点的结点肯定在树末了)
情景 3：删除结点用后继结点(肯定不存在左结点)，如果后继结点有右子结点，那么相当于转换为情景 2，否则转为情景 1。
二叉树删除结点情景关系图如图 18 所示：
图 18：二叉树删除情景转换
综上所述，删除操作删除的结点可以看作删除替代结点，而替代结点最后总是在树末。
有了这结论，我们讨论的删除红黑树的情景就少了很多，因为我们只考虑删除树末结点的情景了。
同样的，我们也是先来总体看下删除操作的所有情景，如图 19 所示：
图 19：红黑树删除情景
哈哈，是的，即使简化了还是有 9 种情景!但跟插入操作一样，存在左右对称的情景，只是方向变了，没有本质区别。同样的，我们还是来约定下，如图 20 所示：
图 20：删除操作结点的叫法约定
图 20 的字母并不代表结点 Key 的大小。R 表示替代结点，P 表示替代结点的父结点，S 表示替代结点的兄弟结点，SL 表示兄弟结点的左子结点，SR 表示兄弟结点的右子结点。灰色结点表示它可以是红色也可以是黑色。
值得特别提醒的是，R 是即将被替换到删除结点的位置的替代结点，在删除前，它还在原来所在位置参与树的子平衡，平衡后再替换到删除结点的位置，才算删除完成。
万事俱备，我们进入最后的也是最难的讲解。
删除情景 1：替换结点是红色结点。