AVL树与Java实现

什么是AVL树？

AVL树是一种自平衡二叉查找树。它是由Seymour Lipschutz和Yaakov Avlson于1962年提出的。AVL树的特点是每个节点的左右两个子树的高度差（平衡因子）最多为1，从而保证了其时间复杂度为O(log n)。

AVL树的基本操作

插入

在插入节点时，首先进行普通二叉查找树的操作，然后根据树的不平衡情况调整树形。AVL树的插入操作可以分为以下几步：

常规二叉查找树插入：将新节点按照普通的二叉查找树规则添加到相应位置。
检查平衡因子：从刚刚插入的新节点向上逐层检查每个节点，更新它们的平衡因子，并判断是否需要旋转来恢复AVL特性。

删除

在删除节点时，首先进行普通二叉查找树的操作，然后根据树的变化情况调整树形。AVL树的删除操作可以分为以下几步：

常规二叉查找树删除：找到要删除的节点并处理其替换节点（最小值或最大值）。
检查平衡因子：从被删除节点的位置向上逐层检查每个节点，更新它们的平衡因子，并判断是否需要旋转来恢复AVL特性。

AVL树的关键操作

旋转操作

AVL树使用旋转操作来调整其不平衡状态。主要有以下三种旋转方式：

左旋（Left Rotation）：当节点的右子树的高度大于左子树时，进行此操作。
右旋（Right Rotation）：当节点的左子树的高度大于右子树时，进行此操作。
左右旋（Left-Right Rotation）和右左旋（Right-Left Rotation）：这两种情况是由于两次旋转后才能恢复平衡。

平衡因子

每个节点包含一个平衡因子来记录其子树的高度差。平衡因子的可能值为-1、0或1，分别表示左重子树、左右子树相同高度和右重子树。

Java实现AVL树

下面是一个简单的Java实现示例：

class AVLNode {
    int key;
    int height;
    AVLNode left, right;

    public AVLNode(int item) {
        key = item;
        height = 1; // 新插入节点的高度为1
    }
}

public class AVLTree {

    AVLNode root;

    // 计算节点高度
    private int height(AVLNode N) {
        if (N == null)
            return 0;
        return N.height;
    }

    // 获取平衡因子
    private int getBalance(AVLNode N) {
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    // 右旋操作
    AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode 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;
    }

    // 左旋操作
    AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode 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;
    }

    AVLNode insert(AVLNode node, int key) {
        if (node == null)
            return new AVLNode(key);

        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else // Equal keys not allowed
            return node;

        // 更新高度
        node.height = 1 + Math.max(height(node.left), height(node.right));

        // 获取平衡因子
        int balance = getBalance(node);

        // 平衡检查
        if (balance > 1 && key < node.left.key) {
            return rightRotate(node);
        }

        if (balance < -1 && key > node.right.key) {
            return leftRotate(node);
        }

        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        // 如果未达到不平衡状态，则不需要调整
        return node;
    }
}

以上代码展示了AVL树的基本操作和Java实现。实际应用中，可以根据需要进一步完善和优化。