紅黑樹 RedBlack Tree

學習目標

• 理解紅黑樹的定義和性質
• 掌握紅黑樹的插入操作和修復機制
• 掌握紅黑樹的刪除操作和修復機制
• 理解紅黑樹的顏色規則和旋轉操作
• 能夠實作紅黑樹的基本操作

1. 紅黑樹的基本概念

1.1 為什麼需要紅黑樹？

問題: 普通的二元搜尋樹 (BST) 可能退化成鏈表，搜尋時間變成 O(n)。

解決方案: 紅黑樹是一種自平衡的二元搜尋樹，透過顏色標記和旋轉操作保持近似平衡。

1.2 定義

紅黑樹是一種二元搜尋樹，滿足以下五個性質：

1. 顏色性質: 每個節點是紅色或黑色
2. 根節點性質: 根節點是黑色
3. 葉節點性質: 所有葉節點（NIL 節點）都是黑色
4. 紅色節點性質: 如果一個節點是紅色，則它的兩個子節點都是黑色（不能有兩個連續的紅色節點）
5. 路徑性質: 從任意節點到其每個葉節點的所有路徑都包含相同數量的黑色節點（黑高度相同）

1.3 黑高度 (Black Height)

黑高度 (bh) 是指從某個節點到葉節點的路徑上黑色節點的數量（不包括該節點本身）。

重要: 紅黑樹的性質 5 保證了所有路徑的黑高度相同。

1.4 範例

以下是一個紅黑樹（用 R 表示紅色，B 表示黑色）：

         10(B)
       /      \
      5(R)    15(B)
     /  \     /  \
   3(B) 7(B) 12(R) 18(R)

驗證性質: - ✓ 根節點 10 是黑色 - ✓ 沒有兩個連續的紅色節點 - ✓ 所有路徑的黑高度都是 2（從根到葉：10→5→3, 10→5→7, 10→15→12, 10→15→18）

2. 紅黑樹的節點結構

2.1 節點定義

enum Color { RED, BLACK };

struct Node {
    int data;
    Color color;
    struct Node* left;
    struct Node* right;
    struct Node* parent;
};

2.2 NIL 節點

• 紅黑樹使用 NIL 節點（空節點）作為葉節點
• 所有實際的 NULL 指標都指向同一個 NIL 節點
• NIL 節點是黑色的

3. 紅黑樹的旋轉操作

紅黑樹使用與 AVL 樹相同的旋轉操作，但目的不同： - AVL 樹: 保持嚴格平衡（高度差 ≤ 1） - 紅黑樹: 保持近似平衡（黑高度相同）

3.1 左旋 (Left Rotation)

struct Node* leftRotate(struct Node* x) {
    struct Node* y = x->right;
    x->right = y->left;

    if (y->left != NULL)
        y->left->parent = x;

    y->parent = x->parent;

    if (x->parent == NULL)
        root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;

    y->left = x;
    x->parent = y;

    return y;
}

3.2 右旋 (Right Rotation)

struct Node* rightRotate(struct Node* y) {
    struct Node* x = y->left;
    y->left = x->right;

    if (x->right != NULL)
        x->right->parent = y;

    x->parent = y->parent;

    if (y->parent == NULL)
        root = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;

    x->right = y;
    y->parent = x;

    return x;
}

4. 紅黑樹的插入操作

4.1 基本步驟

1. 標準 BST 插入: 按照 BST 的規則插入新節點
2. 設為紅色: 新節點設為紅色（保持黑高度）
3. 修復違規: 如果違反紅黑樹性質，進行修復
4. 修復類型: 主要處理「兩個連續紅色節點」的違規

4.2 插入演算法

Insert(root, key):
    1. 標準 BST 插入，新節點設為紅色
    2. 如果新節點是根節點:
        設為黑色，返回
    3. 如果父節點是黑色:
        不需要修復，返回
    4. 如果父節點是紅色（違規）:
        根據叔父節點的顏色進行修復
        a. 如果叔父是紅色:
           重新著色（父、叔父變黑，祖父變紅）
           遞迴修復祖父節點
        b. 如果叔父是黑色或不存在:
           根據節點位置進行旋轉和重新著色

4.3 插入情況分析

情況 1: 叔父節點是紅色

情況: 新節點、父節點、叔父節點都是紅色

修復: 重新著色 - 父節點 → 黑色 - 叔父節點 → 黑色 - 祖父節點 → 紅色 - 遞迴檢查祖父節點

範例:

插入前:
       20(B)
      /    \
    10(R)  30(R)
   /
  5(R)  ← 新插入

修復後:
       20(R)  ← 需要繼續檢查
      /    \
    10(B)  30(B)
   /
  5(R)

情況 2: 叔父節點是黑色，新節點是父節點的右子節點

情況: 父節點是紅色，叔父是黑色，新節點是右子節點

修復: 先左旋父節點，轉換為情況 3

範例:

插入前:
       20(B)
      /
    10(R)
      \
      15(R)  ← 新插入

左旋 10:
       20(B)
      /
    15(R)
    /
  10(R)

現在轉為情況 3

情況 3: 叔父節點是黑色，新節點是父節點的左子節點

情況: 父節點是紅色，叔父是黑色，新節點是左子節點

修復: 右旋祖父節點，並重新著色 - 父節點 → 黑色 - 祖父節點 → 紅色

範例:

插入前:
       20(B)
      /
    10(R)
    /
   5(R)  ← 新插入

右旋 20，重新著色:
       10(B)
      /    \
    5(R)   20(R)

4.4 C 語言實作

// 插入節點
struct Node* insert(struct Node* root, int key) {
    // 標準 BST 插入
    struct Node* node = BSTInsert(root, key);
    node->color = RED;  // 新節點設為紅色

    // 修復紅黑樹性質
    return insertFixup(root, node);
}

// 修復插入後的違規
struct Node* insertFixup(struct Node* root, struct Node* z) {
    while (z->parent != NULL && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            // 父節點是左子節點
            struct Node* y = z->parent->parent->right;  // 叔父節點

            if (y != NULL && y->color == RED) {
                // 情況 1: 叔父是紅色
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                // 情況 2 或 3: 叔父是黑色
                if (z == z->parent->right) {
                    // 情況 2: 新節點是右子節點
                    z = z->parent;
                    root = leftRotate(root, z);
                }
                // 情況 3: 新節點是左子節點
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                root = rightRotate(root, z->parent->parent);
            }
        } else {
            // 對稱情況：父節點是右子節點
            struct Node* y = z->parent->parent->left;

            if (y != NULL && y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    root = rightRotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                root = leftRotate(root, z->parent->parent);
            }
        }
    }

    root->color = BLACK;  // 根節點始終是黑色
    return root;
}

5. 紅黑樹的刪除操作

5.1 基本步驟

1. 標準 BST 刪除: 按照 BST 的規則刪除節點
2. 記錄顏色: 記錄被刪除節點的顏色
3. 修復違規: 如果刪除的是黑色節點，可能違反黑高度性質，需要修復
4. 修復類型: 主要處理「黑高度不平衡」的違規

5.2 刪除情況分析

刪除操作比插入更複雜，因為需要考慮多種情況。

情況 1: 刪除的節點是紅色

處理: 直接刪除，不影響黑高度

情況 2: 刪除的節點是黑色，替代節點是紅色

處理: 將替代節點改為黑色

情況 3: 刪除的節點是黑色，替代節點也是黑色

處理: 需要複雜的修復過程，根據兄弟節點的顏色和子節點情況進行處理

5.3 刪除修復的詳細情況

當刪除黑色節點後，如果替代節點也是黑色，需要根據以下情況修復：

情況 A: 兄弟節點是紅色

修復: - 將兄弟節點改為黑色 - 將父節點改為紅色 - 對父節點進行旋轉 - 轉換為情況 B、C 或 D

情況 B: 兄弟節點是黑色，兄弟的兩個子節點都是黑色

修復: - 將兄弟節點改為紅色 - 將問題向上移動到父節點

情況 C: 兄弟節點是黑色，兄弟的遠端子節點是黑色，近端子節點是紅色

修復: - 交換兄弟和近端子節點的顏色 - 對兄弟節點進行旋轉 - 轉換為情況 D

情況 D: 兄弟節點是黑色，兄弟的遠端子節點是紅色

修復: - 將兄弟節點的顏色設為父節點的顏色 - 將父節點和遠端子節點設為黑色 - 對父節點進行旋轉

5.4 C 語言實作（簡化版）

// 刪除節點
struct Node* deleteNode(struct Node* root, int key) {
    struct Node* z = search(root, key);
    if (z == NULL) return root;

    struct Node* y = z;  // 要刪除的節點
    Color yOriginalColor = y->color;
    struct Node* x;  // 替代節點

    if (z->left == NULL) {
        x = z->right;
        transplant(root, z, z->right);
    } else if (z->right == NULL) {
        x = z->left;
        transplant(root, z, z->left);
    } else {
        y = minValueNode(z->right);
        yOriginalColor = y->color;
        x = y->right;

        if (y->parent == z) {
            if (x != NULL) x->parent = y;
        } else {
            transplant(root, y, y->right);
            y->right = z->right;
            if (y->right != NULL) y->right->parent = y;
        }

        transplant(root, z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }

    if (yOriginalColor == BLACK)
        root = deleteFixup(root, x);

    free(z);
    return root;
}

// 修復刪除後的違規
struct Node* deleteFixup(struct Node* root, struct Node* x) {
    while (x != root && (x == NULL || x->color == BLACK)) {
        if (x == x->parent->left) {
            struct Node* w = x->parent->right;  // 兄弟節點

            if (w->color == RED) {
                // 情況 A
                w->color = BLACK;
                x->parent->color = RED;
                root = leftRotate(root, x->parent);
                w = x->parent->right;
            }

            if ((w->left == NULL || w->left->color == BLACK) &&
                (w->right == NULL || w->right->color == BLACK)) {
                // 情況 B
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right == NULL || w->right->color == BLACK) {
                    // 情況 C
                    if (w->left != NULL) w->left->color = BLACK;
                    w->color = RED;
                    root = rightRotate(root, w);
                    w = x->parent->right;
                }
                // 情況 D
                w->color = x->parent->color;
                x->parent->color = BLACK;
                if (w->right != NULL) w->right->color = BLACK;
                root = leftRotate(root, x->parent);
                x = root;
            }
        } else {
            // 對稱情況
            // ... (類似處理)
        }
    }

    if (x != NULL) x->color = BLACK;
    return root;
}

6. 紅黑樹 vs. AVL 樹

6.1 比較表

特性	紅黑樹	AVL 樹
平衡嚴格度	近似平衡	嚴格平衡
搜尋效能	O(log n)	O(log n)（稍快）
插入效能	O(log n)	O(log n)（可能更快）
刪除效能	O(log n)	O(log n)（可能更慢）
旋轉次數	插入最多 2 次，刪除最多 3 次	可能更多
實作複雜度	中等	較複雜
應用場景	Java TreeMap, C++ map	需要嚴格平衡的場景

6.2 選擇建議

• 選擇紅黑樹: 需要頻繁插入和刪除的場景
• 選擇 AVL 樹: 需要頻繁搜尋且插入/刪除較少的場景

7. 紅黑樹的複雜度分析

7.1 時間複雜度

• 搜尋: O(log n) - 樹的高度最多是 2log(n+1)
• 插入: O(log n) - 最多需要 2 次旋轉
• 刪除: O(log n) - 最多需要 3 次旋轉

7.2 空間複雜度

• 儲存: O(n) - 需要儲存 n 個節點和顏色資訊
• 遞迴堆疊: O(log n)

8. 實際應用

8.1 程式語言實作

• Java: TreeMap, TreeSet 使用紅黑樹
• C++: std::map, std::set 使用紅黑樹
• Linux 核心: 使用紅黑樹管理記憶體

8.2 為什麼選擇紅黑樹？

• 效能平衡: 在搜尋、插入、刪除之間取得良好平衡
• 實作相對簡單: 比 AVL 樹的實作稍簡單
• 旋轉次數少: 插入和刪除的旋轉次數有上限

9. 練習題

練習題 1

請說明紅黑樹的五個性質。

參考答案： 1. 每個節點是紅色或黑色 2. 根節點是黑色 3. 所有葉節點（NIL）都是黑色 4. 紅色節點的兩個子節點都是黑色（不能有兩個連續的紅色節點） 5. 從任意節點到其每個葉節點的所有路徑都包含相同數量的黑色節點

練習題 2

請比較紅黑樹和 AVL 樹的差異。

參考答案： - 平衡嚴格度: AVL 樹嚴格平衡（高度差 ≤ 1），紅黑樹近似平衡 - 搜尋效能: AVL 樹稍快（更平衡） - 插入/刪除: 紅黑樹通常更快（旋轉次數有上限） - 實作複雜度: 紅黑樹相對簡單

練習題 3

在紅黑樹中插入節點時，什麼情況下只需要重新著色，什麼情況下需要旋轉？

參考答案： - 只需要重新著色: 當叔父節點是紅色時，將父節點、叔父節點改為黑色，祖父節點改為紅色 - 需要旋轉: 當叔父節點是黑色或不存在時，需要根據節點位置進行左旋或右旋，並重新著色

10. 考試重點提醒

1. 五個性質: 必須記住紅黑樹的五個性質
2. 插入修復: 理解三種插入情況的修復方法
3. 刪除修復: 理解四種刪除情況的修復方法
4. 旋轉操作: 掌握左旋和右旋的操作
5. 與 AVL 比較: 理解紅黑樹和 AVL 樹的差異和選擇