数据结构与算法 / 系统课时

AVL 树

AVL 树

普通二叉搜索树在有序输入下可能退化为链表,使查找从对数级下降到线性级。AVL 树通过记录节点高度并在插入后旋转失衡子树,让树高持续保持在 O(log⁡n)O(\log n),从而稳定查找、插入和删除的性能。

学习目标

  • 能根据左右子树高度计算平衡因子,并判断节点是否失衡。
  • 能区分 LL、RR、LR、RL 四种失衡类型并选择正确旋转。
  • 能实现可运行的 AVL 插入,并分析其时间与空间复杂度。

平衡机制与旋转

AVL 树首先是一棵二叉搜索树,因此任意节点左子树中的键都更小,右子树中的键都更大。它额外要求每个节点的平衡因子满足 -1、0 或 1。本课约定空子树高度为 0、叶节点高度为 1:

balance(v)=height(v.left)−height(v.right)balance(v)=height(v.left)-height(v.right)

插入新键后,只需沿递归返回路径更新高度。若某个节点的平衡因子绝对值大于 1,说明失衡首次出现;旋转会改变局部父子关系,但必须保持中序遍历顺序不变。

失衡类型 新键所在方向 修复动作
LL 左孩子的左侧 对失衡节点右旋
RR 右孩子的右侧 对失衡节点左旋
LR 左孩子的右侧 先对左孩子左旋,再对失衡节点右旋
RL 右孩子的左侧 先对右孩子右旋,再对失衡节点左旋

AVL 树四种失衡与旋转关系

单次旋转只修改常数个指针并重算少量高度,成本为 O(1)O(1)。AVL 树高度为 O(log⁡n)O(\log n),所以查找和插入均为 O(log⁡n)O(\log n);存储节点需要 O(n)O(n) 空间,递归插入额外使用 O(log⁡n)O(\log n) 调用栈。

完整可运行示例

下面的 Java 17 程序忽略重复键,在递归插入返回时更新高度,并依据新键方向识别四种失衡。旋转后必须先更新原根高度,再更新新根高度,因为新根的高度依赖已经调整过的子树。

java
import java.util.ArrayList;
import java.util.List;

public class AvlTreeDemo {

    private static class Node {
        int key;
        // 约定空子树高度为 0,因此叶节点初始高度为 1。
        int height = 1;
        Node left;
        Node right;

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

    private Node root;

    public void insert(int key) {
        root = insert(root, key);
    }

    private Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key);
        }
        if (key < node.key) {
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            node.right = insert(node.right, key);
        } else {
            // 本示例将结构作为集合使用,重复键不插入。
            return node;
        }

        // 先更新当前节点高度,再根据平衡因子选择旋转。
        updateHeight(node);
        int balance = balanceFactor(node);

        // 四个分支依次对应 LL、RR、LR、RL。
        if (balance > 1 && key < node.left.key) {
            return rotateRight(node);
        }
        if (balance < -1 && key > node.right.key) {
            return rotateLeft(node);
        }
        if (balance > 1 && key > node.left.key) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
        if (balance < -1 && key < node.right.key) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }
        return node;
    }

    private Node rotateRight(Node top) {
        Node newTop = top.left;
        // 中间子树需要重新挂接,才能保持二叉搜索树的中序顺序。
        Node movedSubtree = newTop.right;
        newTop.right = top;
        top.left = movedSubtree;
        updateHeight(top);
        updateHeight(newTop);
        return newTop;
    }

    private Node rotateLeft(Node top) {
        Node newTop = top.right;
        // 中间子树需要重新挂接,才能保持二叉搜索树的中序顺序。
        Node movedSubtree = newTop.left;
        newTop.left = top;
        top.right = movedSubtree;
        updateHeight(top);
        updateHeight(newTop);
        return newTop;
    }

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

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

    private int balanceFactor(Node node) {
        return height(node.left) - height(node.right);
    }

    public void printSummary() {
        List<Integer> ordered = new ArrayList<>();
        collectInOrder(root, ordered);
        System.out.println("中序遍历: " + ordered);
        System.out.println("根节点: " + root.key);
        System.out.println("树高: " + root.height);
        System.out.println("根平衡因子: " + balanceFactor(root));
    }

    private void collectInOrder(Node node, List<Integer> ordered) {
        if (node == null) {
            return;
        }
        collectInOrder(node.left, ordered);
        ordered.add(node.key);
        collectInOrder(node.right, ordered);
    }

    public static void main(String[] args) {
        AvlTreeDemo tree = new AvlTreeDemo();
        int[] values = {30, 20, 10, 25, 28, 27};
        for (int value : values) {
            tree.insert(value);
        }
        tree.printSummary();
    }
}

将代码保存为 AvlTreeDemo.java,然后编译运行:

bash
javac AvlTreeDemo.java
java AvlTreeDemo

预期输出:

text
中序遍历: [10, 20, 25, 27, 28, 30]
根节点: 25
树高: 3
根平衡因子: 0

中序结果严格递增,说明旋转没有破坏二叉搜索树顺序;根平衡因子为 0,并不代表所有节点都必须为 0,只要每个节点都位于合法范围即可。

常见错误与练习

最常见的错误是只旋转指针却忘记更新高度,后续平衡因子会基于旧数据计算;另一个错误是把 LR 当成一次右旋,导致中间键无法成为局部根。调试时可在每次插入后递归校验每个节点的存储高度与实际高度是否一致。

  1. 将输入改为 {30, 10, 20},确认程序触发 LR 双旋转,并输出根节点 20。
  2. 增加 contains(int key),分别查询存在与不存在的键,验收条件是每次查询只沿一条根到叶路径移动。
  3. 编写递归校验方法,要求同时验证二叉搜索树顺序、存储高度和平衡因子,任一条件失败时返回 false。

本课总结

  • AVL 树用严格的高度差约束避免二叉搜索树退化,核心状态是节点高度与平衡因子。
  • LL、RR 使用单旋转,LR、RL 使用双旋转;旋转必须同时维护搜索顺序、子树连接和高度。
  • AVL 树的查找与更新保持 O(log⁡n)O(\log n),适合重视稳定查询延迟的内存索引。

下一课预告

下一课将学习“红黑树原理”,理解它如何用较宽松的颜色约束、旋转和重新着色换取更少的结构调整。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

AVL 树

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通