數據結構：紅黑樹（Red-Black Tree）

從AVL樹的“煩惱”說起

如何用“顏色”來定義“大致平衡”？—— 紅黑樹的五個規則

五個規則如何保證“大致平衡”？

用 C/C++ 代碼定義紅黑樹的結構

定義顏色和節點結構

?定義樹的結構和哨兵節點

從AVL樹的“煩惱”說起

我們從已經了解的 AVL 樹出發。AVL 樹的出發點是什么？

是為了解決二叉搜索樹（Binary Search Tree, BST）在最壞情況下退化成鏈表的問題。它的核心思想是：強制平衡。它有一個非常嚴格的規定：“任意節點左右子樹的高度差 ≤ 1”。

這個規定很有效，保證了樹的高度始終在 O(logN) 級別，因此查找效率非常高。但它的“煩惱”也來源于此：

📌 為了維持這個嚴格的平衡，AVL 樹的插入和刪除操作可能會導致頻繁的旋轉 (Rotation)。有時候，僅僅插入一個節點，就可能需要從插入點一直回溯到根節點，進行多次旋轉。旋轉操作本身是有開銷的。

既然“絕對平衡”的維護成本有點高，我們能不能稍微“放松”一點要求？我們不追求“完美身高”，只追求“身材勻稱”，只要最長路徑和最短路徑的長度別差得太離譜，那它的查找效率不也能保證在 O(logN) 嗎？???

這個“放松要求，換取插入/刪除時更少操作”的想法，就是紅黑樹誕生的根本動機。

第一性原理推導:

目標: 保持樹的查找效率，即樹的高度維持在 O(logN)。
現有方案: AVL 樹通過嚴格限制左右子樹高度差來實現。
痛點: 維護嚴格平衡的成本（旋轉次數）較高。
新思路: 尋找一種弱一點的平衡標準。這個標準必須足夠強，以保證樹高為 O(logN)；又必須足夠弱，以減少插入/刪除時維護平衡的代價。

紅黑樹就是這個新思路的杰出實現。它放棄了用“高度”這個屬性來做限制，而是引入了一個全新的、更巧妙的屬性：顏色 (Color)。

如何用“顏色”來定義“大致平衡”？—— 紅黑樹的五個規則

好，我們現在給每個節點增加一個屬性：color，它可以是紅色 (RED)或黑色 (BLACK)。通過一些“顏色規則 (Coloring Rules)”來限制樹的形態，保證從根到任意葉子的路徑長度不會差太多。

1. 二叉搜索樹的復雜度依賴高度

查找（Search）復雜度 = O(h)，其中 h 是樹高。
如果 h 太大（比如退化成鏈表），復雜度退化為 O(N)。
所以我們必須保證 h = O(log N)。

2. 最短路徑長度與節點數的關系

在一棵二叉樹里，最短路徑長度（記為 h_min）指從根到某個葉子所經過的邊數。
如果所有路徑至少有 h_min 個節點（或邊），那么這棵樹至少包含：2^(h_min) - 1?個節點（這是滿二叉樹的下界）。
因此：N ≥ 2^(h_min) - 1? ? h_min ≤ log2(N+1)

3. 如果最長路徑 ≤ 2 × 最短路徑

設：

h_min = 最短路徑高度
h_max = 最長路徑高度 = 樹的高度

如果能保證：h_max ≤ 2 * h_min

那么結合上面的不等式：h_min ≤ log2(N+1)? ?? ?h_max ≤ 2 * log2(N+1)

于是我們得到了：h_max = O(log N)

我們的最終目標是證明：

一棵紅黑樹從根到最遠葉子節點的路徑長度，不會超過到最近葉子節點路徑長度的兩倍。

如果能證明這一點，就說明樹的高度依然是 O(logN)，我們的目標就達成了。

我們來一步步推導出這些規則：

1??：每個節點要么是紅色，要么是黑色。

這是最基本定義，就像說“游戲里的棋子要么是黑的，要么是白的”。沒有它，后續規則無從談起。

2??：根節點是黑色。

這條規則不是強制性的，但它能簡化很多問題。可以把它看作一個“基準”或“錨點”。

如果根節點是紅色，它可能會違反其他規則（比如后面會提到的“紅色節點的子節點不能是紅色”），所以干脆定為黑色，讓處理更統一。

3??：所有葉子節點都是黑色。

這里的“葉子節點”比較特殊，它不是指最后一個有數據的節點，而是指其下方的 NULL 指針。

在紅黑樹的實現中，我們通常會用一個統一的、黑色的哨兵節點 (Sentinel Node) 來代表所有的 NULL。

這樣做的好處是，處理邊界情況（比如一個節點只有一個子節點）時，我們不需要寫大量的 if (node->left != NULL) 判斷，因為它的 left 和 right 總是指向一個有效的（哨兵）節點。這純粹是為了簡化代碼實現。

至此，我們有了基本的顏色框架。但這些還不足以保證平衡。現在，我們需要引入真正限制樹“形狀”的規則。

4??：紅色節點的子節點必須是黑色的。 (也就是說，不能有兩個連續的紅色節點)

這是實現“放松平衡”的核心規則之一。如果允許紅色節點串在一起（紅->紅->紅...），那這條路徑就會被無限制地拉長，樹就會失衡。

這條規則強制打斷了“紅色路徑”，確保了從根到葉子的路徑上，紅色節點不會連續出現。

5??：從任一節點到其每個葉子（NIL 哨兵節點）的所有路徑，都包含相同數目的黑色節點。

這是另一條核心規則，也是最難理解但最關鍵的一條。它定義了一個叫做“黑高 (Black-Height)”的概念。

這條規則強制要求，無論你從一個節點 x 出發，走左邊還是走右邊，到達終點（葉子）時，路上經過的黑色節點數量必須完全一樣。這就像給樹建立了一個“黑色的骨架”，這個骨架是完美平衡的。紅色節點則可以看作是“填充”在這個黑色骨架之間的節點。

五個規則如何保證“大致平衡”？

現在我們來驗證一下，這五條規則是否達成了我們的最終目標：最長路徑 <= 2 * 最短路徑。

📍最短路徑:

考慮從根節點到一個葉子節點的最短路徑。這條路徑上會包含最少的節點。要讓節點數最少，我們就應該盡量少放紅色節點。

根據規則4，紅色節點不能連續，所以最短的路徑就是一條純黑色的路徑。這條路徑的長度就是這棵樹的黑高 (Black-Height)，我們記為 bh。

📌最長路徑:

要讓路徑最長，我們就應該塞進盡可能多的紅色節點。根據規則4，每兩個黑色節點之間最多只能插入一個紅色節點（黑 -> 紅 -> 黑 -> 紅 ...）。

由于規則5保證了任何路徑上的黑色節點數量都是 bh，那么在最長路徑上，我們最多也就能塞進 bh 個紅色節點。

所以：

最短路徑長度 = bh (全是黑色節點)
最長路徑長度 <= bh (黑色節點) + bh (紅色節點) = 2 * bh

結論：最長路徑長度 <= 2 * 最短路徑長度。

這個結論證明了紅黑樹的高度始終保持在 O(logN) 級別。我們成功地用五條看似無關的顏色規則，間接實現了樹的平衡，而且這個平衡比 AVL 樹更“寬松”。這種寬松，將為我們后續的插入和刪除操作帶來更低的維護成本。

用 C/C++ 代碼定義紅黑樹的結構

好了，理論推導結束。我們現在開始寫代碼，一步步定義出紅黑樹的節點和樹的結構。

定義顏色和節點結構

首先，我們需要一個 enum 來表示顏色。然后定義節點結構 RBTNode。

除了BST原有的 key、left、right 指針，我們還需要 color 屬性和一個指向父節點 (parent) 的指針。父節點指針在后續的旋轉和調整中非常有用，可以避免復雜的遞歸或棧來尋找父節點。

// 使用 C 風格的代碼，不涉及高級語法和STL#include <stdio.h>// 專有名稱: 顏色 (Color)
typedef enum {RED,    // 紅色BLACK   // 黑色
} Color;// 專有名稱: 紅黑樹節點 (Red-Black Tree Node)
typedef struct RBTNode {int key;              // 鍵值Color color;          // 顏色struct RBTNode *left;   // 左子節點指針struct RBTNode *right;  // 右子節點指針struct RBTNode *parent; // 父節點指針
} RBTNode;

這段代碼非常基礎，就是定義了我們討論中需要的所有元素：鍵值、顏色、以及三個方向的指針

?定義樹的結構和哨兵節點

根據規則3，我們需要一個黑色的哨兵節點來代表所有的 NULL 葉子。我們可以定義一個全局的哨兵節點 NIL。樹本身可以用一個指向根節點的指針來表示。

// 接著上面的代碼// 哨兵節點 (Sentinel Node)，代表所有的NULL葉子
RBTNode* NIL;// 紅黑樹結構，本質上是一個指向根節點的指針
typedef struct RedBlackTree {RBTNode* root;
} RedBlackTree;// 初始化函數，用于創建NIL節點
void initializeNIL() {NIL = new RBTNode; // 在C++中用new，在C中用mallocNIL->color = BLACK;NIL->key = 0; // key值無所謂NIL->left = NULL;NIL->right = NULL;NIL->parent = NULL;
}

為什么需要 NIL 哨兵節點？

想象一下，如果沒有 NIL，當你想訪問 node->left->color 時，你必須先檢查 node->left是不是 NULL。而有了 NIL，任何一個節點的 left 和 right 指針，要么指向一個有效的數據節點，要么指向 NIL。

因為 NIL 是一個有確定顏色（黑色）的真實節點，所以你可以安全地訪問 node->left->color，這會讓代碼變得非常整潔。

一個新創建的樹，其根節點應該指向 NIL。

// 創建一棵空樹
RedBlackTree* createRedBlackTree() {RedBlackTree* tree = new RedBlackTree; // C: mallocif (NIL == NULL) {initializeNIL(); // 確保NIL只被初始化一次}tree->root = NIL; // 空樹的根指向NILreturn tree;
}

到目前為止，我們已經成功地：