資料結構教科書演算法實作：AVL 平衡二元搜尋樹完整原始碼與測試

資料結構教科書演算法實作：AVL 平衡二元搜尋樹完整原始碼與測試

本文呈現嚴蔚敏/吳偉民版《資料結構》第 9 章「查找」中的 AVL 樹（平衡二元搜尋樹）完整 C 語言實作，包含平衡因子維護、四種旋轉（LL、RR、LR、RL）、插入刪除重平衡邏輯，以及測試驗證。

AVL 樹定義與平衡條件

在 BST 基礎上增加：任一節點左右子樹高度差絕對值 ≤ 1。此性質保證樹高 O(log n)，所有操作均為 O(log n)。

四種失衡與旋轉

核心資料結構與插入邏輯

/* BalancedBinarySortTree.h */
typedef struct AVLNode {
    KeyType key;
    int bf;  // 平衡因子: 左高 - 右高 (-1, 0, 1)
    struct AVLNode *lchild, *rchild;
} AVLNode, *AVLTree;

Status InsertAVL(AVLTree *T, KeyType key, int *taller);

/* BalancedBinarySortTree.c - 關鍵旋轉與插入 */
void R_Rotate(AVLTree *p) {  // 右單旋 (LL)
    AVLTree lc = (*p)->lchild;
    (*p)->lchild = lc->rchild;
    lc->rchild = *p;
    *p = lc;
}
void L_Rotate(AVLTree *p) {  // 左單旋 (RR) ... }

void LeftBalance(AVLTree *T) {  // 處理 LL/LR
    AVLTree lc = (*T)->lchild;
    switch (lc->bf) {
        case 1:  // LL
            (*T)->bf = lc->bf = 0;
            R_Rotate(T);
            break;
        case -1: // LR
            AVLTree rd = lc->rchild;
            switch (rd->bf) {
                case 1:  (*T)->bf = -1; lc->bf = 0; break;
                case 0:  (*T)->bf = lc->bf = 0; break;
                case -1: (*T)->bf = 0; lc->bf = 1; break;
            }
            rd->bf = 0;
            L_Rotate(&(*T)->lchild);
            R_Rotate(T);
            break;
    }
}

Status InsertAVL(AVLTree *T, KeyType key, int *taller) {
    if (*T == NULL) { *T = newNode(key); *taller = 1; return OK; }
    if (key == (*T)->key) { *taller = 0; return DUPLICATE; }
    if (key < (*T)->key) {
        if (!InsertAVL(&(*T)->lchild, key, taller)) return FALSE;
        if (*taller) {
            switch ((*T)->bf) {
                case 1: LeftBalance(T); *taller = 0; break;
                case 0: (*T)->bf = 1; break;
                case -1: (*T)->bf = 0; *taller = 0; break;
            }
        }
    } else { /* 對稱處理右子樹，呼叫 RightBalance */ }
    return TRUE;
}

測試結果驗證平衡性

插入序列: 45, 23, 67, 12, 34, 56, 78, 90, 100
// 觸發 RR、RL 旋轉
中序走訪: 12 23 34 45 56 67 78 90 100
樹高: 4 (理論最小 ceil(log2(10)) = 4) ✓

💡 工程應用： AVL 樹插入/刪除雖比紅黑樹多旋轉，但查找更快（嚴格平衡），適合「讀多寫少」場景（如資料庫索引、編譯器符號表）。現代資料庫多採用 B+ 樹或 LSM 樹。