樹與樹的演算法 — Trees & Tree Algorithms Interactive

CONTENTS · 內容目錄

P00引言：為什麼需要樹？ P01術語與定義 P02Nodes & References P03解析樹 Parse Tree P04樹的走訪 P05二元堆積 P06二元搜尋樹 P07BST 刪除三情境 P08BST 分析 P09AVL 樹與旋轉（補充） REFMap ADT 總覽比較

PROLOGUE · 開場

樹是電腦科學中最普遍的階層式結構

樹（tree）這個資料結構出現在作業系統、編譯器、資料庫、網路路由、機器學習等幾乎每一個領域。不同於我們前面學過的線性結構（list、stack、queue），樹是階層式的：一個節點可以連到多個子節點，整體組成一個由根（root）往下分支的層次。

本章你會學到的技術 1. 抽象結構：樹的術語、Tree ADT、用 nodes & references 實作。
2. 應用：解析樹（parse tree）將數學表達式轉成可遞迴計算的結構。
3. 三種走訪：preorder、inorder、postorder，全部都是遞迴的優雅實作。
4. 兩個經典樹型 ADT：用陣列實作的 Binary Heap（優先佇列）與用節點實作的 Binary Search Tree（map）。
5. 平衡的代價：BST 在最差情況退化為 $O(n)$，AVL 樹用旋轉維持 $O(\log n)$ 上界。

顏色語義（整頁通用）

未處理正在處理 / 比較當前 / 交換已訪問 / 完成父節點找到目標路徑

每一節都採相同的版面：左邊是視覺化畫布與控制列，右邊是即時統計、虛擬碼與複雜度分析。請大膽地按 ▶ 開始觀察完整動畫，或按 → 單步一格一格觀察。

PART 01 · 術語與定義

樹的術語：節點、邊、根、葉、層、高度

在進入演算法之前，我們先把語言對齊。把滑鼠移到下方互動樹的任何一個節點上，右側面板會即時顯示該節點的所有屬性；點擊節點則會高亮它的「祖先路徑（path-to-root）」與「子樹（subtree）」。

點擊不同節點觀察 path-to-root 與 subtree 的差異

節點屬性 LIVE

key—

parent—

children—

siblings—

level—

subtree height—

is leaf?—

關鍵術語

Root：唯一沒有 parent 的節點。
Edge：連接 parent 與 child 的單向連結。
Path：邊串成的節點序列。
Leaf：沒有 children 的節點。
Subtree：某節點與其所有後代。
Level：root 到該節點的邊數。
Height：樹中任何節點的最大 level。

兩個等價的定義 定義一（集合式）：樹是節點集合 $V$ 與邊集合 $E$ 的二元組，滿足：(1) 恰有一個 root，(2) 除 root 外每個節點恰有一個 incoming edge，(3) 從 root 到每個節點存在唯一路徑。
定義二（遞迴式）：樹要嘛是空的；要嘛由一個 root 連接到零或多個 subtree，每個 subtree 本身也是一棵樹。

遞迴定義對寫程式特別友善 —— 它直接告訴你 base case（空樹）和 recursive step（處理 root + 遞迴處理子樹），這也是後面所有走訪、評估、刪除演算法的骨架。

二元樹（Binary Tree）

本章我們專注於每個節點最多有兩個子節點的樹，稱為二元樹。我們特別命名為 left_child 和 right_child，這個順序在解析樹（運算子的左右運算元）和 BST（小的在左、大的在右）中是有語義的。

PART 02 · 樹的實作

Nodes & References：用類別與遞迴結構表示二元樹

實作二元樹有兩種常見方法：list of lists（用巢狀串列）與 nodes and references（用節點物件 + 指標）。後者更貼近物件導向的思維 —— 我們定義一個 BinaryTree 類別，每個物件帶 key、left_child、right_child 三個屬性。當 left_child 不是 None 時，它本身就是另一棵 BinaryTree —— 這就是樹的遞迴結構。

當前指令 CODE

a_tree = BinaryTree("a")
a_tree.insert_left("b")
a_tree.insert_right("c")
a_tree.get_left_child().insert_right("d")
a_tree.get_right_child().insert_left("e")
a_tree.get_right_child().insert_right("f")
        

BinaryTree 類別 CLASS

class BinaryTree:
    def __init__(self, root_obj):
        self.key = root_obj
        self.left_child = None
        self.right_child = None

    def insert_left(self, new_node):
        if self.left_child is None:
            self.left_child = BinaryTree(new_node)
        else:
            new_child = BinaryTree(new_node)
            new_child.left_child = self.left_child
            self.left_child = new_child
        

注意 insert_left 的兩種情況 Case 1（左邊空）：直接把新節點掛上去。
Case 2（左邊已有東西）：新節點插在中間，把原本的左子樹整個推到新節點的左邊一層。這個「往下推」的設計避免了破壞原本的子結構。insert_right 對稱地處理右邊。

PART 03 · 解析樹

解析樹：把數學表達式轉成可遞迴計算的結構

對於完全括號化（fully parenthesized）的表達式，例如 ((7 + 3) * (5 - 2))，我們可以把它變成一棵樹：運算子放在內部節點、運算元放在葉子上。樹的階層自然就反映了運算優先序 —— 評估時只要遞迴地先算左子樹、再算右子樹、最後套用 root 的運算子。

建構演算法用一個 stack 追蹤 parent：當我們往下走進一個 child（看到 ( 或運算子）就把當前節點 push 進 stack；當需要回到 parent（看到 ) 或讀完一個數字）就 pop。

表達式：

速度

即時狀態 LIVE

當前 token—

當前 node—

stack 深度0

評估結果—

parent stack STACK

parent ↓

建構規則 RULES

1. ( → 新增 left child，下移到 left；push parent。
2. + - * / → 設 root 為運算子，新增 right child，下移到 right；push parent。
3. 數字 → 設 root 為數字，pop 回到 parent。
4. ) → pop 回到 parent。

為什麼評估要用 postorder？要計算一個運算子節點的值，必須先有左右兩個子樹的值。這正好符合 postorder（後序）的訪問順序：先左子樹、再右子樹、最後 root。實際上evaluate 函式就是 postorder 走訪 + 在 root 執行運算 —— 解析樹的計算演算法就是走訪演算法的特例。

PART 04 · 樹的走訪

三種走訪：preorder、inorder、postorder

「走訪」（traversal）就是按某種順序拜訪樹中每個節點。對二元樹有三種對稱遞迴的走訪，差別只在「何時拜訪 root」：

三種走訪的定義 Preorder（前序）：root → 左子樹 → 右子樹
Inorder（中序）：左子樹 → root → 右子樹
Postorder（後序）：左子樹 → 右子樹 → root

寫成程式碼幾乎是逐字翻譯定義 —— 這正是樹的遞迴定義帶來的優雅：

輸出將顯示在此 →

速度

虛擬碼 CODE

def preorder(tree):
    if tree:
        print(tree._key, end=" ")
        preorder(tree._left_child)
        preorder(tree._right_child)
        

遞迴呼叫堆疊 STACK

call stack ↓

用途

Preorder：複製樹、序列化、目錄列表（先列父再進子）。
Inorder：BST 上得到排序輸出；解析樹上得到中序表達式。
Postorder：解析樹的表達式評估、刪除整棵樹（先刪 child 才能釋放 parent）。

小實驗：對解析樹 (3+(4*5)) 做三種走訪

Preorder	+ 3 * 4 5	前綴表達式
Inorder	3 + 4 * 5	中序（沒括號會失精度）
Postorder	3 4 5 * +	後綴表達式

這也說明了為什麼後綴表達式（RPN）能用 stack 直接計算：postorder 的順序就是「邊計算邊累積」的最佳順序。

PART 05 · 二元堆積

Binary Heap：用陣列實作的優先佇列

優先佇列（priority queue）的核心需求是：每次 dequeue 都要取出優先序最高的元素。Min-heap 的慣例是「key 越小，優先序越高」，所以 dequeue 會取出最小 key。

如果只用一般 list 來做，有兩種很直覺但不理想的實作。第一種是永遠維持 sorted list：這樣最小值可以很快拿到，但每次 enqueue 新元素時，都必須找到正確位置並搬移後面的元素，最差要 $O(n)$。第二種是維持 unsorted list：插入可以直接 append，成本 $O(1)$，但每次 dequeue 時就必須掃描整個 list 找最小值，成本 $O(n)$；如果每次 dequeue 前乾脆重新 sort，甚至會變成 $O(n\log n)$。問題的本質是：sorted list 讓插入慢，unsorted list 讓取出最高優先序慢。

Binary heap 的設計目標就是折衷這兩件事：不要求整個 list 完全排序，只維持足夠的局部順序，讓 enqueue 與 dequeue 都是 $O(\log n)$，而 get-min 可以是 $O(1)$。

Priority queue 操作如何用 binary heap 實作？ enqueue(x)：把新元素 append 到陣列最後，然後一路和 parent 比較並 perc_up，成本 $O(\log n)$。
dequeue() / delete-min：取出 root，把最後一個元素搬到 root，再 perc_down 修復 heap order，成本 $O(\log n)$。
change-priority(x, newKey)：先找到元素 $x$ 在 heap 陣列中的位置，更新 key；若 priority 變高（min-heap 中 key 變小）就 perc_up，若 priority 變低（key 變大）就 perc_down。若實作時另外維護一張「元素 $\rightarrow$ index」的對照表，找位置是 $O(1)$，每次 swap 同步更新對照表也是 $O(1)$，所以主要成本只剩上浮或下沉，總成本是 $O(\log n)$。若沒有這張 index 對照表，就必須先在陣列中掃描找 $x$，找位置要 $O(n)$，再加上調整 heap 的 $O(\log n)$，總成本由掃描主導，仍是 $O(n)$。

先看編號方式：Level-order traversal (BFS) 要把一棵樹放進陣列，最自然的編號方式是 level-order traversal，也就是 BFS：先拜訪 root，再由左到右拜訪第 1 層，接著由左到右拜訪第 2 層，依此類推。若用 0-based index 編號，root 是 0，下一層從左到右是 1、2，再下一層是 3、4、5、6。

因為 heap 的樹形會保持為 complete binary tree，這種 BFS 編號不會在中間留下空洞；所以我們可以直接用 heap[i] 表示「BFS 編號為 $i$ 的節點」。

堆積的兩個性質 結構性質（structure property）：是一棵 complete binary tree（除最底層外每層填滿，最底層由左到右填）。
順序性質（heap order property）：每個節點的 key $\le$ 其子節點 key（min-heap）；對稱地 max-heap 是 $\ge$。

結構性質讓我們可以用單一陣列儲存整棵樹：節點 $p$ 的左子在 $2p+1$、右子在 $2p+2$、父節點在 $\lfloor (p-1)/2 \rfloor$。完全不需要指標！

為什麼 child / parent index 是這樣？ Heap 使用 0-based index，root 在第 $0$ 層。因為 complete binary tree 的前 $l$ 層節點數是 $$1 + 2 + 4 + \cdots + 2^l = 2^{l+1}-1,$$ 所以第 $l$ 層最後一個節點的 index 是 $$\text{last}(l) = 2^{l+1}-2.$$ 也就是說，last(l) 是第 $l$ 層最右邊節點的位置。

現在從右往左數。假設第 $l$ 層某個 parent 的 index 是 $$p = \text{last}(l) - j,$$ 其中 $j$ 表示它距離該層最右端有幾格。往下一層時，每個 parent 會對應兩個 child；因此它的右小孩會距離第 $l+1$ 層最右端 $2j$ 格： $$\text{right}(p) = \text{last}(l+1) - 2j.$$ 代入 $j=\text{last}(l)-p$： $$\text{right}(p)=\text{last}(l+1)-2(\text{last}(l)-p).$$ 再代入 $\text{last}(l+1)=2^{l+2}-2$ 與 $\text{last}(l)=2^{l+1}-2$： $$\text{right}(p)=(2^{l+2}-2)-2(2^{l+1}-2-p)=2p+2.$$ 左小孩就在右小孩前一格，所以 $$\text{left}(p)=2p+1,\qquad \text{right}(p)=2p+2.$$ 反過來看，若某個 child index 是 $i$，它一定是某個 $2p+1$ 或 $2p+2$。兩種情況都會被整數除法合併成同一條 parent 公式： $$\text{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor=(i-1)//2.$$

陣列表示（heap[i]）：

插入 key：當前 heap：

速度

即時統計 LIVE

交換次數

比較次數

當前索引 i—

parent (i-1)//2—

虛擬碼 CODE

def _perc_up(self, i):
    while (i - 1) // 2 >= 0:
        p = (i - 1) // 2
        if heap[i] < heap[p]:
            swap(heap[i], heap[p])
        i = p
        

複雜度

insert$O(\log n)$

delete-min$O(\log n)$

change-priority$O(\log n)$*

get-min$O(1)$

heapify$O(n)$

*需已知道元素 index，或維護元素到 index 的對照表；否則先找元素會是 $O(n)$。

為什麼 heapify 是 O(n) 而不是 O(n log n)？ Naïve 想法是對 $n$ 個元素逐一 insert，每個 $O(\log n)$，總共 $O(n \log n)$。但 heapify 不是反覆插入；它從最後一個非葉節點 $\lfloor n/2 \rfloor - 1$ 倒著做 perc_down。證明如下：

一個節點往下 perc_down 的成本，最多正比於它的高度 $h$，因為每往下一層只做常數次比較與交換。
在 complete binary tree 中，高度為 $h$ 的節點數最多是 $\left\lceil n/2^{h+1} \right\rceil$。也就是說，靠近底層的節點很多，但高度很小；靠近 root 的節點高度大，但數量很少。
因此總成本可由各高度分組估計： $$ T(n) \le c\sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^{h+1}}\cdot h = cn\sum_{h=0}^{\lfloor \log n \rfloor} \frac{h}{2^{h+1}} \le cn\sum_{h=0}^{\infty} \frac{h}{2^{h+1}} = cn = O(n). $$

直觀上：樹底層節點多但移動少，頂層節點少但移動多，兩者相乘的總和是線性的。所以 Floyd 的 bottom-up heapify 是 $O(n)$。

應用：Heap Sort（堆排序）

有了 heapify（$O(n)$）和 $n$ 次 delete-min（每次 $O(\log n)$），就能寫出 $O(n \log n)$ 的排序：把所有元素丟進 heap，然後不斷 delete-min 拿出來。這是不需要額外 $O(n)$ 空間的就地排序變體（直接在原陣列上做 heap 操作）的核心。

PART 06 · 二元搜尋樹

Binary Search Tree：實作 Map ADT 的第三種方法

Map ADT 把 key 對應到 value（就像 Python 的 dict）。我們已經學過兩種實作：排序陣列 + binary search（搜尋 $O(\log n)$ 但插入 $O(n)$）和雜湊表（平均 $O(1)$ 但有衝突風險、無排序）。BST 提供第三條路：

BST 性質（BST property）對樹中每個節點 $x$：left subtree 內所有 key < $x$.key < right subtree 內所有 key。
這個簡單的性質導致兩個強大結果：
1. 從 root 出發比較 key，每一步可以排除一半的子樹 → 搜尋平均 $O(\log n)$。
2. 對 BST 做 inorder traversal 直接得到排序的 key 序列。

初始 keys：

操作 key：

速度

即時狀態 LIVE

當前操作—

比較次數0

當前 node—

樹高度—

節點數—

結果—

虛擬碼 — _put CODE

def _put(self, key, value, current_node):
    if key < current_node.key:
        if current_node.left_child:
            self._put(key, value, current_node.left_child)
        else:
            current_node.left_child = TreeNode(key, value, parent=current_node)
    else:
        if current_node.right_child:
            self._put(key, value, current_node.right_child)
        else:
            current_node.right_child = TreeNode(key, value, parent=current_node)
        

build BST 的順序很重要把 keys $70, 31, 93, 94, 14, 23, 73$ 依序插入會得到一棵漂亮的「平衡」BST；但若插入順序是 $14, 23, 31, 70, 73, 93, 94$（已排序），新樹會退化成一條鏈 —— 高度從 $O(\log n)$ 變成 $O(n)$。試試上面的「隨機」按鈕和輸入排序的 keys 比較看看。這就是下一節要解決的問題。

PART 07 · BST 刪除三情境

BST 刪除：三種情境，與 in-order successor

BST 的 put 與 get 直觀，但刪除是最麻煩的操作 —— 因為刪掉一個內部節點後，必須維持 BST 性質。我們把情境分成三類：

三種刪除情境 Case 1：要刪的是葉節點。直接把 parent 的指標設為 None。最簡單。
Case 2：要刪的節點只有一個子節點。把這個 child「提升」上來取代被刪節點。
Case 3：要刪的節點有兩個子節點。找它的 in-order successor（中序後繼） —— 也就是右子樹中 key 最小的節點 —— 把它的 key 拷貝到當前節點，然後從原位置「splice out」 successor。

為什麼 successor 一定有最多一個 child？因為它是右子樹中的最左節點 —— 如果它還有左 child，那個 child 一定更小、應該才是 successor。所以 splice out successor 一定是 case 1 或 case 2，可以遞迴處理。

樹結構（依序插入）：

刪除 key：

當前情境 CASE

情境—

target key—

successor—

階段—

find_successor CODE

def find_successor(self):
    if self.right_child:
        return self.right_child.find_min()
    ...
def find_min(self):
    cur = self
    while cur.left_child:
        cur = cur.left_child
    return cur
        

圖例

要刪除的節點
successor
搜尋路徑

PART 08 · BST 分析

BST 的限制：高度決定一切

BST 所有操作（put、get、in、del）的時間複雜度都正比於樹的高度 $h$，而不是節點數 $n$。所以問題變成：給定 $n$ 個節點，$h$ 會是多少？

高度與節點數的關係完美平衡二元樹的意思是：每個節點的 left subtree 和 right subtree 節點數相同（或只差 1），所以每往下一層，剩下要搜尋的子樹大小大約減半。若樹高是 $h$，每層填滿時節點數為 $$1+2+4+\cdots+2^h=2^{h+1}-1.$$ 因此 $n \approx 2^{h+1}$，也就是 $h \approx \log_2 n$。換句話說，put() 不會拜訪整棵樹，而是從 root 開始，每次比較後只往左或往右其中一邊走；在 balanced binary tree 中，最多走約 $\log_2 n$ 層，所以 worst-case performance 是 $O(\log_2 n)$。
若 keys 隨機插入，高度期望也是 $O(\log n)$，因為大概一半 key 進左、一半進右。
但最差情況 $h = n - 1$ —— 把已排序 keys 依序插入就會發生：每個新節點都比當前所有節點大（或小），永遠落到右（或左）這一支，BST 退化成連結串列。

隨機順序插入

              height = —
            

已排序順序插入

              height = —
            

節點數 n：

複雜度對照

操作	平均	最差
put	$O(\log n)$	$O(n)$
get	$O(\log n)$	$O(n)$
del	$O(\log n)$	$O(n)$

應用：Tree Sort

把 $n$ 個 keys 全部 put 進 BST 再做 inorder traversal，平均得到 $O(n \log n)$ 的排序。但最差情況退化為 $O(n^2)$ —— 這也是 quick sort 在最差情況下退化的同一個原因（pivot 選不好等於插入排序好的 keys 進 BST）。

PART 09 · AVL 樹（補充）

AVL Tree（補充）：保證 O(log n) 的自平衡 BST

BST 退化的原因是插入順序。AVL 樹（Adelson-Velsky 和 Landis，1962）讓樹在每次插入/刪除時自動旋轉，保證它一直是「近似平衡」。代價只是常數因子的開銷。

balance factor（平衡因子）對每個節點 $x$，定義 $\text{bf}(x) = \text{height}(x.\text{left}) - \text{height}(x.\text{right})$。
AVL 規則：每個節點的 bf 必須是 $-1$、$0$ 或 $+1$。任何超出這個範圍的節點觸發旋轉來「修正」。
bf $> 0$：left-heavy；bf $< 0$：right-heavy；bf $= 0$：完美平衡。

速度

當前情境 CASE

不平衡類型LL

解法右旋 (Right Rotate)

當前節點 bf—

階段—

四種旋轉

LL（左左不平衡）：對 root 做單一右旋。
RR（右右不平衡）：對 root 做單一左旋。
LR（左右不平衡）：先對 left child 左旋，再對 root 右旋。
RL（右左不平衡）：先對 right child 右旋，再對 root 左旋。

高度上界

AVL HEIGHT BOUND

$h \le 1.44 \log_2 n$

由 Fibonacci 樹（最瘦的 AVL 樹）推導

為什麼是 1.44 log n？最瘦的 AVL 樹（每個節點 bf 都是 $\pm 1$）滿足遞迴 $N_h = 1 + N_{h-1} + N_{h-2}$，這正是 Fibonacci 數列的型式。當 $h$ 很大時 $N_h \approx \Phi^{h+2}/\sqrt 5$（黃金比例 $\Phi = (1+\sqrt 5)/2$）。對兩邊取 $\log_2$ 並解 $h$ 得到： $$ h \approx \frac{1}{\log_2 \Phi} \log_2 n \approx 1.44 \log_2 n $$ 這比完美平衡的 $\log_2 n$ 只大了一個常數因子，所有 BST 操作仍是 $O(\log n)$。

REFERENCE · 總覽比較

Map ADT 四種實作的對照表

過去兩章我們學了四種實作 map ADT 的方式。下表整理 worst-case 複雜度 —— 注意 hash table 的 $O(1)$ 是平均，最差情況（全部碰撞）會退化到 $O(n)$。

operation	Sorted List (binary search)	Hash Table (平均)	BST (最差)	AVL Tree
put(key, val)	$O(n)$	$O(1)$	$O(n)$	$O(\log n)$
get(key)	$O(\log n)$	$O(1)$	$O(n)$	$O(\log n)$
in (key in m)	$O(\log n)$	$O(1)$	$O(n)$	$O(\log n)$
del m[key]	$O(1)$	$O(1)$	$O(n)$	$O(\log n)$
排序輸出 (in-order)	$O(n)$	$O(n \log n)$	$O(n)$	$O(n)$

什麼時候選什麼？ 需要 $O(1)$ 平均、不需要排序：選 hash table（Python dict、Java HashMap）。
需要保證 $O(\log n)$ worst-case、需要排序輸出：選 self-balancing BST（C++ std::map、Java TreeMap 用紅黑樹；AVL 是它的近親）。
資料是 read-only 且已排序：用陣列 + binary search，記憶體緊湊、cache 友善。
需要快速取出最小/最大值（優先佇列）：選 binary heap（Python heapq），不需要完整排序就能 $O(\log n)$ 操作。

樹結構在實際系統中的地位

這一章你學到的概念是現代軟體系統的基石：

檔案系統（樹）：每個目錄一個節點，檔案是葉子。
編譯器與直譯器（解析樹 / AST）：源碼解析成抽象語法樹，遞迴走訪做型別檢查、最佳化、產生機器碼。
資料庫索引（B-tree / B+tree）：BST 的多路推廣，每個節點容納上百個 keys，是磁碟導向的設計。
路由表 / IP lookup（Trie）：另一種樹型結構，依字元逐層走訪。
Heap 在演算法中的核心地位：Dijkstra 最短路徑、Huffman 編碼、$k$ 路合併、top-$k$ 問題全都靠 priority queue。

「看到階層、想到遞迴、寫成樹」—— 這是這一章最值得帶走的思考方式。