經自動化壓力測試的紅黑樹完整實作（含刪除修復）

編輯：關於C語言

專案特色

完整插入、刪除、旋轉、修復邏輯
內建記憶體池分配器（避免頻繁 malloc/free）
自動化壓力測試：隨機插入/刪除 10,000 節點，驗證樹性質
C 語言實作，無外部依賴

核心資料結構

typedef enum { RED, BLACK } color;

typedef struct _redblack {
    color       m_color;
    int         m_data;
    struct _redblack *parent, *left, *right;
} redblack;

typedef struct _wrapdata {
    redblack *root;
    int       size;
} wrapdata;

關鍵演算法

插入修復

新節點標紅 → 父節點若紅則違反性質 → 根據叔節點顏色與 LL/LR/RL/RR 四種情況旋轉+重新著色。

刪除修復

刪除節點後可能破壞黑高平衡 → 根據兄弟節點顏色與姪節點情況，分 mode=0（刪左子）與 mode=1（刪右子）兩條對稱邏輯，透過旋轉與重新著色恢復性質。

驗證機制

check()：遞迴驗證 BST 有序性、父指標正確性
mid_print()：中序列印並統計節點數，對比 size
depth()：計算樹高，觀察平衡度

壓力測試主程式

int main() {
    init_memory_pool();
    wrapdata *tree = calloc(1, sizeof(wrapdata));
    srand(time(NULL));

    while (1) {
        // 插入階段
        while (tree->size < COUNT) {
            insert(tree, rand() % RAND);
            if (check(tree->root) || mid_print(tree->root,0) != tree->size) return 1;
        }
        // 刪除階段
        while (tree->size > COUNT/2) {
            delete(tree, rand() % RAND);
            if (check(tree->root) || mid_print(tree->root,0) != tree->size) return 1;
        }
    }
}