紅黑樹C++模板實現（二）：核心數據結構與插入邏輯

繼上篇理論鋪墊，本文給出基於《算法導論》的紅黑樹C++模板完整實現，採用哨兵節點簡化邊界判斷，支援任意鍵值類型與關聯數據。代碼已整理為標準頭文件格式，可直接集成專案。

核心數據結構設計

template <class KEY, class U>
class RB_Tree {
private:
    enum COLOR { RED, BLACK };

    class RB_Node {
    public:
        RB_Node() : RB_COLOR(BLACK), right(nullptr), left(nullptr), parent(nullptr) {}
        COLOR RB_COLOR;
        RB_Node* right;
        RB_Node* left;
        RB_Node* parent;
        KEY key;
        U data;
    };

    RB_Node* m_root;      // 根節點
    RB_Node* m_nullNode;  // 哨兵節點（統一替代 NULL）
    // ... 複製構造/賦值刪除，防止淺拷貝

關鍵設計亮點

1. 哨兵節點：構造函數中m_nullNode自指（left/right/parent均指向自身），顏色固定為黑。所有葉子NULL統一替換為m_nullNode，消除了無數if (node == nullptr)分支。
2. 模板雙參數：KEY為排序鍵，U為衛星數據，完美契合map<K,V>語義。
3. 私有複製控制：刪除拷貝構造與賦值運算符，避免指標所有權混淆。

查找與插入入口

// 查找鍵值，若不存在返回插入位置（父節點或哨兵）
RB_Node* find(KEY key) {
    RB_Node* index = m_root;
    while (index != m_nullNode) {
        if (key < index->key) index = index->left;
        else if (key > index->key) index = index->right;
        else break;  // 命中
    }
    return index;
}

// 插入主流程：BST插入 → 標紅 → FIXUP修復
bool Insert(KEY key, U data) {
    RB_Node* insert_point = m_nullNode;
    RB_Node* index = m_root;
    // 1. 尋找插入位置
    while (index != m_nullNode) {
        insert_point = index;
        if (key < index->key) index = index->left;
        else if (key > index->key) index = index->right;
        else return false;  // 鍵值已存在
    }
    // 2. 創建新節點（此處省略 new RB_Node 細節）
    // 3. 建立父子鏈接
    // 4. 新節點著紅，左右指向哨兵
    // 5. RB_INSERT_FIXUP 恢復紅黑性質
    // ...
}

下一步預告

下篇將完整呈現RB_INSERT_FIXUP的三種情況處理（叔紅變色、LL/LR型旋轉）、LeftRotate/RightRotate指標操作細節，以及刪除操作的RB_DELETE_FIXUP四種情況實現。敬請期待。