AVL tree · 拆解与动手

AVL tree (Adelson-Velsky & Landis, 1962) 是历史上第一棵 self-balancing BST。它的不变量只有一条：每个 node 的 balance factor bf = height(left) − height(right) ∈ {−1, 0, +1}。插入 / 删除后从受影响 node 沿父链向上回溯 (retrace): 更新 height、检查 bf，一旦某处 |bf| = 2 就用 rotation 把它压回平衡。这条约束比 red-black tree 更严格，因此 AVL 树更矮、查找更快，代价是增删时的修复更频繁。本页从 balance factor 的定义出发，先看它凭什么把树高锁在 $~1.44\cdot \log _2n$，再亲手过一遍四种失衡形态 (LL / RR / LR / RL) 的旋转，然后单步插入与单步删除，最后对比它与 red-black tree 的取舍。阅读前需要了解 binary search tree (BST) 的基本规则：每个 node 左子树更小、右子树更大，查找 / 插入沿比较路径下降。

本页依次：balance factor 与树高 → 四种失衡形态与旋转 → 单步插入 → 查询与删除 → 番外：AVL vs 红黑树。

1 · balance factor: 一条约束如何把树高锁在 O(log n)

BST 的查找代价正比于树高。问题在于：同一组值，插入顺序不同，树高可以从 $O(\log n)$ 一路烂到 $O(n)$。最坏情形毫不罕见——把已排序的数据顺序插入 naive BST，它会退化成一根只往右长的链表。AVL 的做法是给每个 node 定义一个可局部检查的量，并强制它落在一个很窄的区间内。

这条约束为什么够用？设 N(h) 为「高度为 h 的 AVL 树最少含多少 node」。一棵高 h 的 AVL 树，其较高一侧子树高 $h-1$，另一侧至少 $h-2$（否则 bf 就超界了），于是 $N(h) = N(h-1) + N(h-2) + 1$——这正是 Fibonacci 递推。解得 $N(h) \approx \phi ^h$，反过来高度 $h \le 1.44\cdot \log _2(n+2) - 0.33$。所以 AVL 树高被牢牢压在 $O(\log n)$，且常数 1.44 比 red-black tree 的 2 更小——这就是「AVL 更矮」的来源。

1.1 · 动手：同一串值，AVL vs naive BST

左边是 AVL（每步自动再平衡），右边是 naive BST（从不旋转）。点「插入下一个」逐个喂值，或换不同的输入序列，盯着两棵树的高度差距。试试「升序 1..15」：naive BST 立刻退化成右斜链，AVL 仍是一棵矮树。

2 · 四种失衡形态：每一种对应一种旋转修法

当某个 node 的 |bf| = 2，说明它的一侧子树比另一侧高了 2。失衡只可能是四种形态之一，取决于「重的那一侧」与「重侧孩子又往哪边重」。其中两种 (LL / RR) 一次旋转即可，另两种 (LR / RL) 需先把内侧扳成外侧、再旋一次。所有 AVL 的再平衡最终都归结到这四种。

下面每个按钮构造一棵恰好触发该形态的最小子树：前两个值已平衡插入，点按钮后单步插入第三个值，先看它如何把某个 node 顶成 |bf| = 2（该 node 变红），再看旋转怎么把它压回平衡。inorder 全程不变。

3 · 插入：下降建叶，再沿父链回溯修平衡

插入分两段。第一段是普通 BST 插入，第二段是 AVL 独有的回溯再平衡 (retrace)。若不熟悉旋转的四种形态，可先看上文 四种失衡形态与旋转 一节。

输入一个数点「插入」，再用「下一步」逐步看下降、回溯、bf 变化与旋转；旁白说清属于哪种形态。每次插入完成后校验全部不变量。新树建议先点「示例序列」连插几个，造出需要旋转的局面。

4 · 查询与删除：删除为什么可能旋转多次

查询在 AVL 里和普通 BST 一字不差：从根逐次比较、向左或向右下降。AVL 不改查找逻辑，只是凭 $|bf| \le 1$ 把树高压在 $~1.44\cdot \log _2n$，让这条比较路径足够短。先在下面查一个值，看高亮的下降路径。

删除才是与插入真正不同的地方。先做 BST 删除（有两个孩子时用中序后继的值顶替、改删后继），再从物理删除点的父节点沿父链回溯。区别在于： 插入使某路径变长 1，一次旋转就把高度还原、不再上传；而删除使某路径变短 1，旋转后子树可能整体再矮 1，从而令更上层继续失衡——因此删除最坏需要 $O(\log n)$ 次旋转，要一路回溯到根。

5 · 番外：AVL vs red-black tree，两种平衡哲学

AVL tree (1962) 与 red-black tree（Guibas & Sedgewick, 1978，源自 Bayer 1972 的 symmetric binary B-tree）是 self-balancing BST 的两大主流。它们解决同一个问题——防止 BST 退化——却选择了平衡严格度的两端。这节梳理它们的取舍与各自的工程归宿。

5.1 · 核心区别：平衡的「严」与「松」

AVL 用高度维持平衡：强制每个 node $|bf| \le 1$，约束很严，树几乎总是接近完美平衡。red-black tree 用颜色维持平衡：5 条 property 只保证「最长路径不超过最短路径的 2 倍」，约束较松，允许树长得更歪一点。一句话：AVL 把树修得更直，red-black 让树歪得有限度。

5.2 · 该用哪个：取决于读写比

5.3 · 为什么标准库大多选了 red-black?

通用容器无法预判使用者的读写比，而写入路径的最坏延迟更可控、更重要：red-black 把单次增删的旋转次数封死在常数（插 ≤ 2、删 ≤ 3）,AVL 的删除却可能 O(log n) 次旋转。对追求稳定最坏写入的标准库，这个保证比「查找快一点点」更值钱——何况两者查找都是 O(log n)，常数差距在多数负载下并不显著。于是 red-black tree 成了语言标准库与内核的默认选择，AVL 则更多出现在查询密集的专用场景。