數據結構課程設計：平衡二叉樹（AVL）完整實現與核心操作詳解

專題需求

基於平衡二叉樹（AVL Tree）實現動態查找表，包含三大核心功能：

1. 基本操作：查找、插入、刪除
2. 合併兩棵 AVL 樹
3. 按關鍵字 X 分裂：一棵所有鍵 ≤ X，另一棵所有鍵 > X

設計總結

開發環境

• 語言：C/C++
• IDE：Visual C++ 6.0（經典教學環境）
• 介面：控制台（DOS 視窗）

核心數據結構

typedef struct AVLNode {
    KeyType key;           // 關鍵字
    InfoType data;         // 附加數據
    int bf;                // 平衡因子：-1, 0, +1
    struct AVLNode *lchild, *rchild;
} AVLNode, *AVLTree;

四種旋轉操作（平衡調整核心）

插入算法遞歸實現

// 返回值：是否導致樹高增加
bool InsertAVL(AVLTree *T, KeyType key, InfoType data, bool *taller) {
    if (*T == NULL) {
        *T = (AVLTree)malloc(sizeof(AVLNode));
        (*T)->key = key; (*T)->data = data; (*T)->bf = 0;
        (*T)->lchild = (*T)->rchild = NULL;
        *taller = true;
        return true;
    }
    if (key == (*T)->key) return false;  // 已存在
    
    if (key < (*T)->key) {
        if (!InsertAVL(&(*T)->lchild, key, data, taller)) return false;
        if (*taller) {
            switch ((*T)->bf) {
                case 1: LeftBalance(T); *taller = false; break;
                case 0: (*T)->bf = 1; *taller = true; break;
                case -1: (*T)->bf = 0; *taller = false; break;
            }
        }
    } else {  // key > (*T)->key
        if (!InsertAVL(&(*T)->rchild, key, data, taller)) return false;
        if (*taller) {
            switch ((*T)->bf) {
                case -1: RightBalance(T); *taller = false; break;
                case 0: (*T)->bf = -1; *taller = true; break;
                case 1: (*T)->bf = 0; *taller = false; break;
            }
        }
    }
    return true;
}

刪除算法難點

• 刪除節點後需回溯更新平衡因子，可能引發多次旋轉。
• 採用「刪除後調整」策略：找到替代節點（前驅/後繼），複製數據，轉為刪除替代節點（度 ≤ 1），再向上調整。
• 調整邏輯與插入對稱，但需處理「刪除導致子樹降高」的傳播。

合併兩棵 AVL 樹

思路：中序遍歷較小樹，逐個插入較大樹。時間複雜度 O(m log n)（m ≤ n）。優化：將兩樹轉為有序數組，歸併後重建平衡樹，複雜度 O(m+n)。

按鍵值分裂 AVL 樹

遞歸分裂函數 SplitAVL(T, key, *T1, *T2)：

void SplitAVL(AVLTree T, KeyType key, AVLTree *T1, AVLTree *T2) {
    if (T == NULL) { *T1 = *T2 = NULL; return; }
    if (T->key <= key) {
        SplitAVL(T->rchild, key, &T->rchild, T2);
        *T1 = T;
        // 此處需更新 T1 平衡因子，可能需旋轉
    } else {
        SplitAVL(T->lchild, key, T1, &T->lchild);
        *T2 = T;
        // 同理更新 T2
    }
}

難點在於分裂過程中保持兩棵結果樹的平衡性，通常需引入輔助函數在回溯時重新平衡。

心得與避坑指南

1. 平衡因子更新時機：僅在子樹高度真正變化時傳播，taller/shorter 標誌位至關重要。
2. 旋轉後平衡因子重設：LL/RR 旋轉後雙方 bf 歸零；LR/RL 需根據原中間節點 bf 設置三節點新 bf。
3. 調試技巧：實現 InOrderTraverse 驗證有序性，CheckBalance 遞歸校驗所有節點 |bf| ≤ 1。
4. 內存管理：課設未實現銷毀函數，生產代碼必須提供 DestroyAVL 遞歸釋放所有節點。

擴展思考

• 對比紅黑樹：AVL 查找更快（更嚴格平衡），插入刪除旋轉更多；工程多用紅黑樹（STL map、Linux kernel rbtree）。
• 持久化存儲：將 AVL 節點序列化到文件/數據庫，支援斷點續傳。
• 併發版本：引入讀寫鎖或無鎖結構（如 RCU），實現線程安全 AVL。