數據結構：C語言實現 AVL 平衡二叉樹完整教學（插入、旋轉、平衡因子維護）

編輯：關於C語言

AVL 樹核心性質

任意節點左右子樹高度差（平衡因子 BF）∈ {-1, 0, 1}
插入/刪除後通過旋轉恢復平衡
查找/插入/刪除均保證 O(log n)

節點結構與平衡因子

typedef enum { EH = 0, LH = 1, RH = -1 } BalanceFactor;  // 平衡、左高、右高

typedef struct AVLNode {
    int key;
    BalanceFactor bf;
    struct AVLNode *left, *right;
} AVLNode, *AVLTree;

四種旋轉操作

1. 右旋 (RR 型失衡 → 右旋)

        A (LH)           B
       / \              / \
      B   C    →       D   A
     / \                  / \
    D   E                E   C

void R_Rotate(AVLTree *p) {
    AVLTree lc = (*p)->left;
    (*p)->left = lc->right;
    lc->right = *p;
    *p = lc;
}

2. 左旋 (LL 型失衡 → 左旋)

    A (RH)             B
   / \                / \
  C   B      →       A   E
     / \             / \
    D   E           C   D

void L_Rotate(AVLTree *p) {
    AVLTree rc = (*p)->right;
    (*p)->right = rc->left;
    rc->left = *p;
    *p = rc;
}

3. 左平衡 (LR 型：左子樹右高 → 先左旋左子樹，再右旋根)

void LeftBalance(AVLTree *T) {
    AVLTree lc = (*T)->left;
    AVLTree rd = lc->right;
    switch (lc->bf) {
        case LH:  // LL 型
            (*T)->bf = lc->bf = EH;
            R_Rotate(T);
            break;
        case RH:  // LR 型，需看 rd 的 bf
            switch (rd->bf) {
                case LH: (*T)->bf = RH; lc->bf = EH; break;
                case EH: (*T)->bf = lc->bf = EH; break;
                case RH: (*T)->bf = EH; lc->bf = LH; break;
            }
            rd->bf = EH;
            L_Rotate(&(*T)->left);  // 先左旋左子樹
            R_Rotate(T);            // 再右旋根
            break;
    }
}

4. 右平衡 (RL 型：右子樹左高 → 先右旋右子樹，再左旋根)

void RightBalance(AVLTree *T) {
    AVLTree rc = (*T)->right;
    AVLTree ld = rc->left;
    switch (rc->bf) {
        case RH:  // RR 型
            (*T)->bf = rc->bf = EH;
            L_Rotate(T);
            break;
        case LH:  // RL 型
            switch (ld->bf) {
                case RH: (*T)->bf = LH; rc->bf = EH; break;
                case EH: (*T)->bf = rc->bf = EH; break;
                case LH: (*T)->bf = EH; rc->bf = RH; break;
            }
            ld->bf = EH;
            R_Rotate(&(*T)->right);  // 先右旋右子樹
            L_Rotate(T);             // 再左旋根
            break;
    }
}

遞歸插入與平衡維護

typedef enum { FALSE = 0, TRUE = 1 } Bool;

Bool InsertAVL(AVLTree *T, int key, Bool *taller) {
    if (*T == NULL) {
        *T = malloc(sizeof(AVLNode));
        (*T)->key = key; (*T)->bf = EH;
        (*T)->left = (*T)->right = NULL;
        *taller = TRUE;
        return TRUE;
    }
    if (key == (*T)->key) { *taller = FALSE; return FALSE; }  // 重複不插入

    if (key < (*T)->key) {
        if (!InsertAVL(&(*T)->left, key, taller)) return FALSE;
        if (*taller) {
            switch ((*T)->bf) {
                case LH: LeftBalance(T); *taller = FALSE; break;
                case EH: (*T)->bf = LH; *taller = TRUE; break;
                case RH: (*T)->bf = EH; *taller = FALSE; break;
            }
        }
    } else {
        if (!InsertAVL(&(*T)->right, key, taller)) return FALSE;
        if (*taller) {
            switch ((*T)->bf) {
                case RH: RightBalance(T); *taller = FALSE; break;
                case EH: (*T)->bf = RH; *taller = TRUE; break;
                case LH: (*T)->bf = EH; *taller = FALSE; break;
            }
        }
    }
    return TRUE;
}

關鍵輔助函數

// 中序遍歷（驗證有序性）
void InOrder(AVLTree root) {
    if (root) {
        InOrder(root->left);
        printf("%d ", root->key);
        InOrder(root->right);
    }
}

// 前序遍歷（驗證樹形結構）
void PreOrder(AVLTree root) {
    if (root) {
        printf("%d ", root->key);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

// 查找
AVLTree SearchAVL(AVLTree root, int key) {
    while (root) {
        if (key == root->key) return root;
        root = (key < root->key) ? root->left : root->right;
    }
    return NULL;
}

// 遞歸銷毀
void DestroyAVL(AVLTree *root) {
    if (*root) {
        DestroyAVL(&(*root)->left);
        DestroyAVL(&(*root)->right);
        free(*root);
        *root = NULL;
    }
}

測試主程式

int main() {
    AVLTree root = NULL;
    Bool taller = FALSE;
    int data[] = {13, 24, 37, 90, 53};
    for (int i = 0; i < 5; i++) InsertAVL(&root, data[i], &taller);

    printf("中序: "); InOrder(root);  printf("\n");
    printf("前序: "); PreOrder(root); printf("\n");

    AVLTree found = SearchAVL(root, 37);
    printf("查找 37: %s\n", found ? "存在" : "不存在");

    DestroyAVL(&root);
    return 0;
}

運行結果

中序: 13 24 37 53 90
前序: 37 24 13 53 90

前序可見根節點 37，左右子樹高度平衡。

AVL 插入平衡調整決策表

| 失衡類型 | 失衡節點 BF | 子樹 BF | 調整操作 | |----------|-------------|---------|----------| | LL | LH | LH | 右旋 | | LR | LH | RH | 左旋左子樹 → 右旋 | | RR | RH | RH | 左旋 | | RL | RH | LH | 右旋右子樹 → 左旋 |

AVL vs 紅黑樹選型指南

| 維度 | AVL | 紅黑樹 | |------|-----|--------| | 查找性能 | 略優（更嚴格平衡） | 稍弱 | | 插入/刪除旋轉次數 | 較多（最多 O(log n)） | **最多 2 次旋轉** | | 實現複雜度 | 中等 | 較高 | | 典型應用 | 數據庫索引、只讀多場景 | **語言標準庫 (map/set)、內核** |

總結

AVL 樹通過平衡因子 + 四種旋轉 維持嚴格平衡，保證所有操作 O(log n)。本文給出了完整的節點定義、旋轉實現、左/右平衡調整、遞歸插入、遍歷查找、銷毀全套代碼。理解「插入 → 回溯更新 BF → 發現失衡 → 根據 BF 組合判斷旋轉類型 → 執行旋轉 → 更新 BF」這一核心流程，是掌握所有自平衡二叉搜索樹的基石。