Trees、BST 與 Heaps：形狀約束與順序規則
本頁為依教材與考古題整理的原創摘要；考古題答案經技術覆核，但不是官方答案。
第一次接觸也沒關係
這堂先懂這些詞
先記住白話意思，不必急著背英文。看到正文時，再把正式名稱接回來。
大 O 複雜度
也會看到：Big O、time complexity、O(n)、時間複雜度描述輸入變大時，演算法所需時間或空間的成長速度。
- 生活例子：
- 排 10 人與排 1 萬人時，工作量增加多快比小規模快幾秒更重要。
- 別搞混：
- Big O 不是精確秒數，也不能忽略資料規模與常數成本。
二元搜尋樹
也會看到：BST、Binary Search Tree、二叉搜尋樹每個節點左側較小、右側較大的樹狀結構。
- 生活例子：
- 像按姓氏順序分流：較前往左、較後往右。
- 別搞混：
- BST 不一定平衡；歪斜時搜尋可能退化成線性時間。
完全二元樹
也會看到：complete binary tree、array representation除最後一層外都填滿，最後一層從左到右連續填入的二元樹。
- 生活例子：
- 像電影院座位逐排、每排由左到右坐滿，最後一排可以未滿。
- 別搞混：
- Complete 不等於每個節點都有零或兩個孩子；那是 full binary tree 的概念。
堆積資料結構
也會看到：heap、binary heap、priority queue、優先佇列維持父節點比子節點更大或更小，方便快速取出最高優先項目。
- 生活例子：
- 急診先處理最危急病患，而不是最早到的人。
- 別搞混：
- heap 只保證父子順序，不代表整棵樹已完整排序。
樹的節點與走訪
也會看到：root、parent、child、leaf、inorder traversal、height用根、父子、葉節點與高度描述樹，並依指定順序拜訪所有節點。
- 生活例子：
- 像家族樹從祖先根節點往下分支，走訪則是規定查看每位成員的次序。
- 別搞混：
- 樹的 height 與節點的 depth 方向不同，且走訪順序不一定產生排序結果。
先建立 tree、complete binary tree 與 array representation，再比較 BST 的全域搜尋順序和 heap 的局部 parent-child 順序，最後推導 traversal、priority queue、insert 與 arbitrary search 的複雜度。對應考古題答案均為非官方技術覆核。
先抓住這幾件事
- 使用 root、parent、child、leaf、depth、height 與 complete binary tree 描述樹。
- 依 BST ordering 推導 inorder traversal 的排序結果。
- 區分 min/max heap property 與 BST property，並以 array index 找 parent/children。
- 分析 binary heap 的 insert、extract-priority 與 arbitrary search 成本。
先想像這個場景
醫院資訊台的兩套名單
醫院同時維護兩種看似都是『樹』的名單：病歷索引用姓名大小關係決定往左或往右找；急診候診表則只要求最高優先者在最前面，方便下一位立即取出。外形相似不代表規則相同——能不能排除一整側、能不能快速找任意名字，取決於名單維持的是 BST 全域順序，還是 heap 的局部 parent-child 順序。
先別急著往下看，花十秒想一想：
Min-heap 的 root 是最小值。現在要找一個很大的指定號碼，和 root 比較後能否像 BST 一樣只搜尋其中一個 child subtree？
把故事換成電腦語言
| 生活中的角色 | 對應到 | 技術概念 |
|---|---|---|
| 院區、部門與服務站以一對多的上下層關係畫成組織圖 | Tree 的 root、parent、child、leaf、depth、height | |
| 急診候診位置逐層由左到右填滿，並依序編入緊密 array | Complete binary tree 與 array mapping | |
| 病歷索引每到一個名字，就依比較結果只往左側較小區或右側較大區 | BST ordering、search 與 inorder traversal | |
| 急診表只保證每位 parent 的優先序不低於 children，最急者放在 root | Max-heap 與 priority queue | |
| 新病人先放下一個空位，再沿 parent chain 上調；取走 root 後用最後一人補位並向下調整 | Heap insert、extract 與 sift |
題目出現這些字，先想到
- 看到 complete binary tree 的 array index：Zero-based：parent=floor((i-1)/2)，left=2i+1，right=2i+2；root 沒有 parent。
- 題目問 BST inorder 或搜尋成本：Distinct-key inorder 產生遞增序列；平衡時 O(log n)，偏斜 worst case O(n)。
- 題目寫 min-heap／max-heap 不等號：Min：parent≤children；max：parent≥children。只保證局部順序。
- 題目問 heap insert、peek 或 arbitrary search：Insert/extract O(log n)，peek root O(1)，找任意 key worst case O(n)。
1.Tree 形狀與 array mapping
Tree（樹）是一種階層式的資料結構，由 node（節點）和 edge（邊）組成。每棵樹有一個 root（根節點），每個 node 最多有一個 parent（父節點），可以有零到多個 children（子節點）。沒有 children 的 node 叫做 leaf（葉節點）。 【關鍵術語】 • Depth（深度）：從 root 到某 node 的路徑長度。Root 的 depth 是 0。 • Height（高度）：從某 node 到最遠 leaf 的路徑長度。Leaf 的 height 是 0。樹的 height = root 的 height。 • Binary tree：每個 node 最多有 2 個 children（left child 和 right child）。 • Complete binary tree：除了最後一層外都填滿，最後一層的 nodes 靠左排列。 • Full binary tree：每個 node 要嘛有 0 個 children，要嘛有 2 個 children。 【Array 表示法】Complete binary tree 可以用陣列高效儲存。將 root 放在 index 1（或 0），則對於 index i 的 node： • 若 root 在 index 1：left child = 2i，right child = 2i+1，parent = i/2（取整數） • 若 root 在 index 0：left child = 2i+1，right child = 2i+2，parent = (i-1)/2 這個對應關係不需要 pointer，省記憶體且 cache-friendly。但只適用於 complete binary tree — 如果樹不是 complete 的，會浪費很多空間（sparse array）。 【考試連結】(1) 給定陣列求對應的樹形狀，或反過來。(2) n 個 node 的 complete binary tree 的 height 是 ⌊log₂ n⌋。(3) 分辨 complete、full、perfect binary tree — perfect 是每個非 leaf node 都有 2 個 children 且所有 leaf 在同一層。
- Root 沒有 parent，leaf 沒有 children。
- Depth 是 root 到節點的邊數；height 是節點到最深 leaf 的最長邊數，使用前要確認課本 convention。
- Complete 不等於 full：complete 強調逐層、由左到右填入。
- Array mapping 很適合 complete tree；任意稀疏 binary tree 可能浪費大量空間。
2.BST 的全域 ordering 與 traversal
Binary Search Tree（BST）是一種特殊的 binary tree，滿足 BST property：對於任何 node，左子樹的所有 node 值都小於該 node，右子樹的所有 node 值都大於該 node。注意是「所有」不是「直接 children」— 這是全域（global）的排序約束。 【基本操作與複雜度】 • Search：從 root 開始，比較目標值和當前 node。小於 → 往左走，大於 → 往右走。Average case O(log n)，worst case O(n)（退化成鏈表）。 • Insert：按 search 路徑找到正確位置，新增 leaf。 • Delete：三種情況：(1) 刪除 leaf → 直接移除。(2) 刪除只有一個 child 的 node → child 替代。(3) 刪除有兩個 children 的 node → 用 in-order successor（右子樹最小值）或 in-order predecessor（左子樹最大值）替代。 【四種 traversal】 • In-order（中序）：左 → root → 右。在 BST 上會產生升序排列。 • Pre-order（前序）：root → 左 → 右。可用來序列化/重建 BST。 • Post-order（後序）：左 → 右 → root。常用於刪除樹或計算子樹大小。 • Level-order（層序）：逐層由左到右，使用 queue 實作。 【具體範例】BST [8, 3, 10, 1, 6, 14]，root=8。In-order traversal 結果：1, 3, 6, 8, 10, 14（升序）。 【考試連結】最常考的題型：(1) 依序插入元素畫出 BST。(2) 對 BST 執行 in-order traversal 寫出結果。(3) 刪除某 node 後的 BST 形狀。陷阱：BST 的形狀取決於插入順序 — 同一組元素用不同順序插入會得到不同的 BST。
- Inorder：left → node → right；preorder：node → left → right；postorder：left → right → node。
- 平衡 BST 的 search/insert 可為 O(log n)；嚴重偏斜時 worst case 可到 O(n)。
- BST 不是 complete binary tree 的同義詞，形狀由插入順序與平衡策略決定。
- Traversal 的 O(n) 表示每個節點通常恰好處理一次。
3.Heap 只保證 parent-child 順序
Heap（堆積）是一種 complete binary tree，滿足 heap property： • Max-heap：每個 node 的值 ≥ 其 children 的值。Root 是最大值。 • Min-heap：每個 node 的值 ≤ 其 children 的值。Root 是最小值。 【Heap vs BST 的核心差異】BST 保證全域排序（左子樹 < root < 右子樹），所以 in-order traversal 能得到排序結果。Heap 只保證 parent-child 之間的順序，不保證左右子樹之間的大小關係。例如在 max-heap 中，root 的 left child 可能比 right child 大，也可能比 right child 小 — 只要兩者都 ≤ root 即可。 因此，Heap 不能做高效的「搜尋特定值」（需要 O(n)），但能在 O(1) 取得最大/最小值（root），適合實作 priority queue。 【Heap 的陣列實作】因為 Heap 是 complete binary tree，用陣列表示非常高效。Max-heap [16, 14, 10, 8, 7, 9, 3]： • Index 0: 16（root，最大值） • Index 1: 14, Index 2: 10（16 的 children） • Index 3: 8, Index 4: 7（14 的 children） • Index 5: 9, Index 6: 3（10 的 children） 【考試連結】最常考的陷阱：(1) 以為 Heap 有排序功能 — Heap 只保證 root 是最大/最小，不保證整體排序。(2) 以為 Heap 的 in-order traversal 能得到排序結果 — 那是 BST 的特性。(3) B-tree 和 Heap 是完全不同的東西 — B-tree 是多路搜尋樹（用於資料庫索引），Heap 是 priority queue 的實作。
- Min-heap：parent ≤ children；max-heap：parent ≥ children。
- Heap 的 siblings 與不同 branches 之間沒有完整排序。
- Array 最後位置對應 complete tree 下一個可插入位置。
- Priority queue 是 ADT；binary heap 是常見 implementation。
4.Sift 操作與複雜度
Heap 的兩個核心操作都透過 sift（篩選/滲透）來維護 heap property： 【Insert（插入）→ Sift-up】新元素先放在陣列末尾（complete binary tree 的最後位置），然後和 parent 比較：如果違反 heap property（例如在 max-heap 中新元素 > parent），就和 parent 交換。重複此過程直到到達 root 或不再違反。最多交換 O(log n) 次（樹的高度）。 【Extract-max/min（取出最值）→ Sift-down】取出 root（最大/最小值），用陣列最後一個元素替換 root，然後從 root 往下和 children 比較：在 max-heap 中，如果 root 比某個 child 小，就和較大的 child 交換。重複此過程直到到達 leaf 或不再違反。最多交換 O(log n) 次。 【Build Heap】把一個無序陣列轉成 heap。天真做法：逐一 insert，O(n log n)。高效做法（Floyd's algorithm）：從最後一個非 leaf node（index n/2 - 1）開始，對每個 node 做 sift-down。看似每個 node 都做 O(log n) 的 sift-down，但實際上大部分 node 離 leaf 很近，總複雜度是 O(n)，不是 O(n log n)。 【Heap Sort】步驟：(1) Build max-heap，O(n)。(2) 反覆 extract-max（把 root 和最後一個元素交換，heap size 減 1，sift-down），重複 n-1 次。總計 O(n log n)。Heap Sort 的優點是 worst case 也是 O(n log n)，且 in-place（O(1) 額外空間）。缺點是不穩定。 【Priority Queue】Heap 最常見的應用是實作 priority queue — 支援 insert（加入元素）和 extract-max/min（取出最高優先級元素），兩者都是 O(log n)。應用場景：OS 的 CPU 排程、Dijkstra 演算法、事件驅動模擬。 【考試連結】(1) 手動執行 insert 或 extract-max 過程。(2) Build Heap 的時間複雜度是 O(n) 不是 O(n log n)。(3) Heap Sort 和 Merge Sort 都是 O(n log n) worst case，但 Heap Sort 是 in-place。
- Insert 與 extract-min/max 的 O(log n) 來自 complete binary tree height。
- Peek root 不修改結構，可在 O(1) 完成。
- Arbitrary search worst case O(n)，不是看到 tree 就一律 O(log n)。
- Increase-key 在 max-heap 通常 sift-up；decrease-key 在 min-heap 通常也 sift-up。
一起拆題目
範例 1：依序把 distinct keys 8、3、10、1、6 插入空 BST。請寫出 inorder traversal。
- 8 成為 root；3 放左側；10 放右側。
- 1 小於 8 且小於 3，成為 3 的 left child。
- 6 小於 8 但大於 3，成為 3 的 right child。
- Inorder 依 left subtree、node、right subtree 走訪。
所以答案是：Inorder 是 1、3、6、8、10，與 distinct keys 的遞增排序相同。
範例 2：Complete binary tree 以 zero-based array [90,70,60,40,50] 表示。Index 1 的 parent、left child、right child indices 與值為何？
- Parent index=floor((1-1)/2)=0，值為 90。
- Left child index=2×1+1=3，值為 40。
- Right child index=2×1+2=4，值為 50。
所以答案是：Parent 是 index 0/value 90；left 是 index 3/value 40；right 是 index 4/value 50。
範例 3：Max-heap array 為 [90,70,60,40,50]，插入 80。請追蹤 sift-up。
- 先把 80 放在末端 index 5，維持 complete shape。
- Index 5 的 parent index 是 floor((5-1)/2)=2，parent value=60。
- 80>60，交換兩者，array 變成 [90,70,80,40,50,60]。
- 80 的新 parent 是 90，因 80≤90，停止。
所以答案是：插入後 max-heap 為 [90,70,80,40,50,60]；sift-up 移動一層，worst case 最多 O(log n) 層。
範例 4：Min-heap 只保證 parent≤children。要確認一個很大的 target 是否存在，為何 worst case 不能像 BST 一樣只走一條 root-to-leaf path？
- 在 BST 中，target 與目前 key 的比較可選擇唯一的左或右搜尋方向。
- 在 min-heap 中，若 target 大於目前 key，target 仍可能出現在任一 child subtree。
- 不同 branches 沒有彼此排序，不能只因 target 較大就排除其中一側。
- 若 target 不存在且大於多數 keys，最壞情況可能檢查所有 n 個節點。
所以答案是：Heap order 只提供局部 parent-child 關係，無法決定唯一搜尋方向；arbitrary search worst case 是 O(n)。
這裡最容易選錯
- 把 binary tree、complete binary tree、BST 與 heap 視為同義詞。
- 看到 tree 就假設所有操作 O(log n)，忽略樹高與 ordering property。
- 把 min-heap 寫成 parent≥children；正確是 parent≤children。
- 認為 heap 的 inorder traversal 也會排序；只有 BST ordering 支援這個結論。
- 把 priority queue 當成某一種固定樹；它是 ADT，可有多種 implementations。
- 用 BST 搜尋邏輯尋找 heap 中的 arbitrary key，錯誤地宣稱 O(log n)。
換你快速判斷
先在心中作答，再展開答案。答不出來時，回頭找本課的對照關係。
1為何 distinct-key BST 的 inorder traversal 會產生遞增順序？
Inorder 依 left subtree、node、right subtree；BST 又保證左側 keys 較小、右側 keys 較大。
結論依賴 BST ordering，不適用於任意 binary tree 或 heap。
2BST 與 binary heap 最核心的 ordering 差異是什麼？
BST 提供左右子樹的全域搜尋順序；heap 只保證每個 parent 與 children 的局部優先順序。
因此 BST 可依比較選擇搜尋方向，heap 則能快速取得 root priority、但不能快速找 arbitrary key。
3Zero-based binary heap array 中，index i 的 parent 與 children indices 為何？
Parent=floor((i-1)/2)；left=2i+1；right=2i+2，前提是對應 index 存在。
Complete binary tree 的逐層左填形狀讓 array 不需保存 child pointers。
4Binary heap insert 的 worst-case time complexity 為何？
O(log n)。新 key 先放 array 末端，再沿高度 O(log n) 的 parent chain sift-up。
保持 complete shape 是 O(1) append；worst-case 成本來自最多走到 root 的 sift-up。
5在 min-heap 尋找 arbitrary key 的 worst-case complexity 為何？
O(n)。Heap order 無法像 BST ordering 一樣決定唯一搜尋方向。
Root minimum 可 O(1) 取得，但尋找任意指定值在最壞情況可能檢查所有 nodes。
6為何 binary heap 適合實作 priority queue？
Root 可 O(1) 查看最高優先值，insert 與 extract-min/max 可在 O(log n) 完成，且 array representation 緊密。
Priority queue 是操作介面；binary heap 是兼顧插入與移除最高優先值的常見實作。
最後用考古題驗證
本課連結的題目都已通過可重現的技術覆核，可逐題練習與判分。
開始本課考古題練習參考來源
- Introduction to Algorithms (6.006) — Erik Demaine and Srini Devadas