Java 中的 AVL 树详解 | Baeldung中文网

1. 简介

本文将深入介绍 AVL 树，重点讲解其在 Java 中的实现，涵盖插入、删除和查找等核心操作。AVL 树作为最早提出的自平衡二叉搜索树之一，能有效避免普通 BST 在极端情况下退化为链表的问题，从而保证操作效率稳定。

2. 什么是 AVL 树？

AVL 树是以其发明者 Adelson-Velsky 和 Landis 命名的自平衡二叉搜索树（BST）。

✅ 自平衡的核心在于：每次插入或删除节点后，树会通过特定规则自动调整结构，确保整体高度维持在 O(log N) 级别。

普通 BST 的最坏时间复杂度取决于树的高度。设想一种极端情况：所有节点都只有左子或右子，此时树退化为链表，高度为 N，查找时间变为 O(N)，性能急剧下降。而 AVL 树的目标就是将最大高度控制在接近 log(N)。

每个节点都有一个平衡因子（Balance Factor），定义为：

平衡因子 = 右子树高度 - 左子树高度

⚠️ 在 AVL 树中，任意节点的平衡因子只能是 -1、0 或 1。一旦某个节点的平衡因子变为 2 或 -2，就必须通过旋转操作进行重新平衡。

下面是节点和 AVL 树的基本结构定义：

public class Node {
    int key;
    int height;
    Node left;
    Node right;

    public Node(int key) {
        this.key = key;
        this.height = 0;
    }
}

public class AVLTree {
    private Node root;

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

    int height(Node n) {
        return n == null ? -1 : n.height;
    }

    int getBalance(Node n) {
        return (n == null) ? 0 : height(n.right) - height(n.left);
    }
}

3. 如何平衡 AVL 树？

AVL 树在每次插入或删除后，都会从修改点向上回溯，检查路径上每个节点的平衡因子。若发现某节点平衡因子为 2 或 -2，则立即触发旋转（Rotation）操作进行调整。

主要旋转方式有两种：

✅ 左旋转（Left Rotation）
✅ 右旋转（Right Rotation）

3.1 右旋转

右旋转适用于左子树过高的情况。

假设有一棵子树 T1，根节点为 Y，X 是 Y 的左子节点，Z 是 X 的右子节点。根据 BST 性质，有 X < Z < Y。

对 Y 执行右旋转后，得到新结构 T2：X 成为新根，Y 成为 X 的右子，Z 成为 Y 的左子。BST 的顺序关系依然成立。

右旋转代码实现如下：

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

3.2 左旋转

左旋转用于处理右子树过高的情况。

假设子树 T1 中，Y 为根，X 是 Y 的右子，Z 是 X 的左子。此时有 Y < Z < X。

对 Y 执行左旋转后，X 成为新根，Y 成为 X 的左子，Z 成为 Y 的右子。BST 性质保持不变。

左旋转实现：

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

3.3 重新平衡策略

单次旋转不足以应对所有失衡场景，实际中需要组合使用。主要分为四种情况：

情况一：右右（RR）——左旋

条件：节点 Z 的平衡因子为 2，且其右子 Y 的右子更高
操作：对 Z 执行一次 rotateLeft

情况二：右左（RL）——先右旋再左旋

条件：节点 Z 的平衡因子为 2，但其右子 Y 的左子更高
操作：
1. 对 Y 执行 rotateRight
2. 对 Z 执行 rotateLeft

情况三：左左（LL）——右旋

条件：节点 Z 的平衡因子为 -2，且其左子 Y 的左子更高
操作：对 Z 执行一次 rotateRight

情况四：左右（LR）——先左旋再右旋

条件：节点 Z 的平衡因子为 -2，但其左子 Y 的右子更高
操作：
1. 对 Y 执行 rotateLeft
2. 对 Z 执行 rotateRight

最终的 rebalance 方法整合了上述所有情况：

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

✅ 关键点：每次插入或删除后，必须从变更节点一路向上回溯到根，对路径上的每个节点调用 rebalance。

4. 插入节点

插入操作遵循 BST 基本规则：

从根开始，根据 key 大小决定向左或向右查找插入位置
找到合适位置后创建新节点
插入完成后，从下往上对路径上的每个节点执行 rebalance

Node insert(Node root, int key) {
    if (root == null) {
        return new Node(key);
    } else if (root.key > key) {
        root.left = insert(root.left, key);
    } else if (root.key < key) {
        root.right = insert(root.right, key);
    } else {
        throw new RuntimeException("duplicate Key!");
    }
    return rebalance(root);
}

⚠️ AVL 树中 key 必须唯一，重复插入会抛出异常。

由于树始终保持平衡，插入操作的时间复杂度为 **O(log N)**。

5. 删除节点

删除逻辑比插入稍复杂，需分情况处理：

✅ 叶子节点：直接删除
✅ 仅有一个子节点：用子节点替代
✅ 有两个子节点：找到右子树中的最小节点（最左节点）X，用 X 的值覆盖当前节点 Z，然后递归删除 X

删除后同样需要从下往上 rebalance。

Node delete(Node node, int key) {
    if (node == null) {
        return node;
    } else if (node.key > key) {
        node.left = delete(node.left, key);
    } else if (node.key < key) {
        node.right = delete(node.right, key);
    } else {
        if (node.left == null || node.right == null) {
            node = (node.left == null) ? node.right : node.left;
        } else {
            Node mostLeftChild = mostLeftChild(node.right);
            node.key = mostLeftChild.key;
            node.right = delete(node.right, node.key);
        }
    }
    if (node != null) {
        node = rebalance(node);
    }
    return node;
}

Node mostLeftChild(Node node) {
    return node.left == null ? node : mostLeftChild(node.left);
}

✅ 时间复杂度同样是 **O(log N)**，得益于平衡结构。

6. 查找节点

AVL 树的查找与普通 BST 完全一致，属于简单粗暴的二分查找：

从根开始比较
相等则返回，key 更大则向右，否则向左
直到找到或为空

Node find(int key) {
    Node current = root;
    while (current != null) {
        if (current.key == key) {
            break;
        }
        current = current.key < key ? current.right : current.left;
    }
    return current;
}

查找时间复杂度为 **O(log N)**，性能稳定，无最坏情况。

7. 总结

本文完整实现了 AVL 树的核心操作：插入、删除与查找。通过严格的平衡因子控制和四种旋转策略，AVL 树在动态数据场景下依然能保证高效的 O(log N) 操作性能。

✅ 适用场景：适合读多写少、对查询性能要求极高的系统。
⚠️ 注意：频繁插入删除可能引发较多旋转，需权衡维护成本。

完整代码示例可参考 GitHub 仓库：https://github.com/baeldung/java-algorithms/tree/master/avl-tree

Persistence

REST

Security