紅黑樹：執法者

演算法背後的故事：官僚的規則

想像一棵樹，每個節點都被塗成 紅色 或 黑色。 一位官僚遞給妳一本規則書：

1. 根規則： 國王（根節點）必須是黑色的。
2. 紅色規則： 如果一個節點是紅色的，她的孩子必須是黑色的（不能有兩個連續的紅色）。
3. 黑高規則： 從國王到最底層的每一條路徑，必須經過完全相同數量的黑色節點。

這些規則看起來很隨意。為什麼是顏色？為什麼要數黑色？ 但這些規則創造了一個數學保證：樹中最長的路徑，永遠不會超過最短路徑的兩倍。 透過強迫樹遵守這些法律，無論妳輸入什麼數據，樹都能保持大致的平衡 ($O(\log N)$)。

為什麼需要它？

• Java 的 TreeMap / TreeSet： 內部使用紅黑樹。
• C++ STL std::map： 使用紅黑樹。
• Linux 內核： 使用紅黑樹進行進程調度（CFS 調度器）和記憶體管理。

演算法是如何「思考」的

這個演算法是一個修正者。 每當妳插入一個節點，妳把她塗成 紅色。這可能會違反規則（例如，出現了兩個連續的紅色）。 演算法隨後使用兩個工具來「修復」這棵樹：

1. 重新著色 (Recoloring)： 將節點從紅變黑（或反之）。
2. 旋轉 (Rotation)： 物理扭轉樹的結構（左旋或右旋）來上下移動節點。

這就像玩魔方。妳走了一步，打亂了它，然後執行一套固定的扭轉序列來恢復秩序。

工程決策：AVL vs. 紅黑樹

• AVL 樹： 嚴格檢查平衡。每一次插入都會觸發檢查。她極其平衡，但寫入速度慢。
  • 適用場景： 讀多寫少（字典）。
• 紅黑樹： 寬鬆檢查平衡。她允許樹稍微有點歪。這使得插入和刪除快得多。
  • 適用場景： 通用負載（標準函式庫）。

實作參考 (Python 概念版)

實作一個完整的紅黑樹需要 200 多行旋轉邏輯。這裡我們實作 左旋 (Left Rotate)，這是平衡的核心機制。

class Node:
    def __init__(self, val, color='RED'):
        self.val = val
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

def left_rotate(tree, x):
    # 將節點 X 向左旋轉
    y = x.right # 設定 y
    
    # 1. 將 y 的左子樹變成 x 的右子樹
    x.right = y.left
    if y.left:
        y.left.parent = x
    
    # 2. 將 y 連結到 x 的父親
    y.parent = x.parent
    if not x.parent:
        tree.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    
    # 3. 將 x 放在 y 的左邊
    y.left = x
    x.parent = y

# 注意：在真實實作中，妳需要在每次插入後檢查顏色
# 並在違反規則時調用 rotate()。

小結

紅黑樹教會我們：絕對的完美是昂貴的。與完美平衡的 AVL 樹不同，紅黑樹接受「足夠好」的平衡以換取速度。她提醒我們，在工程中，一個能稍微彎曲的剛性系統，往往比一個一折就斷的完美系統更耐用。