我已经是第三次学红黑树了。第一次只是把算法导论上头的代码给翻译过来抄了上去，还没调过；第二次囫囵吞枣学了学，大体上搞懂了这玩意儿为啥正确；第三次，也就是这一次，我觉得我才真正明白了这玩意儿的思路是什么样的。

首先红黑树有两条重要性质：

• 结点有红色黑色之分。红结点的儿子必须是黑的，黑结点的儿子任意。一个结点如果没有儿子，我们指定它的儿子连向一个特殊的黑色结点 NIL。

• 对于每个结点，它子树中任意一个叶子到它的路径上，经过的黑结点数量必须相同。如果我们定义黑高 $bh(x)$ 表示 $x$ 子树中叶子结点到它所经过的黑色结点数量，那么本条性质可以改写为：每个结点的黑高唯一确定。

事实上有一个不那么显然的性质：NIL 也是结点，所以根到所有 NIL 所经过的黑结点数量要相等。这几条限制共同限制了红黑树的树高是一定的。这个证明不难。可以像算法导论那样归纳证，也可以感性理解：因为最差情况也是红黑颜色交替，而黑高又要相等，因此

红黑树的插入比较简单。首先按照二叉树把新结点插入为一个红叶子。之所以为红，是为了防止调整黑高，不然很麻烦。然后我们需要处理的就是第一条性质。可以递归向上地处理。设当前处理的结点为 $x$，则有三种情况：

• 如果 $x$ 的父亲不是红色，维护完毕。否则，$x$ 的父亲是红色，$x$ 的祖父一定是黑色

• 如果 $x$ 的叔叔是红色的，那么我们可以直接把父亲和叔叔设为黑色，祖父变成红色，以在保证黑高不变的同时消除双红。随后，$x$ 更新到其祖父

• 如果 $x$ 的叔叔是黑色的，我们可以旋转父亲之后，把父亲设为红的，原祖父设为黑的，随后 $x$ 更新为父亲。

插入的核心思想就是消除双红的同时规避处理黑高。这还是比较简单的。

删除稍微麻烦一点儿。

删除一个结点，我们还是按照二叉树的方法。如果它左右儿子之一是空的，就用这个儿子替换它，随后向上更新。否则，找 $x$ 的后继 $y$，用这个后继替换 $x$ 的位置，$y$ 的位置用它的右儿子代替（因为它的左儿子一定空）。

这之后，我们要判断被移动的位置原来是不是个黑结点。把这个原位置叫做 $x$，那么如果 $x$ 原来是黑色的话，$x$ 及其上的所有点的黑高都不再平衡。

随后就是对黑高的修复。我们把当前 $x$ 的状态，看作是有两个黑结点的叠加态，也就是它对黑高的贡献为二，这样可以简单认为黑高没变。我们的任务是把这多余的一个贡献送给别人。

有两种基本情况，和另外两种转化为这两种基本情况的其他情况。

基本情况：

• $x$ 的哥哥是黑色，他哥哥的两个儿子也是黑色。此时，我们把多余的黑高送给父亲。同时为了维护哥哥的黑高，我们让哥哥变成黑色。随后，让 $x$ 更新为其父亲。

• $x$ 的哥哥是黑色，异向侄子是红色。此时，我们通过改变树的结构来把多余的黑高送出去。首先旋转叔叔，让他成为新的祖父。让原异向侄子变成黑的，以维护他的黑高。由于原哥哥变成了祖父，我们让父亲和它的颜色交换。

另两种情况的主要思路是转化为前两种：

• $x$ 的哥哥是红色。