深入理解AVL树（Java语言实现自平衡二叉搜索树完整教程）

AVL树的核心概念

• 平衡因子（Balance Factor）：每个节点的左子树高度减去右子树高度，值只能是 -1、0 或 1。
• 旋转操作：当插入或删除导致不平衡时，通过旋转恢复平衡。包括左旋、右旋、左右旋、右左旋四种情况。

Java实现AVL树

下面我们用Java编写一个完整的AVL树类，包含节点定义、插入、旋转和高度计算等方法。

1. 定义AVL树节点

class AVLNode {    int key;    AVLNode left;    AVLNode right;    int height;    public AVLNode(int key) {        this.key = key;        this.height = 1; // 新节点初始高度为1    }}  

2. AVL树主类框架

public class AVLTree {    private AVLNode root;    // 获取节点高度    private int height(AVLNode node) {        if (node == null) return 0;        return node.height;    }    // 更新节点高度    private void updateHeight(AVLNode node) {        if (node != null) {            node.height = Math.max(height(node.left), height(node.right)) + 1;        }    }    // 计算平衡因子    private int getBalance(AVLNode node) {        if (node == null) return 0;        return height(node.left) - height(node.right);    }}  

3. 实现旋转操作

旋转是AVL树保持平衡的关键：

    // 右旋    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; // 新的根节点    }  

4. 插入操作

插入后检查平衡并进行必要的旋转：

    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 = getBalance(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 class Main {    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树构建完成！");    }}  

总结

通过本教程，你已经掌握了AVL树的基本原理和Java AVL树实现方法。这种自平衡二叉搜索树是许多高级数据结构（如红黑树）的基础，在数据库索引、内存管理等领域有广泛应用。

建议你动手实践上述代码，尝试添加删除操作，加深对这一重要数据结构教程内容的理解。祝你在学习数据结构的道路上越走越远！