樹與圖

從通訊錄到捷運路線圖：兩種「關係」的資料結構

想像你手機裡的通訊錄正在快速膨脹。每次撥號前，你都要從上千筆聯絡人裡找到正確的那一個。如果這些名字只是亂無章法地堆在一起，每次查找都得從頭翻到尾。但如果它們依照姓氏「分層」排序——先看第一個字決定往左或往右，再看下一個字——你只需要比對少數幾次就能命中目標。這種「一層一層分岔、快速縮小範圍」的組織方式，就是樹(tree)。

再換個場景：你打開捷運路線圖，想知道從某站到另一站怎麼搭最快。這裡的關係更複雜——一個站可能連到三、四條路線，路線之間還會交會、繞圈。沒有所謂的「上層」與「下層」，只有「誰跟誰相連」。這種任意連結、可能成環的結構，就是圖(graph)。

樹與圖是資料結構裡描述「關係」的兩大主角。樹強調階層(hierarchy)，圖強調網絡(network)。理解它們，等於拿到了搜尋引擎、社群網路、編譯器、地圖導航背後共通的鑰匙。

樹的基本術語：一座家族的譜系

樹是由節點(node)與邊(edge)構成的階層結構。我們用家族譜系來建立直覺：

• 根(root)：最頂端、沒有父節點的節點，整棵樹的起點。
• 父節點(parent)／子節點(child)：相鄰兩層之間，上方為父、下方為子。
• 葉(leaf)：沒有任何子節點的節點，位於樹的末端。
• 子樹(subtree)：任一節點連同它底下所有後代，自成一棵小樹。
• 深度(depth)：從根到某節點的邊數；根的深度為 0。
• 高度(height)：從某節點到最深葉的邊數；整棵樹的高度即根的高度。

一個關鍵性質：含有 $n$ 個節點的樹恰好有 $n-1$ 條邊，而且任兩節點之間有唯一一條路徑——這正是「無環的連通結構」。少一條邊就會斷開，多一條邊就會成環，也就不再是樹了。

二元樹與二元搜尋樹：分岔的紀律

二元樹(binary tree) 是最常用的一種樹：每個節點最多有兩個子節點，分別稱為左子節點與右子節點。它的形狀變化多端，從只有一條鏈的「退化樹」到左右均衡的「完滿樹」都算。

真正讓二元樹發揮威力的，是替它加上一條排序紀律，成為二元搜尋樹(binary search tree, BST)：

對任一節點，左子樹的所有值都小於它，右子樹的所有值都大於它。

這條看似簡單的不變式(invariant)帶來巨大好處：查找一個值時，每比對一次就能淘汰一整側子樹。若樹是平衡的，含 $n$ 個節點的 BST 高度約為 $\log_2 n$，查找、插入、刪除都只要 $O(\log n)$ 時間。這正是開頭通訊錄那種「每次砍掉一半」的效率來源。

但 BST 有個致命弱點：如果你依序插入 1, 2, 3, 4, 5，它會退化成一條只往右長的鏈，高度變成 $n-1$，所有操作退回 $O(n)$，跟亂堆一通沒兩樣。這個陷阱，正是後面「平衡樹」要解決的核心問題。

動手看一個例子：在 BST 裡查找

假設我們依序插入 50, 30, 70, 20, 40, 60, 80，建出這棵 BST：

            50
          /    \
        30      70
       /  \    /  \
      20  40  60  80

現在要查找 60，過程如下：

步驟 1：從根 50 開始。60 > 50 → 往右走，到 70。
步驟 2：到 70。60 < 70 → 往左走，到 60。
步驟 3：到 60。命中！

只比對 3 次就找到了。對照之下，若 7 個值是一條亂序清單，最壞情況要比對 7 次。樹的層級結構把線性掃描換成了對數級的下降。

樹的走訪：把階層攤平成序列

很多時候我們需要「拜訪」樹中每一個節點——例如印出所有值、計算總和、序列化存檔。把一棵立體的樹轉成一條線性序列的過程，稱為走訪(traversal)。走訪分成兩大家族。

深度優先：前序、中序、後序

深度優先走訪(depth-first traversal, DFS) 沿著一條路徑一直往深處鑽，到底了再回頭。依「處理當前節點」的時機不同，分成三種：

• 前序(preorder)：先處理自己，再走左子樹，最後走右子樹（根→左→右）。
• 中序(inorder)：先走左子樹，再處理自己，最後走右子樹（左→根→右）。
• 後序(postorder)：先走左子樹，再走右子樹，最後處理自己（左→右→根）。

對前面那棵 BST，三種走訪的輸出為：

前序：50 30 20 40 70 60 80
中序：20 30 40 50 60 70 80
後序：20 40 30 60 80 70 50

特別注意中序走訪 BST 會得到由小到大的有序序列——這是 BST 與中序的經典搭配，常用來驗證一棵樹是否為合法 BST。前序常用於複製或序列化整棵樹，後序則用於釋放記憶體或計算子樹彙總（必須先處理完小孩才能處理父親）。

def inorder(node, visit):
    """中序走訪：左 -> 根 -> 右"""
    if node is None:
        return
    inorder(node.left, visit)
    visit(node.value)
    inorder(node.right, visit)

廣度優先：一層一層地看

廣度優先走訪(breadth-first traversal, BFS) 則完全不同——它一層一層地拜訪，先看完深度 0，再看深度 1，依此類推。實作上用一個佇列(queue) 來記住「待訪清單」：

from collections import deque

def bfs(root, visit):
    """層序走訪：用佇列逐層拜訪"""
    if root is None:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        visit(node.value)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

同一棵 BST 的 BFS（層序）輸出為：50 30 70 20 40 60 80。BFS 適合「找最近的目標」——因為它保證先抵達層數較淺的節點。DFS 用堆疊(stack)（遞迴隱含的呼叫堆疊），BFS 用佇列，這個對比之後在圖上會再次出現。

圖：當關係不再有上下之分

樹是圖的特例。圖(graph) $G = (V, E)$ 由一組頂點(vertex) $V$ 與一組邊(edge) $E$ 構成，邊連接頂點。和樹相比，圖更自由：

• 可以有環(cycle)：捷運繞一圈回到原點。
• 可以不連通：兩座孤立的城市鐵路網。
• 邊可以有向(directed)：單行道、社群媒體的「關注」是單向的。
• 邊可以有權重(weighted)：路段的距離、網路的延遲。

要在程式裡表示一張圖，主要有兩種方式。

鄰接矩陣與鄰接串列

鄰接矩陣(adjacency matrix) 用一個 $|V| \times |V|$ 的二維陣列 $A$，其中 $A[i][j]=1$ 表示頂點 $i$ 到 $j$ 有邊（無邊則為 0；帶權圖則存權重）。

鄰接串列(adjacency list) 則為每個頂點維護一份「鄰居清單」，只記錄真正存在的邊。

以下是一張 4 個頂點的無向圖（邊：0-1、0-2、1-2、2-3）的兩種表示：

鄰接矩陣（對稱）              鄰接串列
    0  1  2  3               0 -> [1, 2]
0 [ 0  1  1  0 ]             1 -> [0, 2]
1 [ 1  0  1  0 ]             2 -> [0, 1, 3]
2 [ 1  1  0  1 ]             3 -> [2]
3 [ 0  0  1  0 ]

兩者各有取捨，整理如下表（$V$ 為頂點數、$E$ 為邊數）：

現實世界的圖（社群網路、道路網）通常是稀疏的——頂點很多，但每個頂點的鄰居有限。因此鄰接串列是更常見的選擇；只有當圖很稠密、或需要頻繁查詢任兩點是否相連時，鄰接矩陣才划算。

圖的走訪與其複雜度

樹的 DFS/BFS 直接搬到圖上，但圖會成環，所以必須多帶一個 visited 標記避免重複拜訪、陷入無窮迴圈——這是樹走訪不需要、圖走訪不可省的關鍵差異。

def graph_dfs(graph, start):
    """圖的深度優先走訪，用 visited 避免重複拜訪"""
    visited = set()
    def explore(u):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                explore(v)
    explore(start)
    return visited

圖走訪的複雜度值得仔細推敲，因為它取決於圖的表示方式。以鄰接串列為例，BFS 與 DFS 都會：(1) 把每個頂點放進佇列／堆疊恰好一次，貢獻 $O(V)$；(2) 對每個頂點，掃過它的鄰接串列恰好一次，所有頂點的鄰居數總和等於邊數的兩倍（無向圖）或邊數（有向圖），貢獻 $O(E)$。兩者相加：

$$ T_{\text{BFS}} = T_{\text{DFS}} = O(V + E) $$

這個 $O(V+E)$ 是圖演算法的黃金基準——它代表「每個頂點與每條邊都只碰一次」的最佳線性掃描。

但若改用鄰接矩陣，要找出某頂點的鄰居，必須掃過整列 $V$ 個格子（即使大多是 0）。對每個頂點都這樣做，總成本變成：

$$ T_{\text{matrix}} = O(V^2) $$

對稀疏圖（$E \ll V^2$）來說，這是顯著的浪費。這正是「資料結構選擇直接決定演算法複雜度」的最佳教材：同一個 BFS，搭配鄰接串列是 $O(V+E)$，搭配鄰接矩陣卻是 $O(V^2)$。

重點回顧

• 樹是無環、有階層的連通結構，$n$ 個節點恰有 $n-1$ 條邊，任兩點間路徑唯一；圖則允許環、多重連結、有向與權重，是更一般化的關係模型，樹是圖的特例。
• 二元搜尋樹(BST) 靠「左小右大」的不變式達到平均 $O(\log n)$ 的查找，但依序插入會退化成 $O(n)$ 的鏈——這是平衡樹要解決的問題。
• 樹走訪分深度優先（前序、中序、後序，用堆疊）與廣度優先（層序，用佇列）；其中中序走訪 BST 會輸出有序序列。
• 圖有鄰接矩陣（$O(V^2)$ 空間，查邊 $O(1)$，適合稠密圖）與鄰接串列（$O(V+E)$ 空間，適合稀疏圖）兩種表示。
• 圖走訪須以 visited 防止重複；搭配鄰接串列時 BFS／DFS 皆為 $O(V+E)$，搭配鄰接矩陣則退化為 $O(V^2)$。

深入探討（研究所視角）

平衡樹：把「最壞情況」工程化

前面提過 BST 依序插入會退化成鏈。研究所層級關注的是：如何保證樹永遠保持 $O(\log n)$ 高度，無論插入順序如何？答案是自平衡二元搜尋樹(self-balancing BST)，核心機制是旋轉(rotation)——一組 $O(1)$ 的局部指標重接操作，能在不破壞 BST 排序性質的前提下調整子樹高度。

• AVL 樹維持「任一節點左右子樹高度差不超過 1」的嚴格不變式，查找最快，但插入／刪除可能觸發較多旋轉。
• 紅黑樹(red-black tree) 放寬條件，只保證最長路徑不超過最短路徑的兩倍（高度上界 $2\log_2(n+1)$），插刪的旋轉攤還(amortized)成本更低，因此被 C++ std::map、Java TreeMap、Linux 排程器廣泛採用。
• 把分支度推廣到大於 2，就得到 B 樹／B+ 樹——這是資料庫索引與檔案系統的基石。當資料存在磁碟上，每次 I/O 讀取一個區塊(block)是昂貴瓶頸，B+ 樹用「高分支、矮高度」把磁碟存取次數壓到最低，這是「快取／記憶體階層感知(cache-aware)」資料結構設計的經典範例。

值得思考的一點：平衡樹的價值不在「更快的平均效能」，而在消除最壞情況的不確定性。在即時系統、資料庫、作業系統核心這些不能容忍偶發 $O(n)$ 卡頓的場景，可預測的 $O(\log n)$ 上界本身就是一種工程資產。

圖走訪複雜度的延伸與下界

$O(V+E)$ 不只是 BFS／DFS 的成本，更是許多圖演算法的「結構性下界」——因為要正確回答任何關於連通性的問題，至少得把每條相關的邊看過一次。理解這點，能把眾多看似不同的演算法串成一張地圖：

• 加權最短路徑不能只靠 BFS（BFS 只在邊權皆相等時才正確）。Dijkstra 演算法在 BFS 骨架上換用優先佇列(priority queue)選取最近頂點，以二元堆積實作為 $O((V+E)\log V)$，以斐波那契堆積(Fibonacci heap)可優化至 $O(E + V\log V)$。
• 拓樸排序(topological sort) 與強連通元件(strongly connected components) 都建構在 DFS 的 $O(V+E)$ 之上，前者解決有向無環圖(DAG)的依賴排序（如編譯建置順序、課程先修），後者（Tarjan／Kosaraju 演算法）找出有向圖中互相可達的頂點群。
• 連通性與環偵測：無向圖用聯集尋找(union-find)或 DFS，有向圖的環偵測則靠 DFS 過程中的「灰色節點」回邊判定——這也是死結偵測(deadlock detection)的理論基礎。

最後一個值得內化的視角：樹與圖的界線是流動的。一棵生成樹(spanning tree)是從圖中抽取的、保留全部頂點而無環的子圖；最小生成樹(minimum spanning tree, 由 Kruskal 或 Prim 演算法求得)在網路設計、叢集分析中無所不在。當你能自如地在「階層」與「網絡」兩種視角間切換，許多分屬不同課程的演算法，其實都是同一組基本操作（走訪、排序、貪婪選擇）在不同結構上的投影。