AVL 树：通过旋转保持平衡

我曾经把“AVL 树：通过旋转保持平衡”学成了一组互不相干的名词和代码。具体表现是：AVL 的四种旋转我最初完全靠图硬记，隔一段时间就忘，后来从失衡节点和插入方向重新推，才不再依赖口诀。后来我尝试只保留一个问题：它到底在减少哪一种重复工作？顺着这个问题，整块知识才稳定下来。

AVL 是严格自平衡的二叉搜索树。对任意节点，左右子树高度差的绝对值不超过 1。它保留 BST 的有序关系，同时把树高稳定控制在 O(log n)。

它从哪里来

AVL 树由 Georgy Adelson-Velsky 与 Evgenii Landis 在 1962 年发表，是最早的自平衡二叉搜索树之一。它用左右子树高度差约束树高，说明搜索树可以在每次更新后做局部旋转，从而保证最坏查询时间。

平衡因子

常见定义为：

balance(node) = height(left) - height(right)

合法值是 -1、0、1。插入或删除后若出现 2 或 -2，就要旋转。节点通常缓存高度，使每次更新只需根据两个孩子重新计算。

四种失衡

类型	新节点方向	修复方式
LL	左孩子的左侧	右旋
RR	右孩子的右侧	左旋
LR	左孩子的右侧	先左旋左孩子，再右旋
RL	右孩子的左侧	先右旋右孩子，再左旋

以右旋为例：

AVL 的 LL、RR、LR、RL 四种失衡与旋转图

图：直线失衡使用单旋，折线失衡使用双旋

a < x < b < y < c 的中序关系在旋转前后不变。旋转不是交换数值，而是局部重连节点，同时保持 BST 顺序。

private Node rotateRight(Node y) {
    Node x = y.left;
    Node middle = x.right;
    x.right = y;
    y.left = middle;
    updateHeight(y);
    updateHeight(x);
    return x;
}

private Node rebalance(Node node) {
    updateHeight(node);
    int balance = height(node.left) - height(node.right);
    if (balance > 1) {
        if (height(node.left.left) < height(node.left.right))
            node.left = rotateLeft(node.left);
        return rotateRight(node);
    }
    if (balance < -1) {
        if (height(node.right.right) < height(node.right.left))
            node.right = rotateRight(node.right);
        return rotateLeft(node);
    }
    return node;
}

插入流程

AVL 插入先按 BST 规则递归找到位置，再沿返回路径更新高度并重平衡：

private Node insert(Node node, int value) {
    if (node == null) return new Node(value);
    if (value < node.value) node.left = insert(node.left, value);
    else if (value > node.value) node.right = insert(node.right, value);
    else return node;
    return rebalance(node);
}

递归返回值必须重新赋给 node.left 或 node.right，因为旋转后子树根可能已经变化。最外层同样要写 root = insert(root, value)。

左旋与右旋要保持三类信息

BST 的中序顺序。
父子引用完整，无节点丢失。
高度从下到上重新计算。

以左旋为例：

private Node rotateLeft(Node x) {
    Node y = x.right;
    Node middle = y.left;
    y.left = x;
    x.right = middle;
    updateHeight(x);
    updateHeight(y);
    return y;
}

先保存 middle 是关键。它仍大于 x、小于 y，旋转后应成为 x 的右子树。

高度更新顺序

旋转后应先更新变成下层的旧根，再更新新根。顺序错误会把旧高度继续传播，造成后续误判。实现时最好把“不变量检查”写入测试：递归验证有序性、高度值和平衡因子，而不只是断言查询结果。

private int verify(Node node, long min, long max) {
    if (node == null) return 0;
    if (node.value <= min || node.value >= max) throw new AssertionError("BST order");
    int left = verify(node.left, min, node.value);
    int right = verify(node.right, node.value, max);
    if (Math.abs(left - right) > 1) throw new AssertionError("AVL balance");
    int expected = Math.max(left, right) + 1;
    if (node.height != expected) throw new AssertionError("height cache");
    return expected;
}

验证器必须独立重新计算高度，不能直接相信待测树缓存的 height。

AVL 与红黑树

AVL 更严格平衡，查询密集场景可能拥有更短路径；红黑树允许更松的高度边界，更新时通常旋转更少。Java 的 TreeMap/TreeSet 使用红黑树，不代表 AVL 没有价值，而是通用容器需要在查询、更新和实现成熟度之间平衡。

删除比插入更复杂

插入后通常沿祖先路径找到第一个失衡点即可修复；删除可能让多个祖先高度继续下降，需要一路向上检查。若业务没有特殊需求，不应把教学版 AVL 直接用在生产系统。

删除仍先执行 BST 删除，再对返回路径上的每个节点调用 rebalance。与插入不同，判断双旋方向时不能只看被删除值的位置，应读取孩子自身的平衡因子，因为高度变化可能来自另一侧。

性能与使用场景

AVL 的高度约束比红黑树严格，读多写少、有序查询密集时可能拥有更短路径；更新频繁的通用 Map 往往更偏向红黑树。实际选择还受标准库、内存布局和并发方案影响，不能仅凭旋转次数下结论。

测试清单

分别构造 LL、RR、LR、RL 四种旋转。
递增、递减和随机插入后验证树高。
删除叶子、单孩子、双孩子和根。
每次操作后运行完整不变量验证器。
与 TreeSet 对照外部集合行为。