转载声明：文章来源https://blog.csdn.net/m0_61840987/article/details/143051262

平衡二叉树（AVL Tree）是一种自平衡的二叉搜索树（Binary Search Tree, BST），其特点是通过维护树的高度平衡来保证基本操作（插入、删除和查找）的时间复杂度为 O(log⁡n)。AVL树是由G.M. Adelson-Velsky和E.M. Landis于1962年提出的，因此得名“AVL树”。
1. AVL树的定义
AVL树的每个节点都有一个平衡因子（Balance Factor），其值为该节点的左子树高度减去右子树高度。对于任何一个节点，平衡因子的值只能为 −1、0 或 1，表示树的高度是平衡的。如果一个节点的平衡因子为 −1，表示右子树比左子树高；如果平衡因子为 1，表示左子树比右子树高；如果平衡因子为 0，表示左右子树高度相等。
2. AVL树的特性
性质：对于每个节点，左子树和右子树的高度差（平衡因子）最多为1。
高度平衡：由于AVL树保持高度平衡，查找、插入和删除的时间复杂度都是 O(log⁡n)
自平衡：在插入或删除节点后，AVL树会通过旋转操作来恢复平衡。
3. AVL树的旋转
当AVL树失去平衡时，通过旋转操作来恢复平衡。主要的旋转操作有四种：
右旋（Right Rotation）：
当某个节点的左子树比右子树高时，进行右旋转，以恢复平衡。
适用于插入在左子树的左侧（LL型）。

左旋（Left Rotation）：
当某个节点的右子树比左子树高时，进行左旋转，以恢复平衡。
适用于插入在右子树的右侧（RR型）。

左-右旋（Left-Right Rotation）：
当某个节点的左子树比右子树高，且插入在左子树的右侧时，先进行左旋再进行右旋，以恢复平衡（LR型）。
右-左旋（Right-Left Rotation）：
当某个节点的右子树比左子树高，且插入在右子树的左侧时，先进行右旋再进行左旋，以恢复平衡（RL型）。

4. AVL树的插入操作
插入操作分为以下步骤：
1.普通的二叉搜索树插入：按照二叉搜索树的性质插入新节点。
2.更新平衡因子：从插入位置向上更新每个节点的高度和平衡因子。
3.检查平衡：如果某个节点的平衡因子变为 −2 或 2，则需要进行旋转操作。
4.旋转恢复平衡：根据失衡的情况，选择适当的旋转操作来恢复平衡。
AVL树的Java实现
以下是AVL树的Java实现示例，包括插入和旋转操作：

class AVLTreeNode {
    int key;
    int height;
    AVLTreeNode left, right;
 
    public AVLTreeNode(int key) {
        this.key = key;
        this.height = 1;
    }
}
 
class AVLTree {
    private AVLTreeNode root;
 
    // 获取节点高度
    private int height(AVLTreeNode node) {
        return node == null ? 0 : node.height;
    }
 
    // 获取平衡因子
    private int getBalance(AVLTreeNode node) {
        return node == null ? 0 : height(node.left) - height(node.right);
    }
 
    // 右旋
    private AVLTreeNode rightRotate(AVLTreeNode y) {
        AVLTreeNode x = y.left;
        AVLTreeNode T2 = x.right;
 
        // 进行旋转
        x.right = y;
        y.left = T2;
 
        // 更新高度
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;
 
        return x; // 新的根节点
    }
 
    // 左旋
    private AVLTreeNode leftRotate(AVLTreeNode x) {
        AVLTreeNode y = x.right;
        AVLTreeNode T2 = y.left;
 
        // 进行旋转
        y.left = x;
        x.right = T2;
 
        // 更新高度
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;
 
        return y; // 新的根节点
    }
 
    // 插入节点
    public AVLTreeNode insert(AVLTreeNode node, int key) {
        // 1. 执行普通的BST插入
        if (node == null) {
            return new AVLTreeNode(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;
        }
 
        // 2. 更新当前节点的高度
        node.height = Math.max(height(node.left), height(node.right)) + 1;
 
        // 3. 获取平衡因子
        int balance = getBalance(node);
 
        // 4. 如果节点失衡，则进行旋转操作
        // LL型
        if (balance > 1 && key < node.left.key) {
            return rightRotate(node);
        }
        // RR型
        if (balance < -1 && key > node.right.key) {
            return leftRotate(node);
        }
        // LR型
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        // RL型
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
 
        return node; // 返回未变化的节点指针
    }
 
    // 中序遍历
    public void inorder(AVLTreeNode node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.key + " ");
            inorder(node.right);
        }
    }
 
    public void display() {
        inorder(root);
        System.out.println();
    }
 
    public void insert(int key) {
        root = insert(root, key);
    }
 
    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        int[] keys = {10, 20, 30, 40, 50, 25};
 
        for (int key : keys) {
            avlTree.insert(key);
        }
 
        System.out.println("中序遍历 AVL 树：");
        avlTree.display(); // 输出: 10 20 25 30 40 50
    }
}

代码解读
1.AVLTreeNode类：定义AVL树的节点，包含键值、节点高度和左右子节点指针。
2.AVLTree类：包含根节点和插入、旋转、获取高度及平衡因子的相关方法。
3.插入操作：
在插入方法中，先执行标准的二叉搜索树插入。
更新节点的高度，并计算平衡因子。
根据平衡因子的值判断是否需要旋转，以恢复平衡。
4.旋转操作：
右旋和左旋方法用于在AVL树失衡时，进行旋转操作以恢复平衡。
5.中序遍历：
中序遍历方法用于展示AVL树的节点，确保输出的顺序是升序的。

5. AVL树的优缺点
优点
自平衡：保持高度平衡，保证 O(log⁡n) 的时间复杂度。
高效查找：由于是二叉搜索树，查找操作高效。
缺点
插入和删除复杂：相较于普通二叉搜索树，AVL树的插入和删除操作复杂，需要进行旋转。
空间复杂度：相对其他树结构（如红黑树），AVL树的空间复杂度可能更高，因为需要存储每个节点的高度信息。

6. 应用场景
AVL树常用于需要频繁进行插入和删除操作的场景，如数据库索引、内存管理等。
由于其高度平衡的特性，适合对查询性能有严格要求的应用。
AVL树是一种强大的数据结构，能够在高效查找的同时，保持树的结构平衡，是许多应用中的重要组成部分。