Red-Black Tree 紅黑樹

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。

黑高 = 2 的紅黑樹：

         10(B)
        /     \
      5(R)    20(R)
      / \     / \
    3(B) 7(B) 15(B) 25(B)

最短路徑：10→5→3  長度 2（全黑）
最長路徑：10→5(R)→3  長度 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.color == RED) {           // 情況一
                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 次旋轉解決。

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 修改成本更低。

---

紅黑樹不追求完美平衡，只追求「夠平衡」——工程上通常這樣更快。