本文共 1901 字，大约阅读时间需要 6 分钟。

还没来得及作图，但我认为自己讲解得还是足够详细了。

红黑树是二叉搜索树的一种，进一步也是二叉平衡搜索树的一种。其插入删除之后的调整比较复杂。

因为简单的二叉搜索树很可能退化为链表，二叉平衡搜索树的条件又太严苛。基本上每做一次插入删除都需要调整平衡。实现的过程中确实发现很复杂，情况特别多。插入很快能写出来。而删除的情况尤其复杂。但只要抓住两点，删除调整最多需要旋转3次即可插入需要两次、面向测试用例编程，总是可以把它写出来的。

首先红黑树相比于普通的二叉搜索树有一下规则：

（1）根节点为黑色；

（2）父子不能同为红节点；

（3）从根节点到叶子节点每条路径的黑节点数量（简称黑高）相同；

（4）可以假定所有空子节点为黑色。

添加较为简单，由于有黑高相等的约束。所以我们假设插入的节点是红色的，然后根据各种不同的情况向上变色或旋转调整。可能会疑惑，这样的话岂不是黑高一直不会增加？其实我们调整到根节点为红时，直接将根节点置为黑色就可以了。这样黑高就会增加。

插入后的调整可以分为以下情况：

1、插入节点的父节点是黑；

2、插入节点的祖父节点为黑，父节点和其兄弟节点都为红；

3、插入节点的祖父节点为黑，父节点为红以及兄弟节点为黑。

插入后对应这三种情况的调整使得红黑树的三种规则满足也很简单。

第一种情况直接不用调整。

第二种情况，直接置父节点和叔节点为黑，置祖父节点为红。把祖父节点当作插入节点递归处理即可。

第三种情况，如果不是‘人’字型，先旋转插入节点的父节点，（使得插入节点，父节点，兄弟节点和祖父节点排列成‘人’字型）。然后朝着‘人’字型短的那边旋转祖父节点，置原祖父节点为黑色，原父节点为红色即可。

删除的时候，我们可以尽量让待删节点为叶子节点，这样删除更简单。做法就是让待删节点和它的后继（前驱也可以）节点值交换。转换后的待删节点一定最多只有一个子节点。

删除后的调整可以分为以下情况：

1、待删节点为红结点；

2、待删节点为黑色节点，有红色子节点；

3、待删节点的父节点为红色；

4、待删节点的兄弟节点为红；

5、待删节点的兄弟节点为黑：5.1兄弟节点的子节点都为黑，5.2兄弟节点的子节点有红节点；

情况1：由于我们让待删节点最多有一个子节点，所以对于情况1，直接删掉该节点然后让其子节点代替它的位置即可，因为该节点是红节点，所以删掉它并不会影响黑高。

情况2：我们直接让该节点和它的子节点的值呼唤，然后删掉其子节点即可，因为删掉的是红节点所以并不会影响黑高。

情况3：因为现在待删节点是黑而其父节点都为红色，而待删节点删除后，会导致黑高减少。我们得想办法将黑节点的利用率最大化，那就是旋转使得黑节点朝根部向上走。父亲是红，说明兄弟节点一定是黑，所以我们可以朝待删节点这边旋转祖父节点，使得兄弟节点贡献给待删节点这条分支。但是这样可能会导致父节点的红色和兄弟节点的儿子形成‘双红’的情况，所以我们应该旋转之后检测一下，如果父节点处出现‘双红’则调用插入后的调整函数调整即可。

情况4：当有兄弟节点为红色的时候，我们可以利用起来，因为现在待删节点和其父节点都为黑色，而待删节点删除后，会导致黑高减少。我们得想办法利用到能利用的红节点。所以我们可以先讲兄弟节点置黑。这个时候父节点的非待删子节点高度会增加一，这个时候我们可以继续旋转，让这个子节点旋上来。这样使得父节点整个分支高度增加一。这个时候我们有两种选择。选择1：使当前祖父节点的黑色和正常分支的红色颜色互换，这样既满足了正常分支仍然正常，而且增高的分支的高度减一（前提是正常分支为红节点）。选择2：将父节点置红，这个时候又可能有‘双红’冲突，我们可以调用插入后调整的函数进行调整。或者我们如果不想调用插入后调整，我们可以假设一定先考虑选择1，那么只有在原兄弟节点的靠近待删节点子节点的子节点是一红一黑的时候才会出现‘双红’冲突，我们总是可以通过选择将一红一黑的情况通过旋转给提前消除掉，就没有‘双红’的担忧了。

情况5.1：我们将兄弟节点置为红，这个时候整个父节点的高度都是平衡的但是黑高少了一，所以我们只需要令父节点为待删节点递归处理即可（注意不能真正的直接调用删除后调整函数，因为你不是真的要删除该新的待删节点）。

情况5.2：如果兄弟节点的子节点中有一个红节点，和前面类似我们可以利用起该红节点，首先将其置黑，然后如果这个节点在内侧（靠近待删节点）。我们得将兄弟节点朝着外侧旋转，调整黑高较高的分支在外侧（类似于添加后调整处所做的‘人字形调整’）。先一步就是旋转父节点重新达到平衡即可。

到此红黑树的添加删除后的调整就讲完了。

转载地址：http://qyqgn.baihongyu.com/