樹與圖（進階）：旋轉、並查集與最短路徑的正確性

為什麼你的二元搜尋樹會「退化成一條鏈」？

假設你讀完入門篇，已經知道二元搜尋樹（Binary Search Tree, BST）的查找平均是 $O(\log n)$。於是你興沖沖地寫了一個 BST，把使用者依註冊順序得到的學號 1, 2, 3, 4, 5, ... 一個一個插進去。然後你發現：查找變得跟陣列線性掃描一樣慢。為什麼？

因為當資料已經有序時，每個新節點都掛在前一個節點的右子樹，整棵樹退化成一條長度為 $n$ 的鏈（linked list），高度從理想的 $\log n$ 暴增到 $n$。這正是入門篇通常一筆帶過、但決定資料結構生死的關鍵：樹的效能不取決於它「是不是樹」，而取決於它「有多平衡」。

這篇進階文章不再重述什麼是樹、什麼是 BFS／DFS。我們直接進入三個更硬的主題：(1) 樹如何透過旋轉維持平衡；(2) 不相交集合（Disjoint Set）這個被低估的資料結構；(3) 帶權圖上的最短路徑與最小生成樹背後的貪婪正確性論證。

平衡的代價：旋轉（Rotation）

要讓樹永遠維持 $O(\log n)$ 高度，核心操作是旋轉——一種在保持 BST 中序（in-order）大小關係不變的前提下，重新分配父子關係、改變子樹高度的局部操作。

考慮一個右旋（right rotation）。設節點 y 的左子是 x，x 有右子樹 T2：

      y                x
     / \              / \
    x   T3   ──►     T1  y
   / \                  / \
  T1  T2               T2  T3

旋轉後 x 成為新的子樹根，y 變成 x 的右子，而原本 x 的右子樹 T2 改掛到 y 的左邊。關鍵在於：中序走訪結果 T1 < x < T2 < y < T3 完全不變，所以「搜尋樹性質」被保留，但子樹高度被重新分配了。

class Node:
    __slots__ = ('key', 'left', 'right', 'height')
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        self.height = 1   # 葉節點高度為 1

def h(node):
    return node.height if node else 0

def update_height(node):
    node.height = 1 + max(h(node.left), h(node.right))

def rotate_right(y):
    x = y.left
    t2 = x.right
    # 旋轉
    x.right = y
    y.left = t2
    # 高度必須由下往上更新：先 y 再 x
    update_height(y)
    update_height(x)
    return x   # 回傳新的子樹根

def rotate_left(x):
    y = x.right
    t2 = y.left
    y.left = x
    x.right = t2
    update_height(x)
    update_height(y)
    return y

注意更新高度的順序：y 變成 x 的子節點，所以必須先更新 y 的高度，x 的高度才會正確。這是初學者實作旋轉最常踩的雷。

AVL 樹：用平衡因子驅動旋轉

AVL 樹（以發明者 Adelson-Velsky 與 Landis 命名）規定每個節點的平衡因子（balance factor）= 左子樹高 − 右子樹高，必須落在 $\{-1, 0, +1\}$。一旦插入或刪除後某節點失衡（平衡因子變成 $\pm 2$），就用旋轉修復。失衡有四種型態：LL、RR、LR、RL。

def balance_factor(node):
    return h(node.left) - h(node.right) if node else 0

def rebalance(node):
    update_height(node)
    bf = balance_factor(node)
    # 左重
    if bf > 1:
        if balance_factor(node.left) < 0:   # LR 型：先左旋子節點
            node.left = rotate_left(node.left)
        return rotate_right(node)           # LL 型
    # 右重
    if bf < -1:
        if balance_factor(node.right) > 0:  # RL 型：先右旋子節點
            node.right = rotate_right(node.right)
        return rotate_left(node)            # RR 型
    return node

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    else:
        return node   # 不允許重複鍵
    return rebalance(node)

AVL 樹保證高度 $h \le 1.44 \log_2(n+2)$，因此所有操作都是嚴格 $O(\log n)$。代價是插入／刪除時可能需要多次旋轉與高度更新，常數因子比紅黑樹（red-black tree）略高——這也是為什麼大多數標準函式庫（如 C++ std::map、Java TreeMap）選紅黑樹：它放寬平衡條件，換取更少的旋轉次數，特別利於寫入密集的場景。AVL 則在讀取密集（查找遠多於修改）時更佔優，因為它更「矮」。

被低估的資料結構：不相交集合（Disjoint Set / Union-Find）

入門篇談圖時通常聚焦走訪。但有一類問題——「這兩個節點屬於同一個連通分量嗎？」「加入這條邊會不會形成環？」——用 BFS／DFS 每次都重跑太慢。不相交集合（又稱並查集）正是為此而生：它把元素分組成若干互不相交的集合，支援兩個近乎 $O(1)$ 的操作。

• find(x)：回傳 x 所屬集合的「代表元」（root）。
• union(x, y)：合併 x 與 y 所在的兩個集合。

樸素實作是一片「森林」，每個集合是一棵樹，根節點即代表元。但若不優化，樹也會退化成鏈。兩個經典優化讓它近乎常數時間：按秩合併（union by rank）與路徑壓縮（path compression）。

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))   # 一開始每個元素自成一集合
        self.rank = [0] * n            # 樹的近似高度

    def find(self, x):
        # 路徑壓縮：把沿途節點直接掛到根
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False   # 已在同一集合，回傳 False 代表「會形成環」
        # 按秩合併：矮樹掛到高樹下，避免長高
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

同時使用這兩個優化後，$m$ 次操作的總時間是 $O(m\,\alpha(n))$，其中 $\alpha$ 是反阿克曼函數（inverse Ackermann function）。對任何實際可能出現的 $n$（即使大到全宇宙的原子數），$\alpha(n) \le 4$。所以你可以放心當它是常數。

看一個例子：Kruskal 演算法用 DSU 偵測環

最小生成樹（Minimum Spanning Tree, MST）的 Kruskal 演算法，核心就是「把邊按權重由小到大排序，逐一加入，只要不形成環就保留」。「會不會形成環」恰好就是 union 回傳 False 的情況：

def kruskal(n, edges):
    # edges: list of (weight, u, v)
    edges.sort()                 # 按權重排序，O(E log E)
    dsu = DSU(n)
    mst, total = [], 0
    for w, u, v in edges:
        if dsu.union(u, v):      # u、v 原本不連通，加這條邊不成環
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:
                break            # 已有 n-1 條邊，MST 完成
    return mst, total

edges = [(1,0,1),(2,1,2),(2,0,2),(3,2,3),(4,1,3)]
print(kruskal(4, edges))   # ([(0, 1, 1), (1, 2, 2), (2, 3, 3)], 6)

整體複雜度由排序主宰，為 $O(E \log E)$。DSU 的部分幾乎免費。

帶權圖的最短路徑：為什麼 Dijkstra 不能有負邊？

入門篇的 BFS 能在無權圖（或每條邊權重相同）找最短路，因為 BFS 一層一層擴展，先碰到目標的層數就是最短步數。但一旦邊有不同權重，BFS 失效——最少「邊數」不等於最小「總權重」。

Dijkstra 演算法把 BFS 的佇列換成優先佇列（priority queue，即最小堆），每次取出「目前已知距離最短」的未確定節點，將它「定案」，再鬆弛（relax）它的鄰邊。

import heapq

def dijkstra(graph, src):
    # graph: dict[node] -> list of (neighbor, weight)
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    pq = [(0, src)]              # (目前距離, 節點)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue            # 過時的條目，跳過（lazy deletion）
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

用二元堆實作，複雜度是 $O((V + E) \log V)$。

關鍵限制：Dijkstra 假設所有邊權非負。它的正確性建立在「一旦某節點被取出定案，它的距離就不會再變短」這個貪婪不變量上。若存在負權邊，一個已定案節點的距離可能被後來經過負邊的路徑再縮短，整個貪婪假設崩潰。

動手算一下：負邊如何欺騙 Dijkstra

考慮三個節點 A、B、C，邊為 $A \to B = 1$、$A \to C = 5$、$C \to B = -10$。

從 A 出發，Dijkstra 先取出 A（距離 0），鬆弛得 $\text{dist}[B] = 1$、$\text{dist}[C] = 5$。接著取出最小的 B（距離 1），將 B 定案為 1。但真正的最短路是 $A \to C \to B = 5 + (-10) = -5$！Dijkstra 因為太早把 B 定案而錯過。

處理負邊要改用 Bellman-Ford 演算法：對所有邊鬆弛 $V-1$ 輪，複雜度 $O(VE)$，較慢但能處理負權，並能在第 $V$ 輪仍可鬆弛時偵測出負權環（negative cycle，此時最短路無定義）。

def bellman_ford(n, edges, src):
    # edges: list of (u, v, w)
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break                    # 提前收斂
    # 第 n 輪仍能鬆弛 => 存在負權環
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise ValueError("圖中存在負權環，最短路無定義")
    return dist

有向無環圖（DAG）與拓樸排序

許多真實問題天然是有向無環圖（Directed Acyclic Graph, DAG）：課程的先修關係、編譯系統的相依性、試算表的儲存格公式。它們的共同需求是「找一個合法的線性處理順序，使每個任務都排在它所有前置任務之後」——這就是拓樸排序（topological sort）。

Kahn 演算法用入度（in-degree）逐步剝離：

from collections import deque

def topo_sort(graph, n):
    indeg = [0] * n
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    queue = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    if len(order) != n:
        raise ValueError("圖中有環，無法拓樸排序")
    return order

複雜度 $O(V + E)$。漂亮之處在於：若最後 order 的長度不足 $n$，就證明圖裡有環——拓樸排序順帶成了環偵測器。在 DAG 上，拓樸排序也讓最短／最長路徑能以 $O(V+E)$ 線性解決（按拓樸序鬆弛），這是一般帶權圖做不到的。

重點回顧

• 平衡決定一切：未平衡的 BST 在有序輸入下退化成 $O(n)$ 鏈；AVL／紅黑樹透過旋轉維持 $O(\log n)$，旋轉的本質是保持中序不變、重新分配子樹高度。
• AVL vs 紅黑樹的取捨：AVL 更矮、查找快，適合讀取密集；紅黑樹旋轉少、寫入快，是多數標準函式庫的預設。
• Union-Find 以按秩合併 + 路徑壓縮達到近乎常數的 $O(\alpha(n))$，是 Kruskal MST 與動態連通性問題的核心引擎。
• 最短路徑要看權重正負：Dijkstra（貪婪，$O((V+E)\log V)$）只適用非負邊；負邊須用 Bellman-Ford（$O(VE)$），它還能偵測負權環。
• DAG 上的拓樸排序 解決相依性排序，$O(V+E)$，並兼具環偵測能力。

深入探討（研究所視角）

攤銷分析（amortized analysis）與勢能函數。 Union-Find 的 $O(\alpha(n))$ 不是單次操作的最壞界，而是攤銷界——個別 find 可能較慢，但路徑壓縮會「投資」未來，使長序列操作平均極快。嚴格證明用 Tarjan 的勢能法（potential method），定義每個節點的勢能隨秩與壓縮狀態變化，證明總攤銷成本受反阿克曼函數約束。這套框架同樣支撐動態陣列倍增、Fibonacci heap 的 decrease-key 等分析。

Dijkstra 的資料結構選擇與理論下界。 用二元堆是 $O((V+E)\log V)$；改用 Fibonacci heap 可把 decrease-key 攤銷降到 $O(1)$，理論複雜度進步到 $O(E + V\log V)$，在稠密圖（$E \approx V^2$）上漸進更優。但 Fibonacci heap 常數大、實作複雜，實務上常被配對堆（pairing heap）取代。對整數權重，Thorup 證明了單源最短路可達線性 $O(V+E)$，繞過了比較模型的 $\Omega(V \log V)$ 下界。

平衡樹的統一視角與持久化。 AVL、紅黑樹、Treap、Splay 樹、加權平衡樹（weight-balanced tree）可視為「不同平衡不變量 + 旋轉修復」的同一家族。Splay 樹放棄顯式平衡欄位，改以攤銷保證，並有著名的「動態最適猜想」（dynamic optimality conjecture）至今未解。在函數式程式設計中，紅黑樹可做成持久化資料結構（persistent data structure）：每次更新只複製從根到修改點的 $O(\log n)$ 路徑，舊版本完整保留，這是版本控制、撤銷／重做與並行無鎖結構的理論基礎。

從 MST 到擬陣（matroid）。 Kruskal 的貪婪正確性並非巧合，而是擬陣理論的特例：MST 對應「圖擬陣」（graphic matroid），其中「不成環的邊集合」恰好構成擬陣的獨立集。擬陣的核心定理保證——貪婪演算法在任何擬陣上都能求得最大權重獨立集。這把 MST、排程、最大權重森林等問題統一在同一個代數結構下，也是組合最佳化中「為什麼貪婪有時對、有時錯」的判準。當問題的可行解結構不滿足擬陣公理時，貪婪就失效，必須改用線性規劃鬆弛或近似演算法。