红黑树

__ryp__ · 2024-02-14 21:50:47 · 个人记录

红黑树的性质

• 每个节点或红或黑
• 根节点是黑色的
• 叶节点是黑色的
• 红节点的孩子是黑色的
• 某子树上根到叶子节点的简单路径上经过的黑色节点数相等，并将此量设为 \text{bh}(x)。

（注意这里的叶子节点是指没有权值的哨兵）

我们先证明红黑树的平衡性，即，红黑树的高度是 O(\lg (n+1)) 的。

引理 1 以 x 为根的子树，大小至少为 2^{\text{bh}(x)} - 1。

用归纳法进行证明。

• 当 x 是叶子节点时，显然成立。
• 否则，以 x 为根的子树的大小为：2\times (2^{\text{bh}(x)-1} - 1) + 1 = 2^{\text{bh}(x)}-1

证毕。

引理 2 以 x 为根的子树到其任意叶子节点的简单路径上，至少有一半的节点是黑色的。即，\text{bh}(x) \ge \dfrac h 2

结合性质 4，显然得证。

红黑树的平衡性证明 结合引理 1、2, 可知一棵 n 个节点的红黑树，有 n \ge 2^{h/2}-1。取对数得到：h \le 2\lg (n+1)，即 h = O(\lg (n+1)。

红黑树的插入

红黑树的插入，需要维护它的一些性质。我们按照普通二叉搜索树的方式插入，并将新节点标记成红色（因为处理黑高很麻烦），然后考虑哪些性质可能被违反：

• 性质 1：不违反
• 性质 2：如果新插入的节点就是根，那么违反
• 性质 3：不违反
• 性质 4：如果父节点是红色的，那么违反
• 性质 5：不违反

性质 2 的违反是边界情况，我们先考虑维护性质 4。

下面是平衡树标准的繁杂分类讨论……

我们设当前新加入的节点为 x，父节点为 y，叔节点（即它父亲的兄弟节点）为 z，祖父节点为 p，并以 c(x) 引用 x 的颜色，0 为黑色，1 为红色，那么已知：c(x) = 1，c(y)=1，c(p) = 0：

我们具体分析一下。

对于一个新加入的叶子节点，它可能面临哪些情况？

首先，当一个新的节点的父亲是红色的时候，我们知道：它一定没有兄弟节点。否则，它的兄弟 w 一定是黑色的。那么，显然 y 子树上黑高不平衡。得证。

否则，如果它的父亲是黑色的，那么这时候不违反任何性质。

于是我们知道，当最开始进入 fixup 过程的时候，一定是面临第一种情况。

红黑树的删除

很多人说红黑树的删除很恶心之类，但实际上和插入是一个原理，只需要分类讨论即可。

我们先按普通二叉树的删除方法来删除节点 x。具体即：

• 若 x 无孩子，直接删除
• 若 x 只有一个孩子，那么将此孩子提升到 x 的位置
• 否则，找 x 的后继，设为 y。当 y 不是 z 的直接右儿子时，我们以 y 的右儿子替换它。之后，我们用 y 替换 x。

我们记录 x 原来的位置被哪个点替代，设做 z。我们知道，如果 x 只有一个孩子，那么它一定是黑色的，删除它一定会导致这个子树上黑高变少。而当 x 有两个孩子的时候，黑高的变化依赖于替代它的节点的颜色。如果这个节点是红色的，那么它的父亲是黑色的，于是 x 的左子树上一定有一单位黑高用来平衡。于是，我们将 y 移动到 x 的位置不会影响黑高。

否则当这个节点是黑色的时候，我们推不出来什么，需要进行平衡。

下面是具体的平衡方法。我们设 x 为 x 原来位置上现在的节点，即 y 或 x 唯一的那个儿子。设 y 是 x 的父亲，z 是 x 的兄弟，\alpha 和 \beta 分别是 z 的两个子节点。

• 我习惯把边界条件放在前面。c(z) = 0 且 c(\beta) = 1 时，这时我们旋转 z，并 c(z) \gets 1, c(y) \gets 0, c(\beta) \gets 0。此时整个子树的左边多了一个黑色，右边仍然是一个黑色，平衡，达到边界。

• 同样 c(z) = 0，但 c(\alpha) = 1， c(\beta) = 0 时，我们旋转 \alpha，并使 c(\alpha) \gets 0, c(z) \gets 1，转化到前一种情况。

• c(z) = 1$，我们也没法直接得到一个黑节点，但可以转化下去。我们旋转 $z$，并使 $c(y) \gets 1, c(z) \gets 0

经过以上的情况，我们便可以平衡原子树上缺少的黑高，保持了红黑树的性质。

以上。