平衡二叉樹（AVL）C 語言完整實現：插入、刪除、旋轉與高度維護

編輯：關於C語言

平衡二叉樹（AVL）C 語言完整實現：插入、刪除、旋轉與高度維護

AVL 樹通過旋轉操作維持左右子樹高度差 ≤ 1，保證查找 O(log n)。本文從旋轉原理、節點結構、輔助函數、插入刪除邏輯逐步構建完整可運行代碼，附頭文件與源文件。

四種旋轉操作

節點結構含 data、height、左右孩子指針。空節點高度定義為 -1，葉子高度 0。

LL 單右旋（左左）

BTNode* singleRotateLL(BTree* BT, BTNode* phead) {
    BTNode* temp = phead->lchild;
    if(temp->rchild) {
        phead->lchild = temp->rchild;
        phead->lchild->height = node_height(BT, phead->lchild);
    } else phead->lchild = NULL;
    temp->rchild = phead;
    if(temp->rchild->data == BT->phead->data) BT->phead = temp;
    phead = temp;
    // 更新高度：先子後父
    phead->rchild->height = node_height(BT, phead->rchild);
    phead->height = node_height(BT, phead);
    return phead;
}

RR 單左旋（右右）

鏡像對稱，處理 temp->lchild。

LR 雙旋（左右）

BTNode* doubleRotateLR(BTree* BT, BTNode* phead) {
    BTNode* temp = phead->lchild;
    phead->lchild = singleRotateRR(BT, temp); // 先對左孩子 RR
    temp = phead;
    phead = singleRotateLL(BT, temp);        // 再對當前節點 LL
    return phead;
}

RL 雙旋（右左）

鏡像：先對右孩子 LL，再對當前節點 RR。

輔助函數

int node_height(BTree* BT, BTNode* n) {
    if(!n) return -1;
    if(!n->lchild && !n->rchild) return 0;
    return max(node_height(BT, n->lchild), node_height(BT, n->rchild)) + 1;
}
void tree_height(BTree* BT, BTNode* n) { // 遍歷更新全樹高度
    if(!n) return;
    node_height(BT, n);
    if(n->lchild) tree_height(BT, n->lchild);
    if(n->rchild) tree_height(BT, n->rchild);
}
int max(int a, int b) { return a > b ? a : b; }

插入邏輯：遞歸插入 + 回溯平衡

BOOL tree_add(BTree* BT, BTNode* phead, TYPE value) {
    if(!phead || phead->data == value) return 0;
    if(value < phead->data) {
        if(!phead->lchild) { /* 創建節點 */ }
        else {
            tree_add(BT, phead->lchild, value);
            // 回溯檢查平衡
            BTNode* root = (phead == BT->phead) ? phead : phead->lchild;
            if(node_height(BT, root->lchild) - node_height(BT, root->rchild) == 2) {
                if(root->lchild->data > value) root = singleRotateLL(BT, root);
                else root = doubleRotateLR(BT, root);
            }
            phead = root; // 關鍵：更新父節點的孩子指針
        }
    } else { /* 右子樹對稱 */ }
    phead->height = node_height(BT, phead);
    return 1;
}

關鍵點：無父指針，需通過返回值或雙重指針更新父節點的孩子指針；根節點特殊處理。