紅黑樹 (Red-Black Tree)#

為什麼需要平衡樹？#

普通 BST 在頻繁插入刪除後可能退化成連結串列，時間複雜度從 O(log n) 退化到 O(n)。

平衡的意義：保持樹的高度接近 log n，確保操作效率穩定。

紅黑樹的定義#

紅黑樹是一種近似平衡的二元搜尋樹，需滿足：

1. 節點是紅色或黑色
2. 根節點是黑色
3. 葉節點 (NIL) 是黑色（空節點）
4. 紅色節點的子節點必為黑色（不能有連續紅節點）
5. 從任一節點到其所有葉節點的路徑，黑色節點數量相同

條件 3 的 NIL 節點是為了簡化實作，實際上可共用同一個黑色空節點。

為什麼是「近似」平衡？#

推導：

1. 去除紅節點後，黑節點形成的樹高度 ≤ log₂n
2. 紅節點不能連續，加回紅節點後高度 ≤ 2log₂n

為什麼工程偏好紅黑樹？#

工程結論：紅黑樹性能穩定，適合需要頻繁動態更新的場景。Java 的 TreeMap、C++ 的 map 都採用紅黑樹。

平衡調整基本操作#

旋轉#

• 左旋 (Left Rotation)：將右子節點提升為父節點
• 右旋 (Right Rotation)：將左子節點提升為父節點

旋轉只是局部改接指標，並不破壞 BST 的中序順序——這是它能在維持有序性的前提下調整高度的關鍵。

// 左旋：把節點 x 的右子 y 提升為父，x 變成 y 的左子
//     x                y
//      \      ➡️      /
//       y          x
private fun rotateLeft(x: TreeNode): TreeNode {
    val y = x.right!!          // y 必存在才可左旋
    x.right = y.left           // y 的左子樹改接到 x 的右邊
    y.left = x                 // x 下降為 y 的左子
    return y                   // y 成為這棵子樹的新根
}

// 右旋：左旋的鏡像
private fun rotateRight(x: TreeNode): TreeNode {
    val y = x.left!!           // y 必存在才可右旋
    x.left = y.right           // y 的右子樹改接到 x 的左邊
    y.right = x                // x 下降為 y 的右子
    return y                   // y 成為這棵子樹的新根
}

插入後調整#

新插入節點預設為紅色，可能違反「不能有連續紅節點」的規則。

學習建議：

• 理解紅黑樹的用途和性質即可
• 不需要背誦旋轉細節（工程中不會手寫）
• 如需手動實作平衡樹，跳表是更簡單的替代方案