第 11 章平衡树¶

原作：Josh Hug，UC Berkeley CS61B Spring 2021 配套读本。
中文翻译版，仅供非商业学习；采用 CC BY-NC-SA 4.0 许可。
原始网站：https://joshhug.gitbooks.io/hug61b/content/

11.1 B 树入门¶

二叉树高度¶

二叉搜索树最好与最坏结构的运行时间差异非常大：

最坏：Θ(N)；
最好：Θ(log N)。

如果树非常细长，它实际上接近链表，操作需要线性时间；如果树枝繁叶茂，高度约为 log N，操作就是对数时间。

大 O 与最坏情况¶

大 O 不等于最坏情况。大 O 是上界；只要函数最终不超过该界，就属于这个大 O 集合。最坏情况描述则更具体。

例如，若说“酒店最贵房间是 500 美元”，只有确实达到 500 美元的酒店符合；若说“所有房间价格是 O(500)”，大量更便宜酒店也满足这个宽松上界。

因此，即使 BST 最坏运行时间是 Θ(N)，它也同时属于 O(N²)。后者正确，但信息更少。

BST 性能术语¶

深度（depth）：某结点与根之间的边数；
高度（height）：树中结点的最大深度；
平均深度：所有结点深度的平均值：

(Σ dᵢ nᵢ) / N

其中 dᵢ 是深度，nᵢ 是该深度的结点数。

树的高度决定最坏运行时间，因为最坏情况下目标位于最底层。平均深度则决定典型或平均查找成本。

插入顺序¶

BST 的插入顺序决定树高。

练习 11.1.1。 对整数 1 到 7：什么顺序产生最坏高度？什么顺序产生最好高度？

答案：

最坏：按 1,2,3,4,5,6,7 插入，形成单链；
最好：先 4，再 2、6，最后 1、3、5、7，形成满而平衡的树。

不一定必须精心设计顺序。随机顺序插入 BST 时，期望平均深度和高度都是 Θ(log N)。

但现实数据可能实时到达，程序只能按到达顺序插入，无法先随机打乱。下一节将学习始终自动保持平衡的树。

11.2 B 树¶

普通 BST 的问题在于：新键总是作为新的叶子插入，因此树高可能不断增加。即使一开始很平衡，某些插入顺序也会破坏结构。

一个大胆想法是：不要立刻创建新叶子，而是把新键直接加入已有叶结点。这样树高不会增加。

但若一个结点无限容纳元素，查找结点内部某个键仍可能需要线性扫描，最终又退化为 Θ(N)。

解决办法是限制单个结点可保存的键数。假设上限为 3 个键；若再插入一个导致出现 4 个键，就把结点拆分，并把中间键上推到父结点。

例如包含 15 和 17 的结点有三个孩子，分别存放小于 15、介于 15 与 17、以及大于 17 的键。结点内部键保持有序，所以仍能利用搜索树思想。

通过从中间拆分结点，可以始终保持所有叶子位于同一层。这类树称为 B 树。常见特例包括：

2-3 树：每个内部结点有 2 或 3 个孩子，即含 1 或 2 个键；
2-3-4 树：每个内部结点有 2、3 或 4 个孩子，即含 1、2 或 3 个键。

插入过程¶

对 2-3-4 树：

像普通搜索树一样向下走，找到应插入的叶结点；
把新键加入该叶结点；
若结点溢出为 4 个键，就拆分，并把中间偏左键上推，重新分配孩子；
若父结点因此溢出，继续向上拆分；
直到某个父结点能够容纳，或根被拆分并生成新根。

2-3 树过程类似，只是在临时出现 3 个键时把中间键上推。

可通过可视化练习进一步熟悉。

11.3 B 树不变量与运行时间¶

普通 BST 的高度会受插入顺序强烈影响。B 树也可能因顺序得到不同具体高度，但它始终保持“矮而宽”。

练习 11.3.1。 按顺序把 1 到 7 插入 B 树，观察高度。能否改变顺序进一步降低高度？

一种能得到高度 1 的顺序是：

2, 3, 4, 5, 6, 1, 7

B 树的重要不变量：

所有叶子到根的距离相同；
含 k 个键的非叶结点恰好有 k+1 个孩子。

这两个条件共同保证树始终枝繁叶茂并保持完美平衡。

运行时间¶

设每个结点最多有 L 个键，L 是固定常数。

最坏查找需要：

沿树高访问 O(log N) 个结点；
在每个结点中检查至多 L 个键。

总工作为：

O(L log N) = O(log N)

因为 L 是常数。

B 树删除更复杂，本课程正文不展开，可参考附加幻灯片。

总结¶

BST 最好高度 Θ(log N)，最坏高度 Θ(N)；
大 O 不等于最坏情况；
B 树修改了二叉搜索树结构，避免线性高度；
一个结点可保存 1 到 L 个键；
查找类似普通搜索树；
插入把键加入已有叶结点，溢出时拆分；
所有叶子保持同层，操作为 O(log N)；
B 树实现更复杂，但能高效处理任意插入顺序。

11.4 树旋转¶

B 树始终平衡，但实现很困难：结点能存多个键，拆分与孩子重排都较复杂。我们希望找到一种仍使用普通 BST 结点、却能够保持平衡的方法。

BST 的多种结构¶

同一组键可以组成多种都满足 BST 不变量的结构。下面各树都只包含 1、2、3：

不同插入顺序会得到不同结构。即使结点已经存在，也可以通过旋转（rotation）改变结构，同时保持所有键的中序顺序不变。

左旋与右旋¶

形式定义：

rotateLeft(G)：令 x 为 G 的右孩子，把 G 变成 x 的左孩子；
rotateRight(G)：令 x 为 G 的左孩子，把 G 变成 x 的右孩子。

左旋示意：

设 P 是 G 的右孩子。左旋时：

P 上升为子树新根；
P 原来的左子树交给 G 作为右子树；
G 下沉为 P 的左孩子。

旋转可以发生在非根结点：暂时断开该子树与父结点的连接，旋转，再把新子树根接回去。

简化实现：

private Node rotateRight(Node h) {
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    return x;
}

private Node rotateLeft(Node h) {
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    return x;
}

练习 11.4.2。 把图中左树变成右树需要哪些旋转？

答案：

rotateRight(3)
rotateLeft(1)

旋转可以把一棵不平衡 BST 完全重新平衡。下一节将学习一种通过旋转自动维持平衡的树。

11.5 红黑树¶

2-3 树始终平衡，但实现复杂。能否用普通 BST 结点实现一种与 2-3 树结构等价、因而同样平衡的树？这就是红黑树的出发点。本节具体讨论左倾红黑树（LLRB），它对应 2-3 树。

从 2-3 树到 BST¶

2-3 树中的 2-结点本身就与普通 BST 结点相同，无需修改。

对于含两个键的 3-结点，可以想象加入一个不保存信息的“胶水结点”，把两个键绑在一起：

但额外结点浪费空间，也让代码丑陋。更好的办法是使用胶水边：

约定较小键作为较大键的左孩子，并把连接二者的特殊边标为红色；普通 BST 边标为黑色。于是得到左倾红黑树。

每棵 2-3 树都唯一对应一棵 LLRB。一般红黑树则可对应 2-3-4 树。

LLRB 不变量¶

与 2-3 树一一对应；
不允许某个结点同时参与两条连续向下的红边；
不允许红色右边，红边必须左倾；
从根到任意空叶子的路径包含相同数量的黑边；
高度不超过对应 2-3 树高度的两倍。

插入¶

理论上可以先向 2-3 树插入，再转换为 LLRB，但这失去了简化实现的意义。实际做法是先像普通 BST 一样递归插入，再用旋转与颜色翻转修复不变量。

任务一：新边颜色¶

2-3 树插入本质上是把新键加入某个叶结点，因此 LLRB 中新结点与父结点之间的边应设为红色。

任务二：修复右倾红边¶

LLRB 不允许红色右边。如果右孩子为红而左孩子不红，就对当前结点左旋：

若左右孩子都为红，则暂时保留，交给颜色翻转处理。

任务三：修复连续左红边¶

若当前结点的左边为红，左孩子的左边也为红，就出现了非法的临时 4-结点。先右旋：

随后翻转相关颜色，这等价于 2-3 树中把中间键向父结点上推并拆分临时 4-结点。

修复规则汇总：

插入新结点时使用红边；
若出现右倾红边且左边不红：左旋；
若出现两条连续左红边：右旋；
若左右孩子都为红：颜色翻转，模拟结点拆分。

可能需要从递归底部向上连续执行多次修复，直到整棵树重新满足不变量。

运行时间¶

LLRB 与 2-3 树一一对应，且高度最多是对应 2-3 树的两倍。因此查找和插入都为 Θ(log N)。

抽象插入代码：

private Node put(Node h, Key key, Value val) {
    if (h == null) {
        return new Node(key, val, RED);
    }

    int cmp = key.compareTo(h.key);
    if (cmp < 0) {
        h.left = put(h.left, key, val);
    } else if (cmp > 0) {
        h.right = put(h.right, key, val);
    } else {
        h.val = val;
    }

    if (isRed(h.right) && !isRed(h.left)) {
        h = rotateLeft(h);
    }
    if (isRed(h.left) && isRed(h.left.left)) {
        h = rotateRight(h);
    }
    if (isRed(h.left) && isRed(h.right)) {
        flipColors(h);
    }

    return h;
}

代码相当短，但背后维持了严格的数学对应关系。

总结¶

普通 BST 简单，但可能失衡并退化为线性时间；
2-3 树始终平衡，但实现麻烦；
LLRB 用普通 BST 结点和带颜色的边表示 2-3 树；
插入实现相对简洁，删除仍然复杂；
Java 的 TreeMap 使用红黑树，但不是左倾版本；
LLRB 对应 2-3 树，一般红黑树可对应 2-3-4 树；
实现比普通 BST 复杂，但提供稳定的 Θ(log N) 性能。

第 11 章 平衡树¶

11.1 B 树入门¶

二叉树高度¶

大 O 与最坏情况¶

BST 性能术语¶

插入顺序¶

11.2 B 树¶

插入过程¶

11.3 B 树不变量与运行时间¶

运行时间¶

总结¶

11.4 树旋转¶

BST 的多种结构¶

左旋与右旋¶

11.5 红黑树¶

从 2-3 树到 BST¶

LLRB 不变量¶

插入¶

任务一：新边颜色¶

任务二：修复右倾红边¶

任务三：修复连续左红边¶

运行时间¶

总结¶

第 11 章平衡树¶