紅黑樹的特性與實現

在數據結構領域，二叉搜索樹（BST）憑借 O (log n) 的平均時間復雜度成為查找、插入和刪除操作的優選結構。但它有個致命缺陷：當輸入數據有序時，會退化為鏈表，時間復雜度驟降至 O (n)。為解決這一問題，計算機科學家設計了多種自平衡二叉搜索樹，紅黑樹（Red-Black Tree）便是其中應用最廣泛的一種。它通過巧妙的著色規則和有限的旋轉操作，在保證平衡的同時將維護成本降到最低，成為 STL 容器、Linux 內核等工業級系統的核心數據結構。本文將從底層原理到工程實踐，全面剖析紅黑樹的工作機制。

一、紅黑樹的核心特性與平衡原理

紅黑樹是一種自平衡二叉搜索樹，其每個節點除了存儲鍵值、左右子節點和父節點指針外，還額外包含一個顏色屬性（紅色或黑色）。通過嚴格遵循以下 5 條性質，紅黑樹實現了結構平衡：

顏色約束：每個節點要么是紅色，要么是黑色。
根節點規則：根節點必須是黑色。
葉子節點規則：所有葉子節點（NIL 節點，即空節點）都是黑色。
連續紅色禁止：如果一個節點是紅色，則它的兩個子節點必須是黑色（不存在連續的紅色節點）。
黑色平衡規則：從任意節點到其所有后代葉子節點的路徑中，包含的黑色節點數量相同（稱為 "黑高"）。

平衡原理深度解析

這些特性共同構建了紅黑樹的 "平衡能力"：

性質 4 避免了 "紅色鏈" 的無限延伸，限制了樹的傾斜程度；
性質 5 保證了所有路徑的 "黑高" 一致，而紅色節點僅能穿插在黑色節點之間；
由此可推導出關鍵結論：紅黑樹中最長路徑的長度不會超過最短路徑的 2 倍（最短路徑全為黑色節點，最長路徑為黑紅交替）。

這一結論直接確保了紅黑樹的高度始終為 O (log n)，從而保證了所有操作的最壞時間復雜度為 O (log n)。

二、紅黑樹的節點結構與基礎定義

2.1 節點結構設計

紅黑樹的節點需要存儲 5 類信息：鍵值、顏色、左子節點、右子節點和父節點。為簡化邊界條件處理（如空節點的顏色判斷），通常將所有空節點統一指向一個哨兵節點（NIL 節點），該節點永久為黑色，且左右子節點和父節點均指向自身。

enum Color { RED, BLACK };// 節點結構定義
struct Node {int key;          // 鍵值Color color;      // 節點顏色Node *left;       // 左子節點Node *right;      // 右子節點Node *parent;     // 父節點// 構造函數：新節點默認紅色（插入時優化）Node(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};// 哨兵節點定義（全局唯一）
Node *NIL_NODE = new Node(0);
NIL_NODE->color = BLACK;
NIL_NODE->left = NIL_NODE;
NIL_NODE->right = NIL_NODE;
NIL_NODE->parent = NIL_NODE;

2.2 關鍵設計細節

哨兵節點的作用：將所有空指針替換為 NIL_NODE，避免在操作中頻繁判斷nullptr，統一邊界處理邏輯；
新節點默認紅色：插入紅色節點僅可能違反性質 4（連續紅色），而插入黑色節點會直接違反性質 5（黑高不一致），前者修復成本更低；
父節點指針的必要性：紅黑樹的旋轉和修復操作需要回溯到祖先節點，必須通過父指針實現向上遍歷。

三、紅黑樹的核心操作：插入與修復

3.1 插入流程

紅黑樹的插入操作分為兩步：

按 BST 規則插入：找到合適位置插入新節點（默認紅色）；
修復紅黑樹性質：通過旋轉和變色消除對紅黑樹性質的破壞。

插入核心代碼（BST 部分

void insert(Node *&root, int key) {Node *z = new Node(key);Node *y = NIL_NODE;  // 記錄x的父節點Node *x = root;// 查找插入位置while (x != NIL_NODE) {y = x;if (z->key < x->key) {x = x->left;} else {x = x->right;}}// 確定新節點的父節點z->parent = y;if (y == NIL_NODE) {root = z;  // 樹為空，新節點成為根} else if (z->key < y->key) {y->left = z;} else {y->right = z;}// 初始化新節點的子節點為哨兵z->left = NIL_NODE;z->right = NIL_NODE;z->color = RED;  // 新節點默認紅色// 修復紅黑樹性質insertFixup(root, z);
}

3.2 插入后的修復操作（insertFixup）

插入紅色節點后，可能違反的性質為：

性質 2（根節點為紅色）：僅當插入的是第一個節點時可能發生；
性質 4（連續紅色節點）：當父節點為紅色時發生。

修復過程通過循環處理，直到上述性質均被滿足。根據 "叔節點"（父節點的兄弟節點）的顏色，分為 3 種情況：

情況 1：叔節點為紅色

場景：新節點（z）的父節點（p）為紅色，叔節點（u）為紅色；
破壞性質：僅可能違反性質 4（連續紅色）；
修復邏輯：
1. 將父節點（p）和叔節點（u）改為黑色；
2. 將祖父節點（g）改為紅色；
3. 令 z = g，繼續向上修復（祖父節點可能與它的父節點形成連續紅色）。

// 情況1：叔節點為紅色
case 1:z->parent->parent->left->color = BLACK;  // 叔節點變黑z->parent->parent->right->color = BLACK; // 父節點變黑z->parent->parent->color = RED;          // 祖父節點變紅z = z->parent->parent;                   // 向上追溯break;

情況 2：叔節點為黑色，且新節點是右孩子

場景：父節點（p）為紅色，叔節點（u）為黑色，z 是右孩子；
破壞性質：性質 4（連續紅色）；
修復邏輯：
1. 對父節點（p）執行左旋，將 z 轉為左孩子；
2. 轉化為情況 3 處理（統一修復邏輯）。

// 情況2：叔節點為黑色，z是右孩子
case 2:z = z->parent;              // z指向父節點leftRotate(root, z);        // 左旋父節點// 轉化為情況3

情況 3：叔節點為黑色，且新節點是左孩子

場景：父節點（p）為紅色，叔節點（u）為黑色，z 是左孩子；
破壞性質：性質 4（連續紅色）；
修復邏輯：
1. 對祖父節點（g）執行右旋；
2. 交換父節點（p）和祖父節點（g）的顏色；
3. 修復完成（無需繼續向上追溯）。

// 情況3：叔節點為黑色，z是左孩子
case 3:z->parent->color = BLACK;   // 父節點變黑z->parent->parent->color = RED;  // 祖父節點變紅rightRotate(root, z->parent->parent);  // 右旋祖父節點z = root;  // 退出循環break;

3.3 旋轉操作的實現

旋轉是紅黑樹維護平衡的核心手段，分為左旋和右旋，作用是改變節點間的父子關系而不破壞 BST 性質。

左旋操作（leftRotate）

void leftRotate(Node *&root, Node *x) {Node *y = x->right;  // y是x的右子節點x->right = y->left;  // 將y的左子樹轉為x的右子樹if (y->left != NIL_NODE) {y->left->parent = x;  // 更新y左子樹的父節點}y->parent = x->parent;  // 更新y的父節點// 處理x是根節點的情況if (x->parent == NIL_NODE) {root = y;} else if (x == x->parent->left) {x->parent->left = y;  // x是左孩子時，y替代x的位置} else {x->parent->right = y; // x是右孩子時，y替代x的位置}y->left = x;  // x成為y的左孩子x->parent = y;  // 更新x的父節點
}

右旋操作（rightRotate）

右旋與左旋對稱，核心是將左子節點提升為父節點，此處不再贅述。

四、紅黑樹的刪除操作與修復

刪除操作是紅黑樹中最復雜的部分，核心挑戰是如何在刪除節點后維持紅黑樹的 5 條性質。刪除流程分為 3 步：

按 BST 規則刪除節點：找到待刪除節點，根據節點的子節點數量（0、1、2）執行不同刪除邏輯；
記錄關鍵信息：跟蹤 "替代節點"（實際被移除的節點）及其原始顏色；
修復紅黑樹性質：若刪除的是黑色節點，需通過修復流程恢復平衡。

4.1 BST 刪除邏輯

葉子節點（無孩子）：直接刪除；
單孩子節點：用子節點替代該節點；
雙孩子節點：找到中序后繼（右子樹最小節點），復制其值到當前節點，再刪除后繼節點（轉化為前兩種情況）。

4.2 刪除后的修復操作（deleteFixup）

刪除節點后，若被刪除節點是黑色，會破壞性質 5（黑高不一致），此時需要通過 "雙重黑色" 標記來修復。"雙重黑色" 表示該路徑上缺少一個黑色節點，需要通過以下 4 種情況消除：

情況 1：兄弟節點為紅色

場景：當前節點（x）為雙重黑色，兄弟節點（s）為紅色；
修復邏輯：
1. 將兄弟節點（s）改為黑色，父節點（p）改為紅色；
2. 對父節點（p）執行左旋；
3. 轉化為其他情況（兄弟節點變為黑色）。

情況 2：兄弟節點為黑色，且兄弟的兩個孩子均為黑色

場景：x 為雙重黑色，s 為黑色，s 的左右孩子均為黑色；
修復邏輯：
1. 將兄弟節點（s）改為紅色；
2. 令 x = p（將雙重黑色上移）；
3. 繼續向上修復。

情況 3：兄弟節點為黑色，左孩子紅色，右孩子黑色

場景：x 為雙重黑色，s 為黑色，s 的左孩子紅、右孩子黑；
修復邏輯：
1. 將 s 的左孩子改為黑色，s 改為紅色；
2. 對 s 執行右旋；
3. 轉化為情況 4。

情況 4：兄弟節點為黑色，右孩子為紅色

場景：x 為雙重黑色，s 為黑色，s 的右孩子為紅色；
修復邏輯：
1. 將 s 的顏色改為 p 的顏色；
2. 將 p 改為黑色，s 的右孩子改為黑色；
3. 對 p 執行左旋；
4. 令 x = root（修復完成）。

4.3 修復操作的核心目標

消除 "雙重黑色" 標記，恢復路徑上的黑高平衡；
避免出現連續紅色節點，維持性質 4；
通過最少的旋轉和變色操作完成修復，降低時間開銷。

五、紅黑樹與 AVL 樹的深度對比

特性	紅黑樹	AVL 樹
平衡標準	顏色規則 + 黑高平衡	左右子樹高度差≤1（嚴格平衡）
旋轉次數	插入最多 2 次，刪除最多 3 次	插入最多 2 次，刪除可能 O (log n)
空間開銷	存儲顏色（1bit）	存儲平衡因子（通常需 2-4bit）
查找性能	平均 O (log n)，最壞 O (2log n)	嚴格 O (log n)（高度更優）
插入 / 刪除性能	更優（旋轉少）	較差（嚴格平衡導致旋轉頻繁）
適用場景	插入刪除頻繁的場景（如 STL 容器）	查找頻繁的場景（如數據庫索引）

紅黑樹的工業級優勢：在大多數實際場景中，紅黑樹的綜合性能優于 AVL 樹。雖然 AVL 樹的高度更優，但紅黑樹的旋轉操作更少，維護成本更低，尤其適合插入刪除頻繁的動態數據場景。

六、紅黑樹的實際應用場景

C++ STL 容器：std::map、std::set、std::multimap等關聯容器底層均采用紅黑樹實現，利用其 O (log n) 的插入、刪除和查找性能；
Linux 內核：
- 進程調度：CFS（完全公平調度器）用紅黑樹管理進程運行隊列，快速找到下一個待調度進程；
- 虛擬內存管理：VM_area_struct 結構體用紅黑樹組織，高效管理內存區域；
Java 集合框架：TreeMap、TreeSet底層基于紅黑樹，提供有序映射和集合功能；
數據庫：部分數據庫（如 MongoDB）的索引結構采用紅黑樹，平衡查詢和更新性能；
編譯器實現：語法分析階段的符號表常用紅黑樹存儲變量和函數信息，支持快速查找和插入。