「Chaos 算法」系列之 AVL 樹（平衡二叉樹）完整 C++ 實現與圖解

編輯：關於C語言

前言

AVL 樹是最早的自平衡二叉搜索樹，1962 年由 Adelson-Velsky 和 Landis 發明。它強制要求任意節點左右子樹高度差 ≤ 1，通過旋轉操作維持平衡，保證查找、插入、刪除最壞情況均為 O(log N)。本文參考《數據結構與算法分析——C 語言描述》，提供完整 C++ 模板實現並逐步圖解旋轉邏輯。

核心數據結構

template <class T>
class TreeNode {
public:
    T data;                 // 關鍵字
    int hgt;                // 以此節點為根的子樹高度（空樹 -1，單節點 0）
    unsigned int freq;      // 重複鍵計數
    TreeNode *lson, *rson;  // 左右孩子
    TreeNode() : lson(nullptr), rson(nullptr), freq(1), hgt(0) {}
};

AVL 樹類聲明

template <class T>
class AVLTree {
private:
    TreeNode<T> *root;
    // 內部遞歸接口
    void insertpri(TreeNode<T>* &, T);
    TreeNode<T>* findpri(TreeNode<T>*, T);
    void Deletepri(TreeNode<T>* &, T);
    void insubtree(TreeNode<T>*); // 中序遍歷

    // 平衡維護
    int height(TreeNode<T>*);
    int Max(int, int);
    void SingRotateLeft(TreeNode<T>* &);   // LL
    void SingRotateRight(TreeNode<T>* &);  // RR
    void DoubleRotateLR(TreeNode<T>* &);   // LR
    void DoubleRotateRL(TreeNode<T>* &);   // RL

public:
    AVLTree() : root(nullptr) {}
    void insert(T) { insertpri(root, x); }
    TreeNode<T>* find(T) { return findpri(root, x); }
    void Delete(T) { Deletepri(root, x); }
    void traversal() { insubtree(root); }
};

輔助函數

// 獲取節點高度，空指針返回 -1
template <class T>
int AVLTree<T>::height(TreeNode<T>* node) {
    return node ? node->hgt : -1;
}
template <class T>
int AVLTree<T>::Max(int a, int b) { return a > b ? a : b; }

四種失衡情況與旋轉圖解

四種失衡情況

LL：左孩子的左子樹較高 → 右單旋轉
LR：左孩子的右子樹較高 → 先左旋轉左孩子，再右旋轉當前節點（雙旋轉）
RL：右孩子的左子樹較高 → 先右旋轉右孩子，再左旋轉當前節點（雙旋轉）
RR：右孩子的右子樹較高 → 左單旋轉

單旋轉實現（LL / RR）

// LL：k2 失衡，k1 為左孩子
template <class T>
void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2) {
    TreeNode<T>* k1 = k2->lson;
    k2->lson = k1->rson;
    k1->rson = k2;
    k2->hgt = Max(height(k2->lson), height(k2->rson)) + 1;
    k1->hgt = Max(height(k1->lson), k2->hgt) + 1;
    k2 = k1; // 更新父節點指向新根
}

// RR：鏡像操作
template <class T>
void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2) {
    TreeNode<T>* k1 = k2->rson;
    k2->rson = k1->lson;
    k1->lson = k2;
    k2->hgt = Max(height(k2->lson), height(k2->rson)) + 1;
    k1->hgt = Max(height(k1->rson), k2->hgt) + 1;
    k2 = k1;
}

雙旋轉實現（LR / RL）

template <class T>
void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3) {
    SingRotateRight(k3->lson); // 先將 LR 轉為 LL
    SingRotateLeft(k3);
}
template <class T>
void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3) {
    SingRotateLeft(k3->rson);  // 先將 RL 轉為 RR
    SingRotateRight(k3);
}

插入、刪除與查找

插入遞歸下行，回溯時檢查平衡因子並旋轉；刪除分三種情況（無孩子、單孩子、雙孩子），雙孩子採用「右子樹最小節點替換」法，回溯同樣維護平衡。查找同普通 BST，但高度穩定保證 O(log N)。

// 插入核心邏輯片段
if (node->data > x) {
    insertpri(node->lson, x);
    if (2 == height(node->lson) - height(node->rson)) {
        if (x < node->lson->data) SingRotateLeft(node);
        else DoubleRotateLR(node);
    }
} else if (node->data < x) {
    insertpri(node->rson, x);
    if (2 == height(node->rson) - height(node->lson)) {
        if (x > node->rson->data) SingRotateRight(node);
        else DoubleRotateRL(node);
    }
} else ++node->freq;
node->hgt = Max(height(node->lson), height(node->rson)) + 1;