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

CONTENTS · 內容目錄

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

PROLOGUE · 開場

樹是電腦科學中最普遍的階層式結構 cppds §8.1–8.2

樹（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 · 術語與定義

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

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

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

PART 02 · 樹的實作

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

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

先看另一種表示：List of Lists 講義補充（課堂跳過）

巢狀串列版把「根的值」放在第 0 格、左子樹放第 1 格、右子樹放第 2 格；每個子樹自己又是同樣格式的串列，結構本身就是遞迴的。葉節點就是「值＋兩個空串列」。它還有個好處：要表示多元樹（超過兩個子樹），再多掛一個串列就好。

巢狀串列表示 CODE

my_tree = ["a",                        // [0] 根的值
    ["b", ["d",[],[]], ["e",[],[]]],  // [1] 左子樹
    ["c", ["f",[],[]], []        ]]   // [2] 右子樹
 
my_tree[0]  // "a"：根
my_tree[1]  // 整個左子樹（又是一個同構的串列）
my_tree[2]  // 整個右子樹

C++ 是靜態型別語言，寫不出這種「值和串列混住」的巢狀字面值，所以我們直接採用下面的 nodes and references 表示法（對 C++ 來說本來就更自然）。課堂投影片跳過這一小節（RISE skip），列為自學補充。

當前指令 CODE

BinaryTree *aTree = new BinaryTree("a")
aTree->insertLeft("b")
aTree->insertRight("c")
aTree->getLeftChild()->insertRight("d")
aTree->getRightChild()->insertLeft("e")
aTree->getRightChild()->insertRight("f")

BinaryTree 類別 CLASS

class BinaryTree {
  public:
    string key;
    BinaryTree *leftChild, *rightChild;
    BinaryTree(string rootObj)
      : key(rootObj), leftChild(NULL), rightChild(NULL) {}
 
    void insertLeft(string newNode) {
        BinaryTree *t = new BinaryTree(newNode);
        if (leftChild != NULL)
            t->leftChild = leftChild;   // 舊子樹下推
        leftChild = t;
    }
};

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

PART 03 · 解析樹

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

對於完全括號化（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 cppds §8.6

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

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

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

輸出將顯示在此 →

速度

虛擬碼 CODE

preorder(tree):
    if tree != NULL:
        visit(tree->key)   // root
        preorder(tree->left)
        preorder(tree->right)

遞迴呼叫堆疊 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：用陣列實作的優先佇列 cppds §8.7–8.10

優先佇列（priority queue）每次都要 dequeue優先序最高的元素。用 list 的天真實作有兩條路，但都不夠好：維持已排序的 list，插入需搬移 $O(n)$；不排序、每次找最小再 sort，sort 是 $O(n \log n)$。Binary heap 把 enqueue 和 dequeue 都壓到 $O(\log n)$。它有兩個關鍵性質：

堆積的兩個性質 結構性質（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$。完全不需要指標！

陣列表示（heap[i]）：

插入 key：當前 heap：

速度

即時統計 LIVE

交換次數

比較次數

當前索引 i—

parent (i-1)//2—

虛擬碼 CODE

percUp(i):
    while i > 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)$

get-min$O(1)$

heapify$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：底層大量節點高度只有 0 或 1，往下移的成本很小。嚴謹分析會用 $\sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot h = O(n)$。直觀上：樹底層節點多但移動少，頂層節點少但移動多，兩者相乘的總和是 $O(n)$。

完整的 BinaryHeap 類別（cppds §8.9–8.10）

動畫側欄只放了 percUp 的骨架；講義的完整類別把六個方法全部攤開。整個類別只有一個成員 vector<int> heap：樹形是用索引「算」出來的（左子 2i+1、右子 2i+2、父 (i-1)/2），從頭到尾不需要指標。

percUp ＋ insert：新元素往上浮 CODE

void percUp(int i) {
    while (i > 0) {
        int parentIdx = (i - 1) / 2;
        if (heap[i] < heap[parentIdx])
            swap(heap[i], heap[parentIdx]);
        else break;   // 不再比父小就停
        i = parentIdx;
    }
}
void insert(int item) {
    heap.push_back(item);      // 先掛最尾（保結構性質）
    percUp(heap.size() - 1);  // 再浮上去（修順序性質）
}

getMinChild ＋ percDown：往下沉 CODE

int getMinChild(int i) {
    if (2*i + 2 > (int)heap.size() - 1)
        return 2*i + 1;   // 只有左子
    if (heap[2*i+1] < heap[2*i+2])
        return 2*i + 1;
    return 2*i + 2;
}
void percDown(int i) {
    while (2*i + 1 < (int)heap.size()) {
        int smChild = getMinChild(i);
        if (heap[i] > heap[smChild])
            swap(heap[i], heap[smChild]);
        else break;
        i = smChild;   // 跟較小的子交換後繼續沉
    }
}

delet ＋ heapify：取最小、批次建堆 CODE

int delet() {                // 取出最小值
    swap(heap[0], heap[heap.size() - 1]);
    int result = heap.back();
    heap.pop_back();
    percDown(0);             // 新根往下沉
    return result;
}
void heapify(vector<int> notAHeap) {
    heap = notAHeap;
    int i = heap.size() / 2 - 1;  // 最後一個非葉
    while (i >= 0) {
        percDown(i);
        i = i - 1;   // 倒著做，正是 O(n) 的關鍵
    }
}

講義的 demo 依序 insert {10, 4, 9, 8, 12, 15, 3, 5, 14, 18}：不管插入順序怎麼亂，heap[0] 永遠是目前最小值， delet() 也總是取出最小者。名字用 delet 是因為 delete 在 C++ 是保留字。

應用：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 的第三種方法 cppds §8.11–8.13

Map ADT 把 key 對應到 value（就像 `C++` 的 unordered_map）。我們已經學過兩種實作：排序陣列 + 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

put(key, val, cur):
    if key < cur->key:
        if cur->left != NULL:
            put(key, val, cur->left)
        else:
            cur->left = new TreeNode(key, val)
    else:
        if cur->right != NULL:
            put(key, val, cur->right)
        else:
            cur->right = new TreeNode(key, val)

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 cppds §8.13

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

三種刪除情境 Case 1：要刪的是葉節點。直接把 parent 的指標設為 NULL。最簡單。
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—

階段—

findSuccessor CODE

findSuccessor():
    if rightChild != NULL:
        return rightChild->findMin()
    ...
findMin():
    cur = this
    while cur->leftChild != NULL:
        cur = cur->leftChild
    return cur

圖例

要刪除的節點
successor
搜尋路徑

講義的完整拼圖：findSuccessor 三情境與 spliceOut

側欄的 findSuccessor 是刪除專用的精簡版（刪除時節點必有右子樹，successor 就是右子樹的最小值）。講義的完整版其實處理三種情境，另外兩種在中序走訪相關的練習會用到。 successor 找到之後，用 spliceOut() 把它從原位置「縫」出來： successor 保證最多一個 child，所以只有兩種縫法。

findSuccessor 完整版（TreeNode 的方法） CODE

TreeNode* findSuccessor() {
    TreeNode* successor = NULL;
    if (rightChild != NULL) {          // 情境 1：有右子樹
        successor = rightChild->findMin();
    } else if (parent != NULL) {
        if (isLeftChild()) {           // 情境 2：自己是左子 → 父就是後繼
            successor = parent;
        } else {                       // 情境 3：暫時斷開自己，問父親
            parent->rightChild = NULL;
            successor = parent->findSuccessor();
            parent->rightChild = this;
        }
    }
    return successor;
}

刪除只會用到情境 1：Case 3 的節點一定有右子樹。

spliceOut ＋ Case 3 呼叫端 CODE

void spliceOut() {
    if (isLeaf()) {                    // 縫法 1：葉節點直接拆
        if (isLeftChild()) parent->leftChild = NULL;
        else               parent->rightChild = NULL;
    } else if (hasAnyChild()) {        // 縫法 2：孩子上位
        TreeNode* child = (leftChild != NULL) ? leftChild : rightChild;
        if (isLeftChild()) parent->leftChild = child;
        else               parent->rightChild = child;
        child->parent = parent;
    }
}
 
// remove 的 Case 3 分支長這樣：
TreeNode* successor = currentNode->findSuccessor();
successor->spliceOut();
currentNode->key   = successor->key;   // 只搬 key/value
currentNode->value = successor->value; // 節點本身不動
delete successor;

PART 08 · BST 分析

BST 的限制：高度決定一切 cppds §8.14

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

高度與節點數的關係完美平衡二元樹（每層填滿）有 $2^{h+1}-1$ 個節點，所以 $h \approx \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 cppds §8.15–8.17

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)$。

實作內幕：updateBalance、rotateLeft、rebalance cppds §8.16–8.17 · 講義補充

課堂投影片跳過 §8.16（AVL 效能）與 §8.17（AVL 實作）這兩節（RISE skip，講義標 Optional）：屬自學補充。

AVL 的 _put 跟 BST 幾乎一樣，唯一差別是掛上新節點後多呼叫一次 updateBalance()：它沿著 parent 指標往上修正平衡因子，一發現 |bf| > 1 就地 rebalance()。旋轉最多兩次、每次 O(1)，往上修正最多走 log n 層，所以 put 整體仍是 O(log n)。上面的動畫可以對照著看：四個按鈕（LL/RR/LR/RL）正是 rebalance 的四個分支。刪除後的重平衡，講義留作練習。

_put 的差異＋ updateBalance CODE

// _put 掛上新葉之後，多做一件事：
currentNode->leftChild =
    new AVLTreeNode(key, value, 0, currentNode);
updateBalance(currentNode->leftChild);
 
void updateBalance(AVLTreeNode* node) {
    if (node->balanceFactor > 1 ||
        node->balanceFactor < -1) {
        rebalance(node);   // 就地修，不再往上
        return;
    }
    if (node->parent != NULL) {
        if (node->isLeftChild())
            node->parent->balanceFactor += 1;
        else if (node->isRightChild())
            node->parent->balanceFactor -= 1;
        if (node->parent->balanceFactor != 0)
            updateBalance(node->parent);  // 繼續往上
    }
}

rotateLeft（rotateRight 對稱） CODE

void rotateLeft(AVLTreeNode* rotationRoot) {
    AVLTreeNode* newRoot = rotationRoot->rightChild;
    rotationRoot->rightChild = newRoot->leftChild;
    if (newRoot->leftChild != NULL)
        newRoot->leftChild->parent = rotationRoot;
    newRoot->parent = rotationRoot->parent;
    if (rotationRoot->isRoot())
        root = newRoot;
    else if (rotationRoot->isLeftChild())
        rotationRoot->parent->leftChild = newRoot;
    else
        rotationRoot->parent->rightChild = newRoot;
    newRoot->leftChild = rotationRoot;
    rotationRoot->parent = newRoot;
    rotationRoot->balanceFactor = rotationRoot->balanceFactor
        + 1 - min(newRoot->balanceFactor, 0);
    newRoot->balanceFactor = newRoot->balanceFactor
        + 1 + max(rotationRoot->balanceFactor, 0);
}

難點有二：parent 指標要全部接對；最後兩行用 min/max 直接推出新的平衡因子，不用重算高度。

rebalance：四情境對照動畫按鈕 CODE

void rebalance(AVLTreeNode* node) {
    if (node->balanceFactor < 0) {          // right-heavy
        if (node->rightChild->balanceFactor > 0) {
            rotateRight(node->rightChild);   // RL：先右旋子
            rotateLeft(node);                //     再左旋根
        } else {
            rotateLeft(node);                // RR：單一左旋
        }
    } else if (node->balanceFactor > 0) {   // left-heavy
        if (node->leftChild->balanceFactor < 0) {
            rotateLeft(node->leftChild);     // LR：先左旋子
            rotateRight(node);               //     再右旋根
        } else {
            rotateRight(node);               // LL：單一右旋
        }
    }
}

先看「歪向哪邊」，再看「子節點歪向哪邊」決定要不要先轉子節點：跟上面動畫的四個 preset 一一對應。

REFERENCE · 總覽比較

Map ADT 四種實作的對照表 cppds §8.18

過去兩章我們學了四種實作 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（C++ unordered_map、Java HashMap）。
需要保證 $O(\log n)$ worst-case、需要排序輸出：選 self-balancing BST（C++ std::map、Java TreeMap 用紅黑樹；AVL 是它的近親）。
資料是 read-only 且已排序：用陣列 + binary search，記憶體緊湊、cache 友善。
需要快速取出最小/最大值（優先佇列）：選 binary heap（C++ priority_queue），不需要完整排序就能 $O(\log n)$ 操作。

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

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

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

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