数据结构之红黑树（三）——删除操作
分类：Data structure & Algorithm
删除一个节点同样有可能改变树的平衡性，而且，删除所造成的不平衡性比插入所造成的平衡性的修正更加复杂。
化繁为简是算法分析中一个常用的方法。下面我们将欲删除节点分为三大类：欲删除节点为叶子节点、欲删除节点只有一个子节点和欲删除有两个子节点。
而欲删除节点有两种可能的颜色，也需要分别对待。
为简化讨论，我们以欲删除节点在左侧的情况为例进行修正，如果欲删除节点在右侧，进行镜像地修正操作即可。
1. 欲删除节点是叶子节点 1.1 欲删除节点为红色，父节点必为黑色，必无兄弟节点。
只有下图所示两种情况，带黄色边框的为欲删除的节点：
将该节点直接删除即可，所在子树的黑色高度不变，不会影响红黑树的性质。
1.2 欲删除节点为黑色，父节点可红可黑，必存在兄弟节点。
为什么说黑色节点必存在兄弟节点呢？如果一个黑色节点不存在兄弟节点，无论父节点是红是黑，则从该节点到父节点会比空子节点到父节点少一个黑色高度，所以这种情况是不存在的。
下面就可能存在的情况逐个分析：
1.2.1 父节点是红色，则兄弟节点必为黑色
与兄弟节点是否有左子节点相关，分为两种情况。
（1）如果兄弟节点没有左子节点，修正策略如下：
上图中，虚线代表其连接的子节点可在可不在，对修正过程无影响。
（2） 如果兄弟节点有左子节点，修正策略如下：
1.2.2 父节点是黑色，则兄弟节点可红可黑 1.2.2.1 兄弟节点为红色，则它必存在两个黑色子节点。
与左侄节点是否有子节点相关，分为三种情况。
（1）如果左侄节点有右子节点，修正策略如下：
（2）如果左侄节点没有右子节点，只有左子节点，修正策略如下：
这时，左侄节点就有了右子节点，再进行与上一种情况一样的修正。
（3）如果左侄节点为叶子节点，修正策略如下：
1.2.2.2兄弟节点为黑色
与兄弟节点是否有子节点相关，分为三种情况。
（1）如果兄弟节点有右子节点，修正策略如下：
（2）如果兄弟节点无右子节点，只有左子节点，修正策略如下：
（3）如果兄弟节点既无左子节点，也无右子节点，如下图所示：
此时，，依靠该子树的自身是无法解决的，因为该子树的黑色高度为2，如果将带黄色边框的节点删除，无论如何变换颜色、旋转都无法使该子树恢复黑色高度。
有两种解决思路：
（1）借助欲删除节点的祖父节点及祖父节点的子树来修正，只要祖父节点与祖父节点的另一颗子树中含有红色节点，就能通过颜色变化和旋转来使。但是，如果祖父节点与祖父节点的另一颗子树中的节点全为黑色：
这时，依靠该子树本身也是无法解决的，还需要借助更上层的节点。层层传递，直到根节点。如果到根节点还是不能解决，就需要采用另一种思路
（2）降低黑色高度。
但就这颗子树来说，确实是符合红黑规则的，但是，子树的黑色高度降低，会影响到整棵红黑树的黑色高度。
可以看到，变换之后，左子树的黑色高度为1，而右子树的黑色高度是2，违背了红黑规则。这时候就需要同时降低右子树的黑色高度，并层层向上传递，直到根节点，最终使整棵树的黑色高度降低。
但是，有的右子树是无法降低黑色高度的，比如：
旅行，其实是需要具有一些流浪精神的，
