STL 源碼剖析筆記（18）：AVL 平衡二叉樹 C++ 模板實作

AVL 樹是最早發明的自平衡二叉搜尋樹。任一節點的左右子樹高度差絕對值 ≤ 1，確保樹高為 O(log n)，查找、插入、刪除平均與最壞情況均為 O(log n)。

核心概念：平衡因子與旋轉

節點平衡因子 = 左子樹高度 - 右子樹高度。因子為 -1、0、1 視為平衡；±2 需旋轉重新平衡。

插入總發生在葉節點。插入後從葉節點向根追蹤，找到第一個平衡因子變化的節點 X。新節點相對 X 的四種位置決定旋轉類型：

• LL（左左）：新節點在 X 左孩子的左子樹 → 右單旋轉
• RR（右右）：新節點在 X 右孩子的右子樹 → 左單旋轉
• LR（左右）：新節點在 X 左孩子的右子樹 → 左右雙旋轉
• RL（右左）：新節點在 X 右孩子的左子樹 → 右左雙旋轉

雙旋轉可分解為兩次單旋轉。

程式碼架構

採用 C++ 類別封裝 + 模板，支援任意可比較型別。節點結構：

template 
class AVLNode {
public:
    KeyType key;
    AVLNode* left;
    AVLNode* right;
    AVLNode() : key(0), left(nullptr), right(nullptr) {}
    AVLNode(KeyType k) : key(k), left(nullptr), right(nullptr) {}
};

AVLTree 類別宣告

template 
class AVLTree {
    typedef AVLNode Node;
    Node* m_root;

    // 內部輔助函數
    int Height(Node* root) const;
    int BalanceFactor(Node* root) const;
    Node* LLRotation(Node* root);
    Node* RRRotation(Node* root);
    Node* LRRotation(Node* root);
    Node* RLRotation(Node* root);
    Node* Balance(Node* root);
    Node* Insert(Node* root, const KeyType& key);
    Node* Delete(Node* root, const KeyType& key);
    Node* FindMin(Node* root) const;
    Node* FindMax(Node* root) const;
    void Inorder(Node* root) const;
    void Destroy(Node* root);

public:
    AVLTree() : m_root(nullptr) {}
    AVLTree(const vector& vec);
    AVLTree(const KeyType* arr, size_t len);
    ~AVLTree() { Destroy(m_root); }

    void Insert(const KeyType& key) { m_root = Insert(m_root, key); }
    bool Delete(const KeyType& key);
    bool Search(const KeyType& key) const;
    void InorderTraversal() const;
    bool IsEmpty() const { return m_root == nullptr; }
};

關鍵實作：插入與平衡

template 
typename AVLTree::Node* AVLTree::Insert(Node* root, const KeyType& key) {
    if (!root) return new Node(key);

    if (key < root->key)
        root->left = Insert(root->left, key);
    else if (key > root->key)
        root->right = Insert(root->right, key);
    else
        return root; // 重複鍵值不插入

    return Balance(root);
}

template 
typename AVLTree::Node* AVLTree::Balance(Node* root) {
    int bf = BalanceFactor(root);
    if (bf > 1) { // 左高
        if (BalanceFactor(root->left) >= 0)
            return LLRotation(root);
        else
            return LRRotation(root);
    } else if (bf < -1) { // 右高
        if (BalanceFactor(root->right) <= 0)
            return RRRotation(root);
        else
            return RLRotation(root);
    }
    return root;
}

四種旋轉實作

// RR：左單旋轉
template 
typename AVLTree::Node* AVLTree::RRRotation(Node* root) {
    Node* tmp = root->right;
    root->right = tmp->left;
    tmp->left = root;
    return tmp;
}

// LL：右單旋轉
template 
typename AVLTree::Node* AVLTree::LLRotation(Node* root) {
    Node* tmp = root->left;
    root->left = tmp->right;
    tmp->right = root;
    return tmp;
}

// LR：先對左孩子 RR，再對根 LL
template 
typename AVLTree::Node* AVLTree::LRRotation(Node* root) {
    root->left = RRRotation(root->left);
    return LLRotation(root);
}

// RL：先對右孩子 LL，再對根 RR
template 
typename AVLTree::Node* AVLTree::RLRotation(Node* root) {
    root->right = LLRotation(root->right);
    return RRRotation(root);
}

刪除節點

刪除較複雜，需處理三種情況：葉節點、單一子節點、雙子節點。雙子節點時，用左子樹最大值或右子樹最小值取代，再遞歸刪除該取代節點。刪除後同樣需向上檢查平衡並旋轉。

建構與銷毀

• 預設建構函數
• 向量/陣列建構：逐一插入元素
• 解構函數：後序遍歷遞歸釋放所有節點

測試程式

int main() {
    vector vec = {7, 6, 5, 4, 3, 2, 1};
    AVLTree avl(vec);
    avl.Insert(8);

    cout << "中序遍歷: ";
    avl.InorderTraversal(); // 輸出: 1 2 3 5 6 7 8

    cout << "\n搜尋 4: " << (avl.Search(4) ? "找到" : "未找到");
    avl.Delete(4);
    cout << "\n刪除 4 後搜尋: " << (avl.Search(4) ? "找到" : "未找到");
    return 0;
}

完整程式碼已在 Visual Studio 2013 / Windows 7 32-bit 環境驗證通過。