彻底理解红黑树（一）之 二叉搜索树
彻底理解红黑树（二）之 插入
彻底理解红黑树（三）之 删除

前言

红黑树的删除情况相对插入会复杂一些，这里以个人认为较好理解和记忆的方式进行分类，和其他一些文章（比如维基百科）的表达可能不一样，但是实际上是一样的。比如说家有两兄弟A和B。我是根据A是哥哥还是弟弟进行分类；他是根据B是哥哥还是弟弟进行分类。
建议阅读本文后，自己动手试试，一来印证本文是否正确，二来自己尝试着摸一些规律，加深印象（文末也有一个简单的例子）。

1.删除动作

红黑树和二叉搜索树的删除类似，只不过加上颜色属性（这里的子节点均属非NULL节点）：

1. 无子节点时，删除节点可能为红色或者黑色；
   1.1 如果为红色，直接删除即可，不会影响黑色节点的数量；
   1.2 如果为黑色，则需要进行删除平衡的操作了；
2. 只有一个子节点时，删除节点只能是黑色，其子节点为红色，否则无法满足红黑树的性质了。 此时用删除节点的子节点接到父节点，且将子节点颜色涂黑，保证黑色数量。
3. 有两个子节点时，与二叉搜索树一样，使用后继节点作为替换的删除节点，情形转至为1或2处理。

删除动作-情形1 删除动作-情形2 删除动作-情形3

我们发现，删除情形3总是会转换为情形1和2的，而情形1.1和情形2处理平衡非常简单，本文主要讨论的是情形1.2：删除黑色的叶子节点。因为一旦该节点被拿掉，红黑树中通过该节点的路径黑色节点数量将会减1，而且无法像情形2那样将子节点涂黑来达到平衡。此时只能自底向上进行平衡操作。

这里的图特意将黑色的NULL节点给加上，这是因为删除节点被摘掉后，我们可以用一个黑色的节点接上，从而进行统一处理。

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 ->叶子)。

本文下面平衡的思路主要就是基于以上两种方式，另外要注意的是，红色和红色不能连一起的约束也不能违反。理解这个比较重要。

GP->P->叶子 的路径，要么经过N，要么经过S，如果h(P->N->叶子)和h(P->S->叶子)均少1了，自然h(GP->P->叶子)会少1。

删除平衡情形，主要根据 [兄节点的位置/颜色]、[兄的子节点的颜色]、[父节点颜色] 进行分类：

删除平衡的情形

N节点的位置知道后，S的位置自然也就知道了，相反亦可；这里以S位置作为分类，主要是为了便于理解和记忆。

情形1 当前节点为根节点（父节点为NULL）

比较特殊的情况，无需平衡操作。因为经过根节点的黑色数量少一个，意味着所有路径都少一个，已然平衡。

情形2 兄弟节点为黑色（S=黑）

情形2.1 兄弟的子节点全黑（SL/SR=黑）

兄弟节点的子节点全为黑色，也就意味着兄弟节点（S）可以涂红而不会和子冲突。S涂红后，也就实现了子平衡，
这时候我们看父节点是红是黑，再做处理。

情形2.1.1 父节点为黑色（P=黑）

此时将S涂红，父节点作为新的平衡节点N，递归上去处理。
这个也就是之前提到的h(P->N->叶子)不变，h(P->S->叶子)减1；而h(GP->P->叶子)，依然会比h(GP -> U ->叶子)少1，所以要递归上去处理。

情形2.1.1 兄黑-兄子全黑-父黑

情形2.1.2 父节点为红色（P=红）

此时将S涂红，P涂黑，平衡结束。
S涂红后，h(P->N->叶子)不变，h(P->S->叶子)-1，实现子平衡；因为P节点是红色的，如果将它涂黑，h(P->N->叶子)和h(P->S->叶子)均会+1，就可以恢复原来的状态了，而不用递归上去。

情形2.1.2 兄黑-兄子全黑-父红

情形2.2 兄弟的子节点不全黑

所谓的不全黑包括：[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黑】处理方式对称。

情形2.2.1 S为左子，SL红；S为右子，SR红

情形(1) S为黑色，S为左子，SL红时：
以P为支点右旋；交换P和S颜色，SL涂黑；平衡结束。
这里的平衡思路其实就是：h(P->S->叶子)不变（因为SL涂黑补回来了），h(P->N->叶子)+1（因为多了个黑色P）。

情形2.2.1-(1) S黑-S左-SL红

通常旋转后，新的P节点往往都会涂成原P的颜色：一是为了让GP-P不会颜色冲突；二是保持经过P的路径黑色数量不变。

---

对称的情形(2)：S为黑色，S为右子，SR红时：
以P为支点左旋；交换P和S颜色（S涂为P原颜色，P涂黑），SR涂黑；平衡结束。

情形2.2.1-(2) S黑-S右-SR红

情形2.2.2 S为左子，SL黑；S为右子，SR黑

情形(1) S为黑色，S为左子，SL黑
以S为支点左旋，交换S和SL颜色（SL涂黑，S涂红） ，此时转至情形2.2.1-(1) S左-SL红 进行处理。

情形2.2.1-(1) S黑-S左-SL黑

S涂红是为了使h(原S->SR->叶子)不变。

---

对称的情形(2) S为黑色，S为右子，SR黑
以S为支点右旋，交换S和SL颜色（SL涂黑，S涂红），此时转至2.2.1-(1) S右-SR红进行处理。

情形2.2.2-(2) S黑-S为右子-SR黑

情形3 兄弟节点为红色（S=红）

情形(1) S为左子时，以P进行右旋；
情形(2) S为右子时，以P进行左旋；
旋转后交换P和S的颜色（S涂红，P涂黑），此时以P作为当前平衡节点N，进入情形2-兄弟节点为黑色进行处理。

情形3 兄弟节点为红色

3.删除总结与实例

1. 删除动作（移除节点）之后，看看这个节点是不是黑色的叶子节点，如果不是，简单处理就可以达到平衡了；
2. 先看N是不是根节点，是的话啥时不用管；不是的话看兄弟什么颜色：
   2.1 兄弟是红色：进行旋转涂色，去到兄弟为黑色那里处理
   2.2 兄弟是黑色，看看兄弟子节点是不是全部都是黑。
   （1）全黑的话，看父什么颜色进行对应处理；
   （2）不全黑，看兄在的位置，兄在左的话，看兄的左子是不是红色，进行对应处理；兄在右的话，看兄的右子是不是红色，进行对应处理。

现在我们有一颗红黑树：

（1）删除50，删除动作-情形3 --> 删除动作-情形2，简单处理即可：

删除50

（2）删除70，即黑色叶子节点，进行平衡：

删除70

（3）删除60：

删除60

（4）删除10：

删除10

（5）删除20：

删除20