AVL 樹刪除操作完整 C 實作（含四種旋轉平衡）

前言

延續《AVL 樹建構、插入、查詢、列印、銷毀》，本文攻克最複雜的刪除操作。刪除後需從被刪節點向上回溯，檢查祖先平衡因子（BF），執行 LL/LR/RR/RL 四種旋轉之一恢復平衡，直到根節點或高度不再變化。

刪除三種情況

1. 葉子節點：直接移除，父節點對應指標設 NULL，高度 -1 向上傳遞。
2. 僅有一子：以該子節點取代被刪節點，高度 -1 向上傳遞。
3. 雙子皆有：找左子樹最右節點（前驅）或右子樹最左節點（後繼），複製其鍵值，遞迴刪除該前驅/後繼（轉化為情況 1 或 2）。

平衡因子更新與旋轉判斷

• 定義 bool lower 記錄子樹高度是否降低。
• 刪除左子樹 → 調用 delete_left_balance；刪除右子樹 → delete_right_balance。
• 根據當前節點 BF 與較高子樹的 BF 決定旋轉類型（同插入但方向相反）。

核心程式碼架構

// 節點定義
typedef struct AVLNode {
    int key;
    int bf; // LH=-1, EH=0, RH=1
    struct AVLNode *left, *right, *parent;
} AVLNode;

// 外部介面
int avl_delete(AVLTree *tree, int key) {
    bool lower = false;
    if (!tree->root) return AVL_SUCCESS;
    return avl_search_and_delete(tree, tree->root, key, &lower);
}

// 遞迴搜尋並刪除
int avl_search_and_delete(AVLTree *t, AVLNode *n, int key, bool *lower) {
    if (key < n->key) {
        if (!n->left) return AVL_SUCCESS;
        avl_search_and_delete(t, n->left, key, lower);
        if (*lower) return avl_delete_left_balance(t, n, lower);
    } else if (key > n->key) {
        if (!n->right) return AVL_SUCCESS;
        avl_search_and_delete(t, n->right, key, lower);
        if (*lower) return avl_delete_right_balance(t, n, lower);
    } else { // 找到節點
        // 三種情況處理...
        // 刪除後 *lower = true 向上傳遞
    }
    return AVL_SUCCESS;
}

// 左子樹降高平衡
int avl_delete_left_balance(AVLTree *t, AVLNode *n, bool *lower) {
    switch (n->bf) {
        case LH: n->bf = EH; *lower = true; break;
        case EH: n->bf = RH; *lower = false; break;
        case RH: // 失衡，需旋轉
            // 根據 n->right->bf 判斷 RR 或 RL
            // 旋轉後更新 BF、設 *lower、替換父節點指標
            break;
    }
    return AVL_SUCCESS;
}

// 右子樹降高平衡（對稱）
int avl_delete_right_balance(AVLTree *t, AVLNode *n, bool *lower) { ... }

關鍵輔助函數

• avl_replace_child(tree, parent, old, new)：安全替換父節點的左/右指標，處理 parent==NULL（根節點）情況。
• avl_set_left/right(node, child)：設定子指標並更新 child->parent。
• avl_assert(node)：除錯用，驗證父子指標一致性，防止指標錯誤導致無限迴圈。

測試結果

隨機刪除多個節點後，樹結構仍保持 AVL 平衡性質（任意節點左右子樹高度差 ≤ 1）。

完整原始碼下載

完整 400+ 行實作（含建構、插入、刪除、列印、銷毀、驗證）可見原文連結，此處僅列核心邏輯。

常見錯誤避坑

• 忘記更新 parent 指標：旋轉、替換子節點時必須雙向維護。
• BF 更新順序錯：先旋轉結構、再根據旋轉類型重設 BF，否則後續回溯判斷錯誤。
• 雙子節點刪除未轉化：直接 free 被刪節點會破壞遞迴堆疊，必須複製前驅值、刪除前驅節點。
• 未處理根節點替換：parent==NULL 時需更新 tree->root。