Java数据结构之AVL树实例分析

1. AVL树简介

AVL树是一种自平衡的二叉搜索树（BST），由Adelson-Velsky和Landis在1962年提出。AVL树通过维护每个节点的平衡因子（即左子树高度与右子树高度的差值）来确保树的高度始终保持在O(log n)范围内，从而保证查找、插入和删除操作的时间复杂度为O(log n)。

2. AVL树的基本性质

• 平衡因子：每个节点的平衡因子定义为左子树高度减去右子树高度。平衡因子的绝对值不超过1。
• 旋转操作：当插入或删除节点导致树失去平衡时，AVL树通过旋转操作来恢复平衡。常见的旋转操作包括左旋、右旋、左右旋和右左旋。

3. AVL树的Java实现

3.1 节点类定义

首先，我们定义一个表示AVL树节点的类AVLNode：

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

    AVLNode(int key) {
        this.key = key;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
}

3.2 平衡因子计算

为了计算节点的平衡因子，我们需要一个辅助方法来获取节点的高度：

int height(AVLNode node) {
    if (node == null) {
        return 0;
    }
    return node.height;
}

int getBalance(AVLNode node) {
    if (node == null) {
        return 0;
    }
    return height(node.left) - height(node.right);
}

3.3 旋转操作

AVL树的旋转操作包括左旋和右旋：

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;
}

3.4 插入操作

插入操作首先按照二叉搜索树的规则插入节点，然后更新节点的高度并检查平衡因子。如果树失去平衡，则进行相应的旋转操作：

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 {
        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;
}

3.5 删除操作

删除操作与插入操作类似，首先按照二叉搜索树的规则删除节点，然后更新节点的高度并检查平衡因子。如果树失去平衡，则进行相应的旋转操作：

AVLNode deleteNode(AVLNode root, int key) {
    if (root == null) {
        return root;
    }

    if (key < root.key) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.key) {
        root.right = deleteNode(root.right, key);
    } else {
        if ((root.left == null) || (root.right == null)) {
            AVLNode temp = null;
            if (temp == root.left) {
                temp = root.right;
            } else {
                temp = root.left;
            }

            if (temp == null) {
                temp = root;
                root = null;
            } else {
                root = temp;
            }
        } else {
            AVLNode temp = minValueNode(root.right);
            root.key = temp.key;
            root.right = deleteNode(root.right, temp.key);
        }
    }

    if (root == null) {
        return root;
    }

    root.height = Math.max(height(root.left), height(root.right)) + 1;

    int balance = getBalance(root);

    // 左左情况
    if (balance > 1 && getBalance(root.left) >= 0) {
        return rightRotate(root);
    }

    // 左右情况
    if (balance > 1 && getBalance(root.left) < 0) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }

    // 右右情况
    if (balance < -1 && getBalance(root.right) <= 0) {
        return leftRotate(root);
    }

    // 右左情况
    if (balance < -1 && getBalance(root.right) > 0) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }

    return root;
}

AVLNode minValueNode(AVLNode node) {
    AVLNode current = node;
    while (current.left != null) {
        current = current.left;
    }
    return current;
}

4. 实例分析

假设我们有一个空的AVL树，依次插入以下键值：10, 20, 30, 40, 50, 25。插入过程如下：

1. 插入10：树平衡。
2. 插入20：树平衡。
3. 插入30：树失去平衡，进行左旋。
4. 插入40：树平衡。
5. 插入50：树失去平衡，进行左旋。
6. 插入25：树失去平衡，进行左右旋。

最终，AVL树的结构如下：

      30
     /  \
   20   40
  /  \    \
10   25   50

5. 总结

AVL树通过维护每个节点的平衡因子来确保树的高度始终保持在O(log n)范围内，从而保证了查找、插入和删除操作的高效性。通过旋转操作，AVL树能够在插入或删除节点后迅速恢复平衡。本文通过Java代码实现了AVL树的基本操作，并通过实例分析了插入过程。AVL树在需要频繁插入和删除操作的场景中具有重要的应用价值。