🎯 什麼情境該想到我
當你「需要 二元搜尋樹 的有序能力，但不能接受它退化」的時候。
★ 你幾乎不會自己寫它——但你每天都在用它（C++ std::map、Java TreeMap、Linux 排程器與 epoll）。
所以這頁的重點是：它憑什麼保證平衡，以及在 Go 裡該用什麼。
⚙️ 怎麼用（機制與推導）
五條性質
每個節點染成紅或黑，並維持：
- 每個節點非紅即黑
- 根是黑的
- 每個葉（NIL 哨兵）是黑的
- ★ 紅節點的兩個子節點都是黑的（不能有連續兩個紅）
- ★ 從任一節點到其所有後代葉節點的路徑，包含相同數目的黑節點（這個數目叫黑高 black-height）
★ 為什麼這五條就能保證高度
這是紅黑樹唯一真正需要理解的推導：
第 ① 步：黑高為 的子樹，至少有 個內部節點。
（對高度歸納：黑高每增加 1，節點數至少翻倍。）
第 ② 步：由性質 4、5，從根到葉的路徑上「紅節點不能相鄰」
→ 紅節點最多和黑節點一樣多 → （ 為樹高）。
第 ③ 步：合起來
★ 一句話直覺：性質 5 說「所有路徑的黑節點一樣多」，性質 4 說「紅節點不能連續」——
所以最長路徑最多只能是最短路徑的兩倍。這就是「近似平衡」：不像 AVL 樹那樣嚴格，但兩倍已經足夠保證 。
維持平衡的兩種動作
| 動作 | 做什麼 |
|---|---|
| 變色 | 改紅黑屬性，不動結構——便宜 |
| 旋轉 | 改變父子關係， 的局部指標調整，保持中序順序不變 |
右旋 y 左旋 x
y x
/ \ / \
x γ ⇄ α y
/ \ / \
α β β γ
★ 中序走訪前後都是 α x β y γ —— 旋轉不改變順序，只改變高度分佈
插入：先按 BST 規則插入並染紅（染紅只可能違反性質 4，比違反性質 5 容易修），再依「叔叔節點的顏色」分三種情況向上修復。
刪除：比插入複雜（要處理「雙黑」），有四種情況。
兩者都是 ，且旋轉次數是 （插入最多 2 次、刪除最多 3 次）。
★ 紅黑樹 vs AVL 樹（常見追問）
| 紅黑樹 | AVL 樹 | |
|---|---|---|
| 平衡條件 | 最長路徑 ≤ 2× 最短 | 左右子樹高度差 ≤ 1 |
| 高度 | （更矮） | |
| 查找 | 稍慢 | 稍快 |
| ★ 插入／刪除 | 旋轉次數少，修復便宜 | 旋轉次數多 |
| 適合 | 寫多讀多的通用場景 | 讀遠多於寫 |
→ 標準庫選紅黑樹，是因為它在「增刪改查混合」的通用工作負載上更均衡。
★ 在 Go 裡該用什麼（Go 標準庫沒有有序 map/set）
| 需求 | 做法 |
|---|---|
| 資料不常變、要有序查詢 | ★ 排序過的 slice + slices.BinarySearch。最簡單、快取最友善——多數情況的正解（見 二分搜尋） |
| 頻繁增刪且要有序／範圍查詢 | 第三方 B-tree（如 google/btree）或跳表 |
| 只要極值 | 二元堆積（container/heap） |
| 只要查找不要順序 | map（見 雜湊表） |
★ 不要在 Go 裡手寫紅黑樹。 刪除的修復邏輯有四種情況、極易寫錯，
而且在現代硬體上它的快取表現通常輸給「排序 slice」或「B 樹」。
它實際在哪裡被用
| 系統 | 用途 |
|---|---|
C++ std::map / std::set | 標準實作 |
Java TreeMap / TreeSet | 標準實作 |
| Linux 核心 | CFS 排程器（依 vruntime 排序）、epoll 的 fd 管理、虛擬記憶體區域（VMA） |
| Nginx | 計時器 |
★ 為什麼資料庫用 B 樹不用紅黑樹
紅黑樹是二元的：每次比較只排除一半， 要走約 60 層，每層一次可能的 I/O。
B 樹一個節點裝上百個鍵（剛好一個磁碟頁／快取行），同樣的資料量只要 3–4 層。
磁碟與快取的世界裡，「減少節點訪問次數」遠比「減少比較次數」重要。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- ★ 不要自己實作。用標準庫或成熟的第三方。
- 快取不友善：每個節點獨立配置、只裝一個鍵。大資料量請改用 B 樹家族。
- 只要查找就用雜湊表。 勝過 ，而且常數也小很多。
- 靜態資料用排序 slice。建好之後只查不改的話，紅黑樹沒有任何優勢。
- 並行修改要全樹鎖或複雜的細粒度鎖。高並行場景考慮跳表（更容易做無鎖）——這也是 Redis 的 sorted set 用跳表的原因之一。
- 記憶體開銷：每節點多兩個指標 + 顏色位元。
- 面試通常不會要你手寫刪除。能講清楚五條性質、 的推導、旋轉不改變中序這三件事就夠了。
🔗 相關工具
- 二元搜尋樹 —— 基礎，以及它為什麼會退化
- 二分搜尋 —— Go 裡的實務替代方案（排序 slice）
- 雜湊表 —— 對照：更快但沒有順序
- 二元堆積 —— 只要極值時更輕量
- 工具-儲存引擎B-Tree與LSM-Tree —— B 樹在資料庫裡的完整樣貌
- 工具-資料結構的選擇 —— 決策層
- 演算法導論