【本節要點】
- 紅黑樹概念
- 紅黑樹性質
- 紅黑樹結點定義
- 紅黑樹結構
- 紅黑樹插入操作的分析
一、紅黑樹的概念與性質
1.1 紅黑樹的概念
紅黑樹 ，是一種 二叉搜索樹 ，但 在每個結點上增加一個存儲位表示結點的顏色，可以是 Red和 Black 。 通過對 任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路 徑會比其他路徑長出倆倍 ，因而是 接近平衡 的。
紅黑樹構造：[10(黑)] / \[5(紅)] [20(黑)]/ \ / \[3(黑)] [8(黑)] [15(紅)] [25(紅)]/ \ / \ / \ / \NIL NIL NIL NIL NIL NIL NIL NIL1.2 紅黑樹的性質?
- 1. 每個結點不是紅色就是黑色
- 2. 根節點是黑色的?
- 3. 如果一個節點是紅色的，則它的兩個孩子結點是黑色的?
- 4. 對于每個結點，從該結點到其所有后代葉結點的簡單路徑上，均包含相同數目的黑色結點?
- 5. 每個葉子結點都是黑色的(此處的葉子結點指的是空結點)
?以上五點性質可以保證：其最長路徑中節點個數不會超過最短路徑節點個數的兩倍。
?二、紅黑樹結點定義
// 結點的顏色
enum Colour
{RED,BLACK,
};// 紅黑樹結點的定義
template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv; // 結點的鍵值對RBTreeNode<K, V>* _left; // 結點的左孩子RBTreeNode<K, V>* _right; // 結點的右孩子RBTreeNode<K, V>* _parent; // 結點的雙親（紅黑樹需要旋轉，為了實現簡單所以給出該結點）Colour _col; // 結點的顏色// 結點的構造函數RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};
注意：紅黑樹定義結點時，默認結點顏色為紅色，這一設計選擇直接增加紅黑樹的平衡維護效率和整體性能，大大減少時間復雜度。
三、紅黑樹的結構
// 以本數組為例
num[3, 5, 8, 10, 15, 20, 25]紅黑樹構造：[10(黑)] / \[5(紅)] [20(黑)]/ \ / \[3(黑)] [8(黑)] [15(紅)] [25(紅)]/ \ / \ / \ / \NIL NIL NIL NIL NIL NIL NIL NIL圖示說明
-
根結點標記：根結點?
10?為黑色，符合性質2（根結點必黑） -
紅色結點規則：紅色結點?
5、15、25?的子結點均為黑色，滿足性質3（紅色結點不連續） -
黑高一致性驗證：從根結點到任意 NIL 的路徑黑色結點數均為?2
-
NIL結點處理：所有葉子結點顯式標記為 NIL（黑色），符合性質5
-
最長/最短路徑對比
路徑類型 示例路徑 結點數 比例 最短路徑 10→20→NIL 2 1:1 最長路徑 10→5→3→NIL 3 1.5:1 理論極限 紅黑交替路徑（未出現） ≤4 ≤2:1
?四、紅黑樹的插入操作
[開始插入新結點Z]│▼┌─────────執行標準BST插入─────────┐│ │▼ ▼[Z設為紅色] [保持BST性質]│▼┌─────父結點P是否為紅色？─────┐│ │▼ (是) ▼ (否)[存在雙紅沖突需處理] [插入完成]│▼┌────叔結點U的顏色？────┐│ │▼ (紅色) ▼ (黑色/NIL)
[Case1: 顏色翻轉] [判斷沖突結構類型]│ │▼ ├─────────────────────────┐
[將P、U設為黑色] ▼ ▼│ [Z-P-G呈三角型] [Z-P-G呈直線型]▼ │ │
[將G設為紅色] [Case2: 旋轉父結點] [Case3: 旋轉祖父結點]│ │ │▼ ▼ ▼
[以G為新Z向上回溯] [轉為直線型沖突] [交換顏色并旋轉]│▼[調整完成]│▼[最終確保根結點為黑]4.1?基本BST插入階段
-
插入位置遵循二叉搜索樹規則
-
新結點初始顏色必須為紅色（最小化規則破壞）
4.2 沖突檢測階段
- 要素1：父結點狀態判斷
- 要素2：叔結點顏色判定
- 要素3：沖突結構類型識別
4.3??典型場景演練
場景1：叔結點為紅（Case1）
G(黑) G(紅)/ \ 顏色翻轉 / \P(紅) U(紅) → P(黑) U(黑)/ /Z(紅) Z(紅)檢測要點：
確認U存在且為紅
將沖突標記上移給G
繼續以G作為新Z向上檢測
場景2：叔結點為黑-三角型（Case2）
G(黑) G(黑)/ /P(紅) → Z(紅)\ /Z(紅) P(紅)檢測要點：
判斷Z是P的右子結點
識別為三角型沖突
轉換為直線型處理
場景3：叔結點為黑-直線型（Case3）
G(黑) P(黑)/ / \P(紅) → Z(紅) G(紅)/Z(紅)檢測要點：
確認Z是P的左子結點
直接觸發祖父旋轉
完成顏色交換
?4.4 總結
沖突檢測階段通過三級條件篩選（父結點狀態→叔結點顏色→沖突結構類型），將復雜的平衡問題分解為可控的局部操作。這種分層檢測機制：
- 確保90%以上的插入操作只需1次檢測即可完成
- 將最壞情況的時間復雜度嚴格控制在O(log n)
- 為后續的旋轉/顏色調整提供精準的操作依據
該設計體現了紅黑樹"以檢測換計算，以分類求高效"的核心優化思想，是其能在大規模數據場景下保持卓越性能的關鍵所在。
以上就是紅黑樹初階知識的了解，接下來我會繼續更新紅黑樹進階：紅黑樹的模擬實現、使用紅黑樹底層對map和set容器的模擬實現。制作不易，請大家多多點贊收藏啦！！
