AVL樹C語言實現：單旋轉、雙旋轉與插入平衡調整完整代碼

AVL 核心不變量

任意節點左右子樹高度差 (平衡因子) ≤ 1。插入導致失衡時，通過旋轉恢復平衡，分四種情況：

• LL：左子樹的左側插入 → 右單旋轉。
• RR：右子樹的右側插入 → 左單旋轉。
• LR：左子樹的右側插入 → 先左後右雙旋轉。
• RL：右子樹的左側插入 → 先右後左雙旋轉。

數據結構

typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

struct AvlNode {
    int Element;
    AvlTree Left;
    AvlTree Right;
    int Height; // 節點高度：葉子為 0，空為 -1
};

輔助函數

int Max(int a, int b) { return a > b ? a : b; }

int HeightAvl(Position P) {
    return P ? P->Height : -1;
}

四種旋轉實現

1. 右單旋轉 (LL)

/*       K2                      K1
 *      /  \                    /  \
 *     K1   C    ====>         A    K2
 *    / \                         /  \
 *   A   B                       B    C
 */
Position SingleRotateWithLeft(Position K2) {
    Position K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;
    // 更新高度：先更新原根 K2 (現為右子)，再更新新根 K1
    K2->Height = Max(HeightAvl(K2->Left), HeightAvl(K2->Right)) + 1;
    K1->Height = Max(HeightAvl(K1->Left), HeightAvl(K1->Right)) + 1; // 此處原代碼用 K2->Right 為 K1 右子高度，正確
    return K1; // 新根
}

2. 左單旋轉 (RR)

Position SingleRotateWithRight(Position K2) {
    Position K1 = K2->Right;
    K2->Right = K1->Left;
    K1->Left = K2;
    K2->Height = Max(HeightAvl(K2->Left), HeightAvl(K2->Right)) + 1;
    K1->Height = Max(HeightAvl(K1->Left), HeightAvl(K1->Right)) + 1;
    return K1;
}

3. 雙旋轉 (LR = 先右旋左子再左旋根)

Position DoubleRotateWithLeft(Position K3) {
    // K3 為失衡節點，其左子 K3->Left 為 RL 型
    K3->Left = SingleRotateWithRight(K3->Left); // 先對左子做右旋 (變 LL)
    return SingleRotateWithLeft(K3);            // 再對 K3 做左旋
}

4. 雙旋轉 (RL = 先左旋右子再右旋根)

Position DoubleRotateWithRight(Position K3) {
    K3->Right = SingleRotateWithLeft(K3->Right); // 先對右子做左旋 (變 RR)
    return SingleRotateWithRight(K3);            // 再對 K3 做右旋
}

遞歸插入與平衡調整

AvlTree InsertAvl(int X, AvlTree T) {
    if (T == NULL) { // 創建新節點
        T = malloc(sizeof(struct AvlNode));
        T->Element = X; T->Height = 0;
        T->Left = T->Right = NULL;
    } else if (X < T->Element) {
        T->Left = InsertAvl(X, T->Left);
        // 檢查左側失衡 (高度差 == 2)
        if (HeightAvl(T->Left) - HeightAvl(T->Right) == 2) {
            if (X < T->Left->Element) // LL
                T = SingleRotateWithLeft(T);
            else                      // LR
                T = DoubleRotateWithLeft(T);
        }
    } else if (X > T->Element) {
        T->Right = InsertAvl(X, T->Right);
        if (HeightAvl(T->Right) - HeightAvl(T->Left) == 2) {
            if (X > T->Right->Element) // RR
                T = SingleRotateWithRight(T);
            else                       // RL
                T = DoubleRotateWithRight(T);
        }
    }
    // 相等值不插入 (集合語義)
    // 更新當前節點高度
    T->Height = Max(HeightAvl(T->Left), HeightAvl(T->Right)) + 1;
    return T;
}

原代碼問題修正

• malloc(sizeof(AvlTree)) → malloc(sizeof(struct AvlNode)) (分配節點大小而非指針大小)。
• 雙旋轉函數中原代碼 DoubleRotateWithRight 調用了錯誤的單旋轉方向，已修正。
• main 中 InsertAvl(1, Tree) 未初始化 Tree = NULL，已補充。

AVL 樹旋轉的關鍵在於正確識別失衡類型 (LL/LR/RL/RR) 並按順序更新高度 (先子後父)。遞歸插入天然支持回溯更新路徑上所有祖先高度。