AVL 樹 C 語言完整實現：非遞歸插入刪除與平衡調整

資料結構定義

typedef enum { EH = 0, LH = 1, RH = -1 } BalanceFactor;
typedef enum { FALSE = 0, TRUE = 1 } Bool;
typedef int ElemType;

typedef struct BSTNode {
    ElemType key;
    int bf;                    // 平衡因子
    struct BSTNode *lchild, *rchild, *parent;
} BSTNode, *BSTree;

引入 parent 指標，支援非遞歸回溯調整。

核心操作

查找 searchAVL

非遞歸下降，返回是否找到及父節點位置。

輔助：最小/最大/前驅/後繼節點

BSTNode* minNode(BSTNode* root) { while (root->lchild) root = root->lchild; return root; }
BSTNode* maxNode(BSTNode* root) { while (root->rchild) root = root->rchild; return root; }
BSTNode* preNode(BSTNode* t) {  // 中序前驅
    if (t->lchild) return maxNode(t->lchild);
    while (t->parent && t != t->parent->rchild) t = t->parent;
    return t->parent;
}
BSTNode* nextNode(BSTNode* t) {  // 中序後繼
    if (t->rchild) return minNode(t->rchild);
    while (t->parent && t != t->parent->lchild) t = t->parent;
    return t->parent;
}

左平衡旋轉 leftbalance

處理 LL / LR 兩種情況，更新 bf、parent、祖先指向，返回新子樹根。

右平衡旋轉 rightbalance

對稱處理 RR / RL。

插入 insertNode

1. 查找插入位置，建立新節點 bf=EH。
2. 回溯祖先更新 bf：
   - 子樹變高導致祖先 bf 從 EH→LH/RH 繼續向上。
   - 祖先 bf 從 LH/RH→EH 停止回溯。
   - 祖先 bf 從 LH→LH 或 RH→RH 觸發旋轉，調整後結束。

刪除 deleteNode

1. 查找目標節點，若有兩個孩子，用前驅/後繼值替換，轉為刪除葉子或單孩子節點。
2. 實際刪除節點後，回溯祖先更新 bf：
   - 子樹變矮導致祖先 bf 從 LH/RH→EH 繼續向上。
   - 祖先 bf 從 EH→LH/RH 停止。
   - 祖先 bf 從 LH→RH 或 RH→LH 觸發旋轉，調整後結束。
3. 釋放節點記憶體，處理根節點刪除特殊情況。

測試主程式

int data[] = {1,5,7,4,3,2,11,9,10,100};
BSTNode* root = createAVL(data, 10);
InOrderTraverse(root);  // 中序輸出有序
PreOrderTraverse(root); // 先序輸出樹結構

root = deleteNode(5, root);  // 連續刪除驗證平衡維護
root = deleteNode(3, root);
root = deleteNode(1, root);
root = deleteNode(7, root);
root = deleteNode(4, root);
root = deleteNode(2, root);
destroyAVL(root);

關鍵設計亮點

• 非遞歸：避免深度遞歸棧溢出，效率更高。
• 父指標：使回溯與旋轉時祖先重連接變得簡單直接。
• 統一平衡因子更新邏輯：插入/刪除分別對應「變高/變矮」觸發條件，代碼清晰。
• 完整記憶體管理：createAVL/destroyAVL 成對使用，無洩漏。

複雜度

查找、插入、刪除均為 O(log n)，嚴格平衡保證最壞情況性能。