紅黑樹核心原理與 Nginx 實作解析

前言

紅黑樹是一種自平衡二元搜尋樹，廣泛應用於標準庫（如 C++ STL `map`/`set`、Java `TreeMap`）與核心系統（Linux 核心、Nginx）。本文以 Nginx 原始碼為例，系統梳理紅黑樹的五大性質、插入/刪除修正邏輯，並對照原始碼加以解析。

一、紅黑樹五大性質

1. 每個節點非紅即黑。
2. 根節點為黑。
3. 所有葉節點（NIL/哨兵）為黑。
4. 紅節點的子節點必為黑（不存在連續紅節點）。
5. 任一節點到其所有葉節點的路徑，黑節點數相同（黑高一致）。

這些性質保證：最長路徑不超過最短路徑的 2 倍，查找/插入/刪除時間複雜度維持 O(log n)。

二、插入操作與修正案例

新插入節點標記為紅。若父節點為黑，無違規；若父節點為紅，違反性質 4，需透過旋轉與重新著色修正。設當前節點 X，父節點 P，祖父節點 PP，叔叔節點 S。

Case I1：叔叔節點為黑，X 為 P 左子，P 為 PP 左子（LL 型）

1. P 改黑，PP 改紅。
2. PP 右旋。

鏡像情況（RR 型）對稱處理。

Case I2：叔叔節點為黑，X 為 P 右子，P 為 PP 左子（LR 型）

1. P 左旋，轉為 I1（LL 型）。
2. 套用 I1 步驟。

鏡像情況（RL 型）對稱處理。

Case I3：叔叔節點為紅

1. P、S 改黑，PP 改紅。
2. 將 PP 視為新的 X，向上遞迴檢查。若遞迴至根，將根設為黑。

三、刪除操作與修正案例

刪除先依二元搜尋樹規則處理（至多一個非空子節點的節點直接替補；雙子節點找後繼節點替換），再針對被刪除節點原本顏色為黑的情況進行修正。設修正節點 X（實際替補上來的節點），父節點 P，兄弟節點 S，S 的左右子節點 Sl、Sr。

Case D1：S 為紅

• S 改黑，P 改紅，對 P 進行旋轉（左旋若 X 為左子），轉為 D2/D3/D4。

Case D2：S 為黑，Sl、Sr 均為黑

• S 改紅，X 指向 P，繼續向上修正（整棵子樹黑高減 1，需向上補償）。

Case D3：S 為黑，Sl 為紅，Sr 為黑

• S 改紅，Sl 改黑，對 S 右旋，轉為 D4。

Case D4：S 為黑，Sr 為紅（Sl 任意）

• S 取 P 的顏色，P 改黑，Sr 改黑，對 P 左旋。修正完成。

鏡像情況對稱處理。可見 D1→D2/D3/D4→D4 才真正結束修正。

四、Nginx 原始碼對照

4.1 插入函數 ngx_rbtree_insert

void ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) {
    /* 1. 普通 BST 插入 */
    ngx_rbtree_node_t **root = &tree->root;
    ngx_rbtree_node_t *sentinel = tree->sentinel;
    if (*root == sentinel) { /* 空樹 */ ... }
    tree->insert(*root, node, sentinel);

    /* 2. 修正迴圈：while (node != root && parent 是紅) */
    while (node != *root && ngx_rbt_is_red(node->parent)) {
        if (node->parent == node->parent->parent->left) {
            temp = node->parent->parent->right; /* 叔叔 */
            if (ngx_rbt_is_red(temp)) { /* I3 */
                ngx_rbt_black(node->parent);
                ngx_rbt_black(temp);
                ngx_rbt_red(node->parent->parent);
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) { /* I2 */
                    node = node->parent;
                    ngx_rbtree_left_rotate(root, sentinel, node);
                }
                /* I1 */
                ngx_rbt_black(node->parent);
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
            }
        } else { /* 鏡像 */ ... }
    }
    ngx_rbt_black(*root); /* 根永遠設黑 */
}

程式碼精確對應理論三種案例，迴圈條件 `node != *root && parent 為紅` 確保只在違規時修正。

4.2 刪除函數 ngx_rbtree_delete

void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) {
    /* 1. BST 刪除，找出實際被移除節點 subst 及其子節點 temp */
    /* ... 處理 0/1/2 子節點情況，subst 為實際刪除節點 ... */

    /* 2. 若 subst 為紅，直接返回（黑高未變） */
    if (red) return;

    /* 3. 修正迴圈：while (temp != root && temp 為黑) */
    while (temp != *root && ngx_rbt_is_black(temp)) {
        if (temp == temp->parent->left) {
            w = temp->parent->right; /* 兄弟 */
            if (ngx_rbt_is_red(w)) { /* D1 */
                ngx_rbt_black(w);
                ngx_rbt_red(temp->parent);
                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                w = temp->parent->right;
            }
            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { /* D2 */
                ngx_rbt_red(w);
                temp = temp->parent;
            } else {
                if (ngx_rbt_is_black(w->right)) { /* D3 */
                    ngx_rbt_black(w->left);
                    ngx_rbt_red(w);
                    ngx_rbtree_right_rotate(root, sentinel, w);
                    w = temp->parent->right;
                }
                /* D4 */
                ngx_rbt_copy_color(w, temp->parent);
                ngx_rbt_black(temp->parent);
                ngx_rbt_black(w->right);
                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                temp = *root; /* 跳出迴圈 */
            }
        } else { /* 鏡像 */ ... }
    }
    ngx_rbt_black(temp);
}

程式碼結構清晰對應 D1-D4，利用 `w` 代表兄弟節點，`temp` 為修正節點 X。最終 `ngx_rbt_black(temp)` 確保根或紅節點變黑結束。

五、總結

紅黑樹透過嚴格的五大性質與局部旋轉/重新著色，在 O(log n) 內完成動態集合操作。Nginx 實作極具參考價值：哨兵節點簡化邊界判斷、迴圈修正替代遞迴、程式碼高度對應理論案例。深入研讀其原始碼，有助於掌握平衡樹工程化實作精髓。