您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C 語言實現 AVL 樹：單旋轉、雙旋轉與平衡插入算法詳解

編輯：關於C

前言

AVL 樹是最早發明的自平衡二叉搜索樹，通過維護節點平衡因子（左右子樹高度差）在 {-1,0,1} 範圍內，保證查找、插入、刪除均為 O(log n)。本文深入講解四種旋轉操作及插入再平衡邏輯，提供完整 C 代碼。

節點定義與高度維護

typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

struct AvlNode {
    int Element;
    AvlTree Left;
    AvlTree Right;
    int Height;  // 節點高度，葉子為 0，空為 -1
};

static int HeightAvl(Position P) {
    return (P == NULL) ? -1 : P->Height;
}

static int Max(int a, int b) { return (a > b) ? a : b; }

四種旋轉操作

旋轉本質是局部重構，在保持中序遍歷序列不變的前提下降低樹高。

1. 左單旋轉 (LL 型)

情況：節點 K2 的左子樹左側過高（插入在 K2->Left->Left）。

static Position SingleRotateWithLeft(Position K2) {
    Position K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    // 更新高度：先更新原根 K2，再更新新根 K1
    K2->Height = Max(HeightAvl(K2->Left), HeightAvl(K2->Right)) + 1;
    K1->Height = Max(HeightAvl(K1->Left), HeightAvl(K1->Right)) + 1; // 注意此處應為 K1->Right 即 K2
    return K1;  // 新根
}

2. 右單旋轉 (RR 型)

鏡像對稱，插入在 K2->Right->Right。

static Position SingleRotateWithRight(Position K2) {
    Position K1 = K2->Right;
    K2->Right = K1->Left;
    K1->Left = K2;

    K2->Height = Max(HeightAvl(K2->Left), HeightAvl(K2->Right)) + 1;
    K1->Height = Max(HeightAvl(K1->Left), HeightAvl(K1->Right)) + 1;
    return K1;
}

3. 左右雙旋轉 (LR 型)

情況：插入在 K3->Left->Right。先對左孩子右單旋，再對 K3 左單旋。

static Position DoubleRotateWithLeft(Position K3) {
    K3->Left = SingleRotateWithRight(K3->Left);  // 變為 LL 型
    return SingleRotateWithLeft(K3);
}

4. 右左雙旋轉 (RL 型)

鏡像對稱：插入在 K3->Right->Left。先對右孩子左單旋，再對 K3 右單旋。

static Position DoubleRotateWithRight(Position K3) {
    K3->Right = SingleRotateWithLeft(K3->Right);  // 變為 RR 型
    return SingleRotateWithRight(K3);
}

插入與再平衡

AvlTree InsertAvl(int X, AvlTree T) {
    if (T == NULL) {
        T = malloc(sizeof(struct AvlNode));
        if (T == NULL) { fprintf(stderr, "Out of space\\n"); exit(1); }
        T->Element = X; T->Height = 0; T->Left = T->Right = NULL;
    } else if (X < T->Element) {
        T->Left = InsertAvl(X, T->Left);
        // 檢查左側失衡
        if (HeightAvl(T->Left) - HeightAvl(T->Right) == 2) {
            if (X < T->Left->Element)  // LL
                T = SingleRotateWithLeft(T);
            else                       // LR
                T = DoubleRotateWithLeft(T);
        }
    } else if (X > T->Element) {
        T->Right = InsertAvl(X, T->Right);
        // 檢查右側失衡
        if (HeightAvl(T->Right) - HeightAvl(T->Left) == 2) {
            if (X > T->Right->Element) // RR
                T = SingleRotateWithRight(T);
            else                       // RL
                T = DoubleRotateWithRight(T);
        }
    }
    // 相等不插入
    T->Height = Max(HeightAvl(T->Left), HeightAvl(T->Right)) + 1;
    return T;
}

關鍵點解析

高度定義：空樹高度 -1，葉子 0。如此定義使平衡因子計算統一，旋轉後更新順序為「先更新原根，再更新新根」。
旋轉判斷邏輯：插入後回溯時，只需檢查插入路徑上的祖先節點。通過比較插入值 X 與失衡節點孩子的值，判斷是「外側插入」(LL/RR) 需單旋，還是「內側插入」(LR/RL) 需雙旋。
遞歸回溯：`InsertAvl` 返回新的子樹根指針，賦值給父節點的 Left/Right，實現指針重掛接。
雙旋轉分解：`DoubleRotateWithLeft` = `SingleRotateWithRight(K3->Left)` + `SingleRotateWithLeft(K3)`，代碼極其簡潔。

測試驗證

int main(void) {
    AvlTree Tree = NULL;
    int nums[] = {10, 20, 30, 40, 50, 25};  // 觸發 RR, LR 等旋轉
    for (int i = 0; i < 6; i++) Tree = InsertAvl(nums[i], Tree);
    // 中序遍歷應有序：10 20 25 30 40 50
    // 可添加打印函數驗證樹高平衡
    return 0;
}