平衡二叉树（AVL 树）的二叉树算法详解

平衡二叉树（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树失去平衡时，通过旋转操作来恢复平衡。主要的旋转操作有四种：

1. 右旋（Right Rotation）：

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

2. 左旋（Left Rotation）：

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

3. 左-右旋（Left-Right Rotation）：

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

4. 右-左旋（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树是一种强大的数据结构，能够在高效查找的同时，保持树的结构平衡，是许多应用中的重要组成部分。