彻底理解红黑树（三）之 删除
彻底理解红黑树（一）之 二叉搜索树
彻底理解红黑树（二）之 插入
彻底理解红黑树（三）之 删除
红黑树的删除情况相对插入会复杂一些，这里以个人认为较好理解和记忆的方式进行分类，和其他一些文章（比如 维基百科 ）的表达可能不一样，但是实际上是一样的。比如说家有两兄弟A和B。我是根据A是哥哥还是弟弟进行分类；他是根据B是哥哥还是弟弟进行分类。
建议阅读本文后，自己动手试试，一来印证本文是否正确，二来自己尝试着摸一些规律，加深印象（文末也有一个简单的例子）。
红黑树和二叉搜索树的删除类似，只不过加上颜色属性（ 这里的子节点均指非NULL节点 ）：
我们发现，删除情形3总是会转换为情形1和2的，而情形1.1和情形2处理平衡非常简单，本文主要讨论的是情形1.2：删除 黑色的叶子节点 。因为一旦该节点被拿掉，红黑树中通过该节点的路径黑色节点数量将会减1，而且无法像情形2那样将子节点涂黑来达到平衡。此时只能自底向上进行平衡操作。
我们先约定一下节点名称：
h(A->B->叶子)表示从A走到B再走到某一个叶子路径的黑色节点数量（A与B，B与叶子之间可能间隔了多个节点）
本文余下内容均指的是 删除黑色的叶子节点后 引发的一系列平衡操作。比如P->D->N，删除D（黑色）后，N接至父节点：P->N。
因为删除了一个黑色节点（N的父节点D），经过N的路径的黑色数量减1，即h(P->N->叶子) 比 h(P->S->叶子) 少1。平衡的方式有：
（1）h(P->N->叶子)不变，h(P->S->叶子)减1，此时已经子平衡；然而h(GP->P->叶子)还是会比h(GP -> U ->叶子)少1。此时需要将P当作新的N，向上递归处理；
（2）h(P->N->叶子)加1，h(P->S->叶子)不变，也就是恢复了原来的状态，此时已经平衡，因为h(GP->P->叶子)=h(GP -> U ->叶子)。
本文下面平衡的思路主要就是基于以上两种方式，另外要注意的是，红色和红色不能连一起的约束也不能违反。理解这个比较重要。
删除平衡情形，主要根据 [兄节点的位置/颜色]、[兄的子节点的颜色]、[父节点颜色] 进行分类：
N节点的位置知道后，S的位置自然也就知道了，相反亦可；这里以S位置作为分类，主要是为了便于理解和记忆。
比较特殊的情况，无需平衡操作。因为经过根节点的黑色数量少一个，意味着所有路径都少一个，已然平衡。
兄弟节点的子节点全为黑色，也就意味着兄弟节点（S）可以涂红而不会和子冲突。S涂红后，也就实现了子平衡，
这时候我们看父节点是红是黑，再做处理。
此时将S涂红，父节点作为新的平衡节点N，递归上去处理。
这个也就是之前提到的h(P->N->叶子)不变，h(P->S->叶子)减1；而h(GP->P->叶子)，依然会比h(GP -> U ->叶子)少1，所以要递归上去处理。
此时将S涂红，P涂黑，平衡结束。
S涂红后，h(P->N->叶子)不变，h(P->S->叶子)-1，实现子平衡；因为P节点是红色的，如果将它涂黑，h(P->N->叶子)和h(P->S->叶子)均会+1，就可以恢复原来的状态了，而不用递归上去。
所谓的不全黑包括：[SL红, SR红]、[SL黑，SR红]、[SL红，SR黑]。如果其中一个为黑，另外一个肯定是红。
以全黑/非全黑作为分类，是因为全黑时无论N是在左子还是右子，其处理方式是一样的。
而非全黑则要看N所处的位置（或者说 S所处的位置 ）进行特定方向的旋转。
为了方便理解和记忆，以S进行分组：
S为左子时（即N为右子），主要分两组 [SL=红]、[SL=黑]。
S为右子时（即N为左子），主要分两组 [SR=红]、[SR=黑]。
【S为左子，SL红】与【S为右子，SR红】处理方式对称；
【S为左子，SL黑】与【S为右子，SR黑】处理方式对称。
情形(1) S为黑色， S为左子 ， SL红 时：
以 P 为支点 右旋 ；交换P和S颜色， SL涂黑 ；平衡结束。
这里的平衡思路其实就是：h(P->S->叶子)不变（因为SL涂黑补回来了），h(P->N->叶子)+1（因为多了个黑色P）。
通常旋转后，新的P节点往往都会涂成原P的颜色：一是为了让GP-P不会颜色冲突；二是保持经过P的路径黑色数量不变。
对称的 情形(2) ：S为黑色， S为右子 ， SR红 时：
以 P 为支点 左旋 ；交换P和S颜色（S涂为P原颜色，P涂黑）， SR涂黑 ；平衡结束。
情形(1) S为黑色， S为左子 ， SL黑
以 S 为支点 左旋 ，交换S和SR颜色（SR涂黑，S涂红） ，此时转至情形2.2.1-(1) S左-SL红 进行处理。
S涂红是为了使h(原S->SR->叶子)不变。
对称的 情形(2) S为黑色， S为右子 ， SR黑
以 S 为支点 右旋 ，交换S和SL颜色（SL涂黑，S涂红），此时转至2.2.1-(1) S右-SR红进行处理。
情形(1) S为左子时，以P进行右旋；
情形(2) S为右子时，以P进行左旋；
旋转后交换P和S的颜色（S涂黑，P涂红），N兄弟节点变为黑色，进入情形2-兄弟节点为黑色进行处理。
现在我们有一颗红黑树：
（1）删除50，删除动作-情形3 --> 删除动作-情形2，简单处理即可：
（2）删除70，即黑色叶子节点，进行平衡：
（3）删除60：
（4）删除10：
（5）删除20：
