經自動化壓力測試驗證的紅黑樹 C 實作 (含完整刪除邏輯)

專案簡介

本文提供一個 **純 C 語言** 實作的紅黑樹，包含插入、刪除、查找、中序列印、驗證等功能，並內建 **自動化壓力測試主程式**：隨機插入/刪除 10,000 節點，持續驗證樹性質 (BST 有序性、紅黑規則、黑高一致)，確保刪除邏輯正確無誤。

核心資料結構

#pragma pack(1)
typedef enum _color { RED, BLACK } color;

typedef struct _redblack {
    color       m_color;
    int         m_data;                // 鍵值
    struct _redblack *parent;
    struct _redblack *left;
    struct _redblack *right;
} redblack;

// 記憶體池包裝 (避免頻繁 malloc/free 影響測試效能)
typedef struct _wrapredblack {
    struct _wrapredblack *next;
    redblack real;
} wrapredblack;

typedef struct _wrapdata {
    redblack *root;
    int size;
} wrapdata;
#pragma pack()

關鍵演算法函數

壓力測試主程式邏輯

int main() {
    init_memory_pool(); // 初始化節點池
    wrapdata *tree = calloc(1, sizeof(wrapdata));
    srand(time(NULL));

    while (1) {
        // 隨機插入直到節點數達 COUNT (10000)
        while (tree->size < COUNT) {
            insert(tree, rand() % RAND);
            validate(tree); // 每步驗證
        }
        // 隨機刪除直到節點數降至 COUNT/2
        while (tree->size > COUNT/2) {
            delete(tree, rand() % RAND);
            validate(tree);
        }
    }
    return 0;
}

驗證函數

int validate(wrapdata *tree) {
    if (check(tree->root)) { mid_print(tree->root, 0); return 1; } // BST 性質違反
    if (mid_print(tree->root, 0) != tree->size) return 1;           // 節點數不符
    if (error_label) return 1;                                    // 遞迴過深
    return 0;
}

程式碼特色

• 完整刪除實作：涵蓋無子、單子、雙子 (用後繼節點替換) 三種情況，配合 delete_fixup 完整處理所有紅黑違規 Case。
• 記憶體池：預先配置 2*RAND 節點，mycalloc/myfree 從池取/還，提升測試速度並便於檢測 use-after-free。
• 內建自測：無需外部測試腳本，編譯執行即可無限循環壓測，任何違規即刻停止並列印樹狀態。
• 標準 C (C89/C99)：無平台相依性，可在 Linux/Windows/嵌入式環境直接編譯。

編譯與執行

gcc -o rbtree_test rbtree.c
./rbtree_test
# 程式會持續運行並輸出中間樹狀 (size=6666 時)，直到發現錯誤或手動停止

適用場景

• 教學參考：紅黑樹刪除修復邏輯的完整 C 實作範例。
• 嵌入式系統：無 STL/Boost 環境下的有序映射/集合需求。
• 面試準備：手寫紅黑樹刪除的標準參考實作。