2-4树

通用红黑树

这里我们介绍红黑树，这是一种具有对数高度的二叉搜索树。红黑树是应用最广泛的几种数据结构之一。它们作为主要搜索结构出现在许多库实现中，包括 Java 集合框架以及多个 C++ 标准模板库的实现。此外，红黑树也被用于 Linux 操作系统内核中。红黑树之所以广受欢迎，原因如下：

1. 存储 n 个元素的红黑树高度至多为 $2 \log n$。
2. 红黑树上的 add(x) 和 remove(x) 操作在最坏情况下的时间复杂度为 $O(\log n)$。
3. 在执行一次 add(x) 或 remove(x) 操作时，摊还的旋转次数为常数。

前两个特性已经使红黑树优于跳表、Treap 和 scapegoat 树。跳表和 Treap 依赖随机化，其 $O(\log n)$ 的运行时间仅是期望值。Scapegoat 树虽然保证了高度上限，但 add(x) 和 remove(x) 仅在摊还意义下为 $O(\log n)$。第三个特性只是额外的优势：它表明插入或删除一个元素 $x$ 所需的时间远小于查找 $x$ 所需的时间。

注意：跳表和 Treap 在期望意义上也具备第三个性质。

然而，红黑树的优良特性也伴随着实现复杂性的代价。维持 $2 \log n$ 的高度上限并不容易，需要仔细分析多种情况。我们必须确保在每种情况下都执行正确的操作。一旦出现错误的旋转或颜色更改，就会引入难以理解和追踪的 bug。

在直接进入红黑树的实现之前，我们将先介绍一种相关数据结构：2-4 树。这有助于理解红黑树的发现过程，以及为何能够高效地维护这种结构。

2-4 树

2-4 树 是一种有根树，满足以下性质：

性质 1（高度）：所有叶子节点处于相同的深度。

性质 2（度数）：每个内部节点有 2、3 或 4 个子节点。

下图展示了一个高度为 3 的 2-4 树示例。

2-4 树的性质意味着其高度相对于叶子数量是对数级别的：

引理：含有 $n$ 个叶子的 2-4 树高度至多为 $\log n$。

证明：由于内部节点至少有两个子节点，若一棵 2-4 树的高度为 h，则其至少有 $2^{h}$ 个叶子。即：

$$n \geq 2^{h}$$

对不等式两边取对数得 $h \leq \log n$。

插入一个叶子节点

向 2-4 树中插入一个叶子节点非常简单（见下图）。

如果我们希望将新节点 u 作为某节点 w 的孩子添加到倒数第二层，则只需将 u 作为 w 的孩子。这显然保持了高度性质，但可能违反度数性质：如果 w 原本已有四个孩子，那么添加 u 后 w 就有了五个孩子。此时，我们将 w 分裂为两个节点 w 和 w’，分别拥有两个和三个孩子。但此时 w’ 没有父节点，因此我们递归地将 w’ 作为 w 的父节点的孩子。这可能导致 w’ 的父节点子节点过多，于是再次分裂。该过程持续进行，直到遇到一个子节点少于四个的节点，或者分裂了根节点 r 并生成两个节点 r 与 r’。在这种情况下，我们创建一个新的根节点，其子节点为 r 和 r’。这同时增加了所有叶子的深度，从而保持了高度性质。

由于 2-4 树的高度始终不超过 $\log n$，因此插入一个叶子节点的过程最多经过 $\log n$ 步即可完成。

删除一个叶子节点

从 2-4 树中删除一个叶子节点稍显复杂（见下图）。

要从其父节点 w 中删除叶子节点 u，只需将其移除。如果 w 在删除 u 前仅有两个孩子，那么删除后 w 只剩一个孩子，违反了度数性质。

为修复这一问题，我们查看 w 的兄弟节点 w’。由于 w 的父节点至少有两个孩子，因此 w’ 一定存在。如果 w’ 有三个或四个孩子，我们可以从 w’ 中取出一个孩子并转移给 w。这样 w 拥有两个孩子，w’ 拥有两或三个孩子，问题解决。

另一方面，如果 w’ 仅有两个孩子，则我们将 w 和 w’ 合并为一个新节点 w，该节点包含三个孩子。然后我们递归地从 w’ 的父节点中删除 w’。该过程持续进行，直到遇到某个节点 u，使得 u 或其兄弟节点拥有超过两个孩子，或者到达根节点。在后一种情况下，如果根节点只剩一个孩子，则删除根节点，并将其唯一的孩子设为新的根节点。这同时减少了所有叶子的深度，从而保持了高度性质。

同样，由于树的高度始终不超过 $\log n$，删除一个叶子节点的过程最多经过 $\log n$ 步即可完成。

红黑树：模拟 2-4 树

红黑树 是一种二叉搜索树，其中每个节点 u 都有一个颜色属性，颜色为红色或黑色。红色用数值 $0$ 表示，黑色用 $1$ 表示。

1class RedBlackTree(BinarySearchTree):
2    class Node(BinarySearchTree.Node):
3        def __init__(self, x):
4            super(RedBlackTree.Node, self).__init__(x)
5            self.colour = black
6        
7    def __init__(self, iterable=[]):
8        self.nil = RedBlackTree.Node(None)
9        self.nil.right = self.nil.left = self.nil.parent = self.nil
10        super(RedBlackTree, self).__init__([], self.nil)
11        self.r = self.nil
12        self.add_all(iterable)

在对红黑树进行任何操作之前和之后，均满足以下两个性质。这两个性质既可以用“红色”和“黑色”来描述，也可以用数值 $0$ 和 $1$ 来表达。

性质 3（黑高）：从根到任意叶子的路径上，黑色节点的数量相同。（任意根到叶子路径上颜色值之和相等。）

性质 4（无红边）：没有两个红色节点相邻。（对于任意节点 u，除根节点外，均有 u.colour + u.parent.colour $\geq 1$。）

注意，我们可以始终将红黑树的根节点 r 涂成黑色而不破坏上述任一性质，因此我们假设根节点为黑色，且所有更新红黑树的算法都会维护这一设定。另一个简化红黑树的技巧是将外部节点（由 nil 表示）视为黑色节点。这样一来，红黑树中的每一个真实节点 u 都恰好有两个子节点，且每个子节点的颜色都有明确定义。

下图展示了一个黑高为 3 的红黑树示例。外部（nil）节点以方形表示。