Java數據結構之AVL樹實例分析

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樹在需要頻繁插入和刪除操作的場景中具有重要的應用價值。