紅黑樹原理與C語言完整實現（含測試用例）

前言

紅黑樹是一種自平衡二叉搜尋樹，廣泛應用於 C++ STL（`std::map`、`std::set` 等）、Linux 核心調度器、Nginx、Java `TreeMap` 等關鍵基礎設施。本文整理紅黑樹核心性質、C 語言完整實現（頭文件、源文件、測試用例），並說明關鍵操作邏輯，適合需要深入理解或移植自平衡樹的開發者。

一、紅黑樹五大性質

1. 每個節點非紅即黑。
2. 根節點為黑。
3. 所有葉節點（NIL/空指標）為黑。
4. 紅節點的子節點必為黑（不存在相鄰紅節點）。
5. 從任一節點到其所有後代葉節點的路徑，包含相同數目的黑節點（黑高一致）。

由此可證：高度 ≤ 2·log₂(n+1)，保證查找、插入、刪除最壞情況 O(log n)。

二、核心資料結構

typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    void *key;           // 鍵值（由比較函數決定順序）
    void *value;         // 衛星數據
    struct RBNode *left, *right, *parent;
    Color color;
} RBNode;

typedef struct {
    RBNode *root;
    RBNode *nil;         // 哨兵節點，統一處理邊界
    int (*compare)(const void *, const void *); // 比較函數指標
    void (*free_key)(void *);   // 可選：釋放鍵記憶體
    void (*free_val)(void *);   // 可選：釋放值記憶體
} RBTree;

三、關鍵操作：左旋與右旋

旋轉是維持平衡的核心原語，只改變指標指向，O(1) 完成。

// 左旋：x 為旋轉支點，y = x->right
void rb_rotate_left(RBTree *T, RBNode *x) {
    RBNode *y = x->right;
    x->right = y->left;
    if (y->left != T->nil) y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == T->nil) T->root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
}

右旋對稱實現。

四、插入修正

新節點標紅，可能違反性質 4。透過「叔節點顏色判斷 + 旋轉」三種 Case 修正：

• Case 1：叔節點紅 → 父、叔、祖父重新著色，向上繼續檢查。
• Case 2：叔節點黑且新節點為「內側孩子」 → 先對父節點反向旋轉，轉為 Case 3。
• Case 3：叔節點黑且新節點為「外側孩子」 → 父變黑、祖父變紅、對祖父旋轉，結束。

五、刪除修正

刪除節點後可能違反性質 5（黑高不一致）。引入「雙重黑」概念，四種 Case 處理：

• Case 1：兄弟紅 → 父子變色 + 旋轉，轉為 Case 2/3/4。
• Case 2：兄弟黑且雙侄黑 → 兄弟變紅，向上繼續。
• Case 3：兄弟黑、近側侄紅、遠側侄黑 → 兄弟與近侄變色 + 旋轉，轉 Case 4。
• Case 4：兄弟黑、遠側侄紅 → 兄弟繼承父色、父變黑、遠侄變黑 + 旋轉，結束。

六、完整程式碼結構

• red_black_tree.h：介面宣告、結構體、API 原型
• red_black_tree.c：所有操作實現（init、insert、delete、find、traverse、destroy）
• rbtree_test.c：測試用例（隨機插入/刪除、驗證性質、效能基準）

編譯方式：

gcc -std=c99 -Wall -O2 red_black_tree.c rbtree_test.c -o rbtree_test
./rbtree_test

七、應用場景與變體

• C++ STL：`__rb_tree` 模板，支援多重鍵、自定義分配器。
• Linux Kernel：`struct rb_root` + `rb_insert_color`/`rb_erase`，無遞迴、極度精簡。
• Nginx：`ngx_rbtree_t` 用於 Timer、HTTP/2 流控、緩存淘汰。
• Interval Tree：在節點增補 `max_end`，支援區間查詢。

八、常見坑點提醒

1. 哨兵節點 `nil` 必須統一分配，所有空指標指向它，簡化邊界判斷。
2. 插入/刪除修正循環條件嚴謹，避免無限循環或提前跳出。
3. 比較函數必須滿足嚴格弱序，否則樹結構會損壞。
4. 多線程環境需自行加鎖，紅黑樹本身非線程安全。