AVL 樹平衡調整完整模板：四種旋轉操作與插入實作

AVL 模板完整實作，包含節點定義、高度維護、四種旋轉 (LL、RR、LR、RL) 及插入調整邏輯，可直接用於教學或工程參考。

資料結構定義

typedef struct AVLTreeNode *AVLTree;
typedef struct AVLTreeNode {
    int data;
    AVLTree left;
    AVLTree right;
    int height;
} AVLTreeNode;

int getHeight(AVLTree T) {
    return T ? T->height : -1;
}

四種旋轉操作

左單旋 (LL 型)

AVLTree singleLeftRotation(AVLTree A) {
    AVLTree B = A->left;
    A->left = B->right;
    B->right = A;
    
    A->height = max(getHeight(A->left), getHeight(A->right)) + 1;
    B->height = max(getHeight(B->left), A->height) + 1;
    return B;  // 新根節點
}

右單旋 (RR 型)

AVLTree singleRightRotation(AVLTree A) {
    AVLTree B = A->right;
    A->right = B->left;
    B->left = A;
    
    A->height = max(getHeight(A->left), getHeight(A->right)) + 1;
    B->height = max(getHeight(B->right), A->height) + 1;
    return B;
}

左右雙旋 (LR 型)

AVLTree doubleLeftRightRotation(AVLTree A) {
    A->left = singleRightRotation(A->left);  // 先對左子樹右旋
    return singleLeftRotation(A);             // 再對根左旋
}

右左雙旋 (RL 型)

AVLTree doubleRightLeftRotation(AVLTree A) {
    A->right = singleLeftRotation(A->right);  // 先對右子樹左旋
    return singleRightRotation(A);             // 再對根右旋
}

插入與自動平衡

AVLTree avlInsert(int X, AVLTree T) {
    if (!T) {  // 空樹：建立新節點
        T = (AVLTree)malloc(sizeof(struct AVLTreeNode));
        T->data = X;
        T->height = 0;
        T->left = T->right = NULL;
    }
    else if (X < T->data) {  // 插入左子樹
        T->left = avlInsert(X, T->left);
        if (getHeight(T->left) - getHeight(T->right) == 2) {
            if (X < T->left->data)  // LL
                T = singleLeftRotation(T);
            else                    // LR
                T = doubleLeftRightRotation(T);
        }
    }
    else if (X > T->data) {  // 插入右子樹
        T->right = avlInsert(X, T->right);
        if (getHeight(T->left) - getHeight(T->right) == -2) {
            if (X > T->right->data)  // RR
                T = singleRightRotation(T);
            else                     // RL
                T = doubleRightLeftRotation(T);
        }
    }
    // X == T->data：不重複插入
    
    T->height = max(getHeight(T->left), getHeight(T->right)) + 1;
    return T;
}

旋轉判斷邏輯表

關鍵實作細節

• 高度定義：空樹高度 -1，葉節點高度 0，便於平衡因子計算
• 旋轉後更新順序：先更新原根 (現子節點)，再更新新根
• 插入遞歸返回：每層遞歸返回調整後的子樹根，確保父節點連結正確
• 重複值處理：遇到相等值直接返回，不插入、不調整

擴展建議

• 新增刪除操作 (需處理更複雜的再平衡)
• 實作非遞歸版本避免棧溢出
• 加入迭代器支援範圍查詢
• 模板化支援任意可比較型別