算法刷题系列（六十）：平衡搜索树——从 AVL 到 B 树与 B+ 树

算法刷题系列（六十）：平衡搜索树——从 AVL 到 B 树与 B+ 树

普通二叉搜索树的性能取决于高度。连续插入已经有序的数据会得到一条链，查找退化到 O(n)。平衡搜索树通过维护高度约束，保证查找路径不会无限倾斜。

旧“查找树”笔记还列出了 AVL、B 树与 B+ 树。本篇从二叉树旋转讲到多路查找树，并解释为什么数据库和文件系统常使用 B 系列结构。

一、AVL 树：用高度差控制倾斜

AVL 树是一种自平衡二叉搜索树。对每个节点，左右子树高度差的绝对值不超过 1。插入或删除后，若某个祖先失衡，就沿路径向上更新高度并执行旋转。

四类局部失衡及其修复：

类型	失衡路径	修复方式
LL	左孩子的左侧增高	对失衡节点右旋
RR	右孩子的右侧增高	对失衡节点左旋
LR	左孩子的右侧增高	先左旋左孩子，再右旋失衡节点
RL	右孩子的左侧增高	先右旋右孩子，再左旋失衡节点

旋转只重连少量节点，不改变中序顺序，因此 BST 的有序性质仍成立。AVL 的查找、插入和删除为 O(log n)；维护平衡需要额外更新高度和旋转。

二、Java：一次右旋的指针重连

下面是 LL 情况的基础操作。完整 AVL 插入还需维护高度、计算平衡因子，并按四种情况选择旋转。

public class AvlRotation {
    static final class Node {
        int key;
        int height = 1;
        Node left;
        Node right;

        Node(int key) {
            this.key = key;
        }
    }

    static int height(Node node) {
        return node == null ? 0 : node.height;
    }

    static void updateHeight(Node node) {
        node.height = 1 + Math.max(height(node.left), height(node.right));
    }

    static Node rotateRight(Node root) {
        Node newRoot = root.left;
        Node middle = newRoot.right;
        newRoot.right = root;
        root.left = middle;
        updateHeight(root);
        updateHeight(newRoot);
        return newRoot;
    }

    public static void main(String[] args) {
        Node root = new Node(30);
        root.left = new Node(20);
        root.left.left = new Node(10);
        updateHeight(root.left);
        updateHeight(root);
        root = rotateRight(root);
        if (root.key != 20 || root.left.key != 10 || root.right.key != 30) {
            throw new AssertionError("rotation did not preserve the expected order");
        }
    }
}

三、Python：同一旋转操作

from __future__ import annotations

class Node:
    def __init__(self, key: int) -> None:
        self.key = key
        self.height = 1
        self.left: Node | None = None
        self.right: Node | None = None

def height(node: Node | None) -> int:
    return 0 if node is None else node.height

def update_height(node: Node) -> None:
    node.height = 1 + max(height(node.left), height(node.right))

def rotate_right(root: Node) -> Node:
    new_root = root.left
    if new_root is None:
        raise ValueError("right rotation requires a left child")
    middle = new_root.right
    new_root.right = root
    root.left = middle
    update_height(root)
    update_height(new_root)
    return new_root

root = Node(30)
root.left = Node(20)
root.left.left = Node(10)
update_height(root.left)
update_height(root)
root = rotate_right(root)
assert root.key == 20 and root.left.key == 10 and root.right.key == 30

四、B 树与 B+ 树：减少外存访问

二叉树每个节点最多有两个孩子。磁盘或 SSD 的一次块读取成本远高于内存中的整数比较，因此数据库更关心树高和每个节点能容纳多少键。

• B 树：一个节点可以包含多个有序键和多个孩子；所有叶子处在同一层，搜索、插入和删除通过分裂、合并等操作维持平衡。
• B+ 树：内部节点主要保存分隔键和子树指针，记录通常存于叶子；叶子常按顺序链接，范围扫描更方便。
• 节点扇出：一个节点容纳更多分支，整棵树高度通常更低，从而减少外存访问次数。

B 系列树的具体阶数定义在不同教材中有差异，阅读实现或题目时要先确认“阶”指最大孩子数还是其他容量约定。

五、如何选择与常见误区

结构	关注点	适用场景
普通 BST	实现简单，但不保证高度	小规模或已知输入分布
AVL	严格控制高度，旋转相对频繁	需要稳定查询深度的内存结构
红黑树	平衡约束较宽松，更新通常较少旋转	通用有序映射和集合
B/B+ 树	多路分支，降低外存层级访问	数据库索引、文件系统

常见错误是认为“平衡树就是 AVL”，或把 B 树与二叉树混为一类；B 树节点可有多个孩子。实现旋转时也不能只交换键值而忘记重接中间子树。

与系列其他篇章的连接

BST 的基本查找、插入和删除见第 59 篇；堆适合动态取最值，但不支持像搜索树那样按任意键定位。两种结构选择取决于查询和更新模式。

小结

平衡机制解决普通 BST 可能退化的问题。AVL 用局部旋转维持二叉高度约束；B 树和 B+ 树通过多路节点降低整棵索引树的层数，尤其适合昂贵的外存访问。