自从上一次写完红黑树入门已经过去一个多月了……当时天真的我觉得就算再难只要花个一个下午就可以把删除操作搞懂，然而………………
阅前须知
但是我现在在这里申明一点，其实红黑树的删除操作也算不上太难，有一点是因为分类情况太多了。而我迟迟没有理解的一个主要原因在于
我们讨论的删除节点并不是我们在红黑树删除操作中传入的删除的节点,而是被删除节点的替换节点
因为在二叉查找树的删除过程中，被删除的节点实际上会被一个前驱最大节点或者是后继最小节点来替代。
而我们在红黑树中，可以在替换节点的同时，替换节点的颜色改成删除节点的颜色，那么我们的修复目标一下子缩小到了几乎是最下面的子树层，并且对删除节点处的性质并没有任何改变。实在是妙极！
另外感谢这篇文章，我是通过这个博文学习的，并且图片也来自这个博客，写的很好，推荐。
正文
由前文所得，我们的删除操作可以分为两部分，一个是删除，一个是修复。
当然插入的时候也可以分为插入和修复两部分，而且很有条理性，但是插入太简单了，也没细说。
在这里仍然需要提一个大前提：在二叉查找树的删除操作中，对于替换节点，其实是有两个选择的，要么是左孩子一直向右走得到最大前驱，要么是右孩子一直向左走得到最小后继，这里我们统一讨论最小后继。
符号化节点
- D 表示要被删除的节点（其实是替换节点啦，在修复过程中我们视为删除节点）。即：取 Delete 的首字母
- P 表示父节点。即：取 Parent 的首字母；
- S 表示兄弟节点。即：取 Sibling的首字母；
- U 表示叔伯节点。即：取Uncle的首字母；
- G 表示祖父节点。即：取 Grandfather的首字母；
- L 表示左树。即：取Left的首字母；
- R 表示右树。即：取Right的首字母；
- Nil表示叶子节点。即所谓的空节点；注意：红黑树中的叶子节点与其他树中所述说的叶子节点不是同一概念。而且红黑树中的叶子节点(即：Nil节点)永远是被定义为黑色的。
除此之外也会有一些组合表示，这里用的有 DR，删除节点的右孩子，SL，SR，兄弟节点的左右孩子。
分类总览
- D 为红色
- D 为黑色，DR为红色
- D 为黑色，DR为nil，S 为 红色
- D 为黑色，DR为nil，S 为 黑色，SL 为红色，SR颜色任意
- D 为黑色，DR为nil，S 为 黑色，SR 为红色，SL颜色任意
- D 为黑色，DR为nil，S 为 黑色，SL、SR都为黑；P为红色
- D 为黑色，DR为nil，S 为 黑色，SL、SR都为黑；P为黑色
而其中我把 第4种到第7种情况合并为 ** 第 D 种情况**：D 为黑色，DR为nil，S 为 黑色
这样归类的目的在于，第3种情况可以转化为第 D 种情况。
分类讨论
D 为红色
因为我们当前的替换节点是最小后继，所以这个替换节点是没有左孩子的，因此当前节点为根的子树黑高为 0 。从而可得，DR不是红色就是nil。
因此操作为直接将DR替换到 D 的位置即可。
D 为黑色，DR为红色
因为D的左子树的黑高为 0 ，所以DR的两个孩子节点必然为 nil 。
只需将DR替换到D的位置，并将DR染成黑色即可。原D子树的黑高也保持不变。
D 为黑色，DR为nil，S 为 红色
D子树的原黑高为1，删除后为0，而DR为nil，也就是说已经完全没有节点提供我们调整与修复了，所以我们只能去上一层P子树进行调整。
继续分类，可以分为S为红色，或者S为黑色，这里先讨论S为红色。
因为D子树的黑高为 1 ，那么S子树的黑高也同样为1。而S为红色，SL，SR必然为黑色，并且其子孙节点不会有黑色节点。另外，由于红黑树的性质，S为红色，那么P必然为黑色。
如图。
而我们对其的操作如下：
先对P子树进行左旋并交换S和P的颜色，如图。
但是这样操作之后实际上并没有平衡，看上图的P子树，其实DR是nil，而SL必然不是nil（上面有解释）。
但是实际上，这样操作之后也就进入了 第 D 种情况，也就是以下四种情况。
D 为黑色，DR为nil，S 为 黑色，SL 为红色，SR颜色任意
正如之前所说的，SL，SR要么是红色，要么是nil，因此SL与SR都是不影响黑高的。而假定SL为红色，为的是确保这个节点的存在性。
那么修复方法如下：
- 将S子树右旋
- 将SL染成与P一样的颜色 //为的是确保原子树黑高不变
- 将P染成黑色
- 将P子树左旋。
D 为黑色，DR为nil，S 为 黑色，SR 为红色，SL颜色任意
跟上一种情况类似，直接说修复方法：
- 将S染成P的颜色
- 将P染成黑色，SR染成黑色
- 对P子树左旋
D 为黑色，DR为nil，S 为 黑色，SL、SR都为黑；P为红色
SL与SR都为黑色，实际上他们都是nil（看到现在就别问我为什么了）
因为P为红色，那么原P子树的黑高为 1 ，只需要将S染成红色，P染成黑色即可。
D 为黑色，DR为nil，S 为 黑色，SL、SR都为黑；P为黑色
这是最麻烦的情况了，因为它的原P子树的黑高是 2 ，而现在的P子树只有两个节点，在这个P子树上操作是不可能达到 2 的黑高的。
怎么办呢，我们只能将S染红色，将P子树作为一个新的待平衡的点向上递归。
说起来简单，但我感觉实现起来有些困难。
