Java平衡二叉树详解（手把手教你实现AVL自平衡二叉搜索树）

AVL 树的核心概念

• 平衡因子（Balance Factor）：某个节点的左子树高度减去右子树高度，取值为 -1、0 或 1。
• 旋转操作：当插入或删除破坏平衡时，通过以下四种旋转之一恢复平衡：
• 右旋（Right Rotation）
• 左旋（Left Rotation）
• 左右旋（Left-Right Rotation）
• 右左旋（Right-Left Rotation）

Java 实现 AVL 树

下面我们用 Java 编写一个简单的 AVL 树类，包含节点定义、插入、旋转和高度计算等核心功能。

// AVL 树节点类class AVLNode {    int key;    AVLNode left, right;    int height;    AVLNode(int key) {        this.key = key;        this.height = 1; // 新节点初始高度为1    }}// AVL 树主类public class AVLTree {    private AVLNode root;    // 获取节点高度    private int height(AVLNode node) {        return (node == null) ? 0 : node.height;    }    // 更新节点高度    private void updateHeight(AVLNode node) {        if (node != null) {            node.height = Math.max(height(node.left), height(node.right)) + 1;        }    }    // 获取平衡因子    private int getBalanceFactor(AVLNode node) {        return (node == null) ? 0 : height(node.left) - height(node.right);    }    // 右旋    private AVLNode rotateRight(AVLNode y) {        AVLNode x = y.left;        AVLNode T2 = x.right;        x.right = y;        y.left = T2;        updateHeight(y);        updateHeight(x);        return x;    }    // 左旋    private AVLNode rotateLeft(AVLNode x) {        AVLNode y = x.right;        AVLNode T2 = y.left;        y.left = x;        x.right = T2;        updateHeight(x);        updateHeight(y);        return y;    }    // 插入节点    public void insert(int key) {        root = insertRec(root, key);    }    private AVLNode insertRec(AVLNode node, int key) {        // 1. 执行标准 BST 插入        if (node == null) {            return new AVLNode(key);        }        if (key < node.key) {            node.left = insertRec(node.left, key);        } else if (key > node.key) {            node.right = insertRec(node.right, key);        } else {            // 不允许重复键            return node;        }        // 2. 更新当前节点高度        updateHeight(node);        // 3. 获取平衡因子        int balance = getBalanceFactor(node);        // 4. 如果失衡，进行旋转        // Left Left Case        if (balance > 1 && key < node.left.key) {            return rotateRight(node);        }        // Right Right Case        if (balance < -1 && key > node.right.key) {            return rotateLeft(node);        }        // Left Right Case        if (balance > 1 && key > node.left.key) {            node.left = rotateLeft(node.left);            return rotateRight(node);        }        // Right Left Case        if (balance < -1 && key < node.right.key) {            node.right = rotateRight(node.right);            return rotateLeft(node);        }        return node;    }    // 中序遍历（用于测试）    public void inorder() {        inorderRec(root);        System.out.println();    }    private void inorderRec(AVLNode node) {        if (node != null) {            inorderRec(node.left);            System.out.print(node.key + " ");            inorderRec(node.right);        }    }    // 测试示例    public static void main(String[] args) {        AVLTree tree = new AVLTree();        tree.insert(10);        tree.insert(20);        tree.insert(30);        tree.insert(40);        tree.insert(50);        tree.insert(25);        System.out.println("AVL 树中序遍历结果：");        tree.inorder(); // 输出应为有序序列    }}

为什么选择 AVL 树？

在Java平衡二叉树的应用场景中，AVL 树特别适合读多写少的环境，因为它的严格平衡特性确保了最坏情况下的高效查询性能。虽然红黑树在频繁插入/删除时可能更优，但 AVL 树结构更“紧凑”，内存局部性更好。

总结

通过本篇Java数据结构教程，你应该已经掌握了 AVL树实现 的基本原理和代码编写方法。记住，平衡二叉树的关键在于“插入后检查平衡，失衡则旋转”。建议你动手运行上述代码，并尝试添加删除功能，以加深理解。

掌握自平衡二叉搜索树不仅能提升你的算法能力，还能在面试和实际项目中大显身手。继续练习吧，数据结构的世界远比你想象的精彩！