Java
TreeMap用紅黑樹不用 AVL Tree，是有原因的。
AVL Tree 哪裡不夠好？
AVL Tree 要求左右子樹高度差 ≤ 1，非常嚴格。代價是插入或刪除一個節點後，可能要做很多次旋轉才能修復平衡。
讀多寫少的場景沒問題，但 Map 之類的資料結構增刪查都很頻繁——AVL 的修復成本太高。
紅黑樹的思路是：放寬平衡標準，允許「差不多平衡」，換來插入/刪除最多只需 2–3 次旋轉。
五大性質
1. 每個節點是紅色或黑色
2. 根節點是黑色
3. 所有葉（NIL）是黑色
4. 紅色節點的子節點必須是黑色（不能連續兩個紅）
5. 從任一節點到其所有葉節點的路徑，黑色節點數相同性質 4 + 5 合起來保證：最長路徑 ≤ 最短路徑 × 2，樹高不超過 2 log n。
黑高相同、但路徑長度不同的紅黑樹：
13(B)
/ \
8(B) 17(B)
/ \
15(R) 25(R)
最短路徑：13→8 2 個黑節點（整條全黑）
最長路徑：13→17→15 2 個黑節點 + 1 個紅，多一層卻沒多黑高
紅節點不計入黑高、又不能連兩個紅，所以最長路徑頂多是最短的 2 倍。插入：三種修復情況
新節點一律塗紅色（不影響黑高）。如果父節點也是紅色，違反性質 4，開始修復。
修復看叔叔節點的顏色：
情況一：叔叔是紅色 → 重新著色
G(B) G(R) ← 繼續向上
/ \ / \
P(R) U(R) → P(B) U(B)
/ /
Z(R) Z(R)父和叔變黑、祖父變紅，黑高不變，問題往上推。
情況二：叔叔黑 + 內側子 → 先旋轉，轉成情況三
G(B) G(B)
/ \ / \
P(R) U(B) → Z(R) U(B)
\ /
Z(R) P(R)
對 P 左旋情況三：叔叔黑 + 外側子 → 旋轉 + 變色，修復完成
G(B) P(B)
/ \ / \
P(R) U(B) → Z(R) G(R)
/ \
Z(R) U(B)
對 G 右旋，P 變黑，G 變紅private void insertFixUp(Node z) {
while (z.parent != null && z.parent.color == RED) {
if (z.parent == z.parent.parent.left) {
Node uncle = z.parent.parent.right;
if (uncle != null && uncle.color == RED) { // 情況一（null 葉視為黑）
z.parent.color = BLACK;
uncle.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
} else {
if (z == z.parent.right) { // 情況二 → 情況三
z = z.parent;
leftRotate(z);
}
z.parent.color = BLACK; // 情況三
z.parent.parent.color = RED;
rightRotate(z.parent.parent);
}
}
// 右側為鏡像邏輯...
}
root.color = BLACK;
}刪除
刪除黑色節點時黑高被破壞。修復靠「雙重黑色」概念——把「少了一個黑色」掛在替代節點上往上傳遞。4 種情況（各有鏡像版），最多 3 次旋轉解決。
紅黑樹的賣點就藏在「最多幾次旋轉」這欄——三大操作都是 O(log n)，但修復的旋轉次數有硬上限，這是它比 AVL 划算的地方：
| 操作 | 時間複雜度 | 旋轉次數上限 |
|---|---|---|
| 搜尋 | O(log n) | — |
| 插入 | O(log n) | 最多 2 次 |
| 刪除 | O(log n) | 最多 3 次 |
搜尋跟 AVL 沒差多少（都是 O(log n)），差別全在增刪：AVL 為了維持嚴格平衡，一次修復可能沿路轉好幾次；紅黑樹用「顏色」買到「重新著色也算修復」這條路，很多情況塗個色就過關、根本不必旋轉。
🎬 互動視覺化： B-Tree 插入動畫 — 逐一插入節點，看新節點塗紅後怎麼靠重新著色或旋轉修復性質 4，紅黑交替的規律一眼就懂。
AVL vs Red-Black Tree
| AVL | Red-Black | |
|---|---|---|
| 平衡嚴格度 | 嚴格（BF ≤ 1） | 寬鬆（黑高相等） |
| 查詢 | 略快 | 略慢 |
| 插入/刪除旋轉 | 較多 | 最多 2–3 次 |
| 適用 | 讀多寫少 | 讀寫均衡 |
| 現實 | 部分 DB 索引 | Java TreeMap、Linux scheduler、Nginx |
面試常見：「為什麼 Java TreeMap 用 Red-Black Tree？」——因為 Map 增刪查都頻繁，Red-Black Tree 修改成本更低。
紅黑樹不追求完美平衡，只追求「夠平衡」——工程上通常這樣更快。
接下來往哪走
- B+Tree 資料庫索引的核心結構 — 下一篇：從記憶體的平衡樹走到磁碟的平衡樹
- AVL Tree 自平衡二元搜尋樹 — 表格裡那個「完美主義」對照組，旋轉操作的細節在這裡
- Skip List 跳躍表 — Redis 為什麼不用紅黑樹？跳躍表給了三個理由