紅黑樹#
為什麼需要平衡樹？#
普通 BST 在頻繁插入刪除後可能退化成連結串列，時間複雜度從 O(log n) 退化到 O(n)。
平衡的意義：保持樹的高度接近 log n，確保操作效率穩定。
紅黑樹的定義#
紅黑樹是一種近似平衡的二元搜尋樹，需滿足：
- 節點是紅色或黑色
- 根節點是黑色
- 葉節點 (NIL) 是黑色（空節點）
- 紅色節點的子節點必為黑色（不能有連續紅節點）
- 從任一節點到其所有葉節點的路徑，黑色節點數量相同
條件 3 的 NIL 節點是為了簡化實作，實際上可共用同一個黑色空節點。
為什麼是「近似」平衡？#
| 樹類型 | 高度 | 平衡嚴格度 |
|---|---|---|
| AVL 樹 | ≈ log₂n | 嚴格（左右高度差 ≤ 1） |
| 紅黑樹 | ≤ 2log₂n | 寬鬆（最長路徑 ≤ 2 倍最短） |
推導：
- 去除紅節點後，黑節點形成的樹高度 ≤ log₂n
- 紅節點不能連續，加回紅節點後高度 ≤ 2log₂n
為什麼工程偏好紅黑樹？#
| 特性 | AVL 樹 | 紅黑樹 |
|---|---|---|
| 查詢效率 | 略優 | 稍遜 |
| 插入/刪除 | 調整頻繁 | 調整較少 |
| 實作複雜度 | 較複雜 | 較簡單 |
| 適用場景 | 讀多寫少 | 讀寫均衡 |
工程結論：紅黑樹性能穩定，適合需要頻繁動態更新的場景。Java 的 TreeMap、C++ 的 map 都採用紅黑樹。
平衡調整基本操作#
旋轉#
- 左旋 (Left Rotation)：將右子節點提升為父節點
- 右旋 (Right Rotation)：將左子節點提升為父節點
插入後調整#
新插入節點預設為紅色，可能違反「不能有連續紅節點」的規則。
三種調整情況
CASE 1：叔叔節點是紅色
- 父節點、叔叔節點變黑
- 祖父節點變紅
- 關注節點移到祖父節點
CASE 2：叔叔是黑色，當前節點是父的右子節點
- 對父節點左旋
- 轉換為 CASE 3
CASE 3：叔叔是黑色，當前節點是父的左子節點
- 對祖父節點右旋
- 父節點與祖父節點交換顏色
學習建議：
- 理解紅黑樹的用途和性質即可
- 不需要背誦旋轉細節（工程中不會手寫）
- 如需手動實現平衡樹，跳表是更簡單的替代方案