您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

AVL 樹核心原理與 Java 實現：從平衡因子到四種旋轉

編輯：Java 綜合教學

AVL 樹：高度平衡的二叉搜尋樹

AVL 樹（Adelson-Velsky and Landis）是最早發明的自平衡二叉搜尋樹。其核心不變量：任意節點的左右子樹高度差（平衡因子）不超過 1。這保證了查找、插入、刪除的最壞時間複雜度均為 O(log n)。

節點結構定義

class AVLNode<T extends Comparable<T>> {
    T key;           // 關鍵字，用於排序
    AVLNode left;    // 左子樹
    AVLNode right;   // 右子樹
    int height;      // 節點高度
}

失衡四種情形與旋轉策略

插入節點後可能導致祖先節點失衡，按插入位置相對於失衡節點的方向分類：

類型	代號	描述	旋轉方案
左左	LL	插入於左子樹的左側	右單旋轉
右右	RR	插入於右子樹的右側	左單旋轉
左右	LR	插入於左子樹的右側	先左單旋轉（左子樹），再右單旋轉（失衡節點）
右左	RL	插入於右子樹的左側	先右單旋轉（右子樹），再左單旋轉（失衡節點）

單旋轉核心邏輯（以左單旋轉 LL 為例）

// k2 為失衡節點，k1 為其左孩子
public AVLNode<T> leftLeftRotation(AVLNode<T> k2) {
    AVLNode<T> k1 = k2.left;
    k2.left = k1.right;   // k1 的右子樹掛到 k2 左側
    k1.right = k2;        // k2 成為 k1 右孩子
    // 更新高度
    k2.height = maxHeight(height(k2.left), height(k2.right)) + 1;
    k1.height = maxHeight(height(k1.left), k1.right) + 1;
    return k1;            // k1 成為新根
}

右單旋轉（RR）為鏡像操作。雙旋轉（LR/RL）則組合兩次單旋轉。

高度維護關鍵

節點高度 = max(左子樹高度, 右子樹高度) + 1。空節點高度定義為 0。每次旋轉後必須由底向上更新受影響節點高度。

完整測試類骨架

public class AVLTree<T extends Comparable<T>> {
    private AVLNode<T> mRoot;
    // 內部類 AVLNode、height()、maxHeight()、四種旋轉方法
    // 插入、刪除邏輯中調用旋轉修正平衡
}

提示：實際工程中推薦使用成熟庫（如 Java 集合框架的 TreeMap 內部即為紅黑樹），但理解 AVL 旋轉機制對掌握平衡樹原理至關重要。