紅黑樹完整實現與超大量隨機數生成測試

紅黑樹核心特性回顧

紅黑樹作為自平衡二元搜尋樹，維持以下五大性質確保操作複雜度為 O(log n)：

1. 節點非紅即黑
2. 根節點為黑
3. 空節點（NIL）視為黑
4. 紅節點的子節點必為黑
5. 任一節點到葉節點的所有路徑包含相同數目的黑節點

程式架構說明

資料結構定義

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;

核心操作函數

• rb_insert：插入節點並透過 rb_insert_rebalance 維持平衡
• rb_search：標準二元搜尋樹查找
• rb_erase：刪除節點並透過 rb_erase_rebalance 修復紅黑性質
• rb_rotate_left/right：左右旋轉基礎操作

插入修正算法詳解

新節點標記為紅，若父節點也為紅則違反性質 4，需分情況處理：

情況 1：叔節點為紅

父、叔改黑，祖父改紅，將祖父作為新檢查節點繼續向上處理。

情況 2：叔節點為黑且節點為內側孩子

先對父節點進行相反方向旋轉轉化為情況 3。

情況 3：叔節點為黑且節點為外側孩子

父改黑、祖父改紅、對祖父進行同方向旋轉，修正完成。

刪除修正算法詳解

刪除黑節點會導致路徑黑高減少，需從被刪節點的子節點開始向上修正：

核心邏輯

將「雙重黑」問題向上傳遞，透過兄弟節點顏色及其子節點顏色分情況旋轉重新著色，直到節點變紅或到達根節點。

測試驗證設計

超大量隨機數生成策略

程式採用 GetRdm(min, max) 宏生成偽隨機數，並每 32768 次呼叫 srand(time(NULL)) 重置種子，試圖緩解 rand() 週期短的問題。實際測試插入 1000 萬筆資料，並與 std::map 交叉驗證正確性。

完整測試流程

1. 插入測試：同步插入紅黑樹與 std::map，檢測鍵值一致性
2. 查找測試：遍歷 std::map 驗證紅黑樹查找結果
3. 刪除測試：依序刪除所有節點，驗證記憶體管理（useCount 計數器）

程式碼亮點與不足

亮點

• 完整實現紅黑樹所有核心操作，邏輯清晰
• 採用哨兵節點簡化邊界條件判斷
• 記憶體分配/釋放配對檢查，防洩漏

改進建議

• 隨機數品質低，建議改用 std::mt19937 或系統熵源
• 遞迴實現可能導致棧溢位，大數據量建議改迭代
• 缺乏迭代器支援，不便於範圍查詢
• 未封裝為類，介面不夠現代化

總結

本程式提供了教學級別的紅黑樹完整 C 實現，適合演算法學習參考。工程應用建議直接使用 std::map/std::set 或成熟庫（如 Linux 核心 rbtree.h），避免重複造輪子引入風險。