樹與樹的演算法

cppds Chapter 8 — Trees, Heaps, BSTs & AVL（對應講義 09）
術語｜解析樹｜走訪｜二元堆積｜BST｜AVL
向下捲動開始互動↓
📌 本頁使用方式（cppds Ch.8｜講義 09）

① 照節次讀：每一節先讀說明、動手玩互動元件，預測結果再按按鈕驗證。 ② 對照講義：頁上 §徽章對應 cppds 章節；細節與完整程式請回講義 09 與 cppds 原文。 ③ 每節做 quiz：答錯就回到該節重讀，不要往下跳。 ④ 最後翻 關鍵詞彙卡（33 張）自測術語（中文為主、術語附英文），並用 REF 總覽區當速查表。標 Optional／Python 參考的內容第一輪可略過。

📑 講義 09 PDF🖥 講義 09 HTML📖 cppds 原文（Trees）📘 Hello 演算法（樹）📘 Hello 演算法（堆積）🏠 章節總覽
CONTENTS · 內容目錄
P00引言：為什麼需要樹？ P01術語與定義 P02Nodes & References P03解析樹 Parse Tree P04樹的走訪 P05二元堆積 P06二元搜尋樹 P07BST 刪除三情境 P08BST 分析 P09AVL 樹與旋轉 REFMap ADT 總覽比較 QUIZ自我檢測（8 題） CARD關鍵詞彙卡（33 張）
PROLOGUE · 開場

Examples of Trees：最普遍的階層式結構 cppds §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（小的在左、大的在右）中是有語義的。

講義完整範例：BinaryTree 與解析樹的使用畫面

講義 09 · BinaryTree 基本操作
#include <iostream> #include "pythonds3/cppds/binarytree.hpp" // 本節的完整類別 using namespace std; int main() { BinaryTree aTree("a"); cout << aTree.getRootVal() << endl; cout << aTree.getLeftChild() << endl; // NULL 印出來是 0 aTree.insertLeft("b"); cout << aTree.getLeftChild()->getRootVal() << endl; aTree.insertRight("c"); cout << aTree.getRightChild()->getRootVal() << endl; aTree.getRightChild()->setRootVal("hello"); cout << aTree.getRightChild()->getRootVal() << endl; return 0; }
預期輸出
a
0
b
c
hello

getLeftChild() 回傳的是整棵左子樹（BinaryTree*），不只是值：所以能一路 -> 下去操作任何深度的節點。insertLeft 若遇到既有左子樹，會把它「往下推」成新節點的左子樹。

講義 09 · 解析樹：建樹、求值、還原
#include <iostream> #include "pythonds3/cppds/binarytree.hpp" // buildParseTree + evaluate + printExp using namespace std; int main() { BinaryTree* pt = buildParseTree("( 3 + ( 4 * 5 ) )"); inorder(pt); // 中序走訪：印回運算式的骨架 cout << endl; cout << evaluate(pt) << endl; // 後序邏輯：先算子樹再套運算子 cout << printExp(pt) << endl; // 中序＋括號還原 return 0; }
預期輸出
3 + 4 * 5 
23
((3)+((4)*(5)))

三個函式就是三種走訪的應用：inorder 印骨架（但括號不見了）、evaluate 是後序（算 4*5=20 再算 3+20）、printExp 是中序加括號（每個子樹都包一層，連葉節點也包）。課後練習：改 printExp，讓葉節點不要包括號，輸出變成 (3+(4*5))。

PART 02 · 樹的實作

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

Python 原書另示範 list of lists（巢狀串列）；這裡只保留為語言比較。C++ 主線採 nodes and references（節點物件 + 指標）：每個 BinaryTree 帶 key、leftChild、rightChild，子指標不是 NULL 時就指向另一棵遞迴定義的樹。

語言比較：List of Lists Python 原書參考（課堂跳過）

巢狀串列版把「根的值」放在第 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
#include "pythonds3/cppds/binarytree.hpp"int main() { BinaryTree aTree("a"); aTree.insertLeft("b"); aTree.insertRight("c"); aTree.getLeftChild()->insertRight("d"); aTree.getRightChild()->insertLeft("e"); aTree.getRightChild()->insertRight("f"); return 0; }
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。

›按「開始」逐 token 建構解析樹
速度
即時狀態 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
#include "pythonds3/cppds/binarytree.hpp" void preorderPanel(BinaryTree* tree) { if (tree != NULL) { cout << tree->getRootVal() << " "; preorderPanel(tree->getLeftChild()); preorderPanel(tree->getRightChild()); } }
遞迴呼叫堆疊 STACK
call stack ↓
用途
Preorder：複製樹、序列化、目錄列表（先列父再進子）。
Inorder：BST 上得到排序輸出；解析樹上得到中序表達式。
Postorder：解析樹的表達式評估、刪除整棵樹（先刪 child 才能釋放 parent）。
小實驗：對解析樹 (3+(4*5)) 做三種走訪
Preorder+ 3 * 4 5前綴表達式
Inorder3 + 4 * 5中序（沒括號會失精度）
Postorder3 4 5 * +後綴表達式
這也說明了為什麼後綴表達式（RPN）能用 stack 直接計算：postorder 的順序就是「邊計算邊累積」的最佳順序。
PART 05 · 二元堆積

Binary Heap：用陣列實作的優先佇列 cppds §8.7–8.10

優先佇列每次取出優先級最高的元素。若用 vector，維持排序會讓取最小為 $O(1)$、插入因搬移而為 $O(n)$；不排序則插入 $O(1)$、尋找並刪除最小值 $O(n)$。Binary heap 讓 insert 與 delete-min 都是 $O(\log n)$。

cppds §8.8：Priority Queue Example 排程工作 (2, compile)、(5, backup)、(1, interrupt)、(3, render) 放進 min-heap 後，依序取出 interrupt、compile、render、backup。Heap 只保證 root 是當前最小者，不會把其餘元素完整排序。
堆積的兩個性質 結構性質（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]）：
›選擇操作後按「開始」
當前 heap：
速度
即時統計 LIVE
交換次數
0
比較次數
0
當前索引 i—
parent (i-1)/2—
虛擬碼 CODE
#include <algorithm>#include <vector>using namespace std; void percUp(vector<int>& heap, int i) { while (i > 0) { int parent = (i - 1) / 2; if (heap[i] < heap[parent]) swap(heap[i], heap[parent]); else break; i = parent; } }
複雜度
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() { // 取出最小值 if (heap.empty()) throw underflow_error("empty heap"); swap(heap[0], heap[heap.size() - 1]); int result = heap.back(); heap.pop_back(); if (!heap.empty()) 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() 也總是取出最小者。findMin() 讀取最小值，delMin() 移除最小值，size() 回傳元素數，buildHeap() 從一批資料建堆。delet() 與 heapify() 分別是 delMin() 與 buildHeap() 的別名。

應用：Heap Sort（堆排序）

有了 heapify（$O(n)$）和 $n$ 次 delete-min（每次 $O(\log n)$），教學版可把結果寫到另一個 vector，總時間 $O(n \log n)$、額外空間 $O(n)$。真正的 in-place heapsort 則直接在原陣列管理 heap 範圍。

講義 09 · buildHeap 的使用畫面＋heapSort 練習
#include <iostream> #include <vector> #include "pythonds3/cppds/binaryheap.hpp" using namespace std; vector<int> heapSort(vector<int> unsortedList) { BinaryHeap heap; vector<int> sortedList; ____; // 1. heap.buildHeap(unsortedList)，O(n) while (____) { // 2. !heap.isEmpty() ____; } return sortedList; } int main() { BinaryHeap aHeap; aHeap.buildHeap({10, 4, 9, 8, 12, 15, 3, 5, 14, 18}); aHeap.print(); for (int x : heapSort({10, 3, 5, 1, 15, 7, 9, 2, 8})) cout << x << " "; cout << endl; return 0; }
buildHeap 與 heapSort 的輸出
3 4 9 5 12 15 10 8 14 18
1 2 3 5 7 8 9 10 15

第一行是 buildHeap 建立的最小堆積，每個父節點都小於或等於其子節點；第二行是 heapSort 排好的結果。buildHeap 為 O(n)，逐一 insert 建堆的最差成本為 O(n log n)；delMin 每次 O(log n)。

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 提供第三條路：

Map 與 ownership 契約 put(key, value) 遇到重複 key 時更新 value、不增加 size。remove() 釋放被移除節點；整棵樹具備 destructor、deep copy 與 move 行為，避免兩個物件共同擁有同一批 pointers。 平衡樹子類別透過 protected virtual insertOrAssign() hook 延伸插入，不繞過公開 put() 的 size 契約。
BST 性質（BST property） 對樹中每個節點 $x$：left subtree 內所有 key < $x$.key < right subtree 內所有 key。
這個簡單的性質導致兩個強大結果：
1. 從 root 出發比較 key，每一步會排除整個不可能的子樹，但不保證剛好一半；成本是 $O(h)$，平衡時才是 $O(\log n)$。
2. 對 BST 做 inorder traversal 直接得到排序的 key 序列。
›輸入 key 並選擇操作
速度
即時狀態 LIVE
當前操作—
比較次數0
當前 node—
樹高度—
節點數—
結果—
虛擬碼 — put CODE
#include <string> struct TreeNode { std::string key, value; TreeNode *leftChild = nullptr, *rightChild = nullptr, *parent = nullptr; TreeNode(std::string k, std::string v, TreeNode* p = nullptr) : key(k), value(v), parent(p) {} }; void put(const std::string& key, const std::string& value, TreeNode* currentNode) { if (key == currentNode->key) { currentNode->value = value; return; } if (key < currentNode->key) { if (currentNode->leftChild != nullptr) put(key, value, currentNode->leftChild); else currentNode->leftChild = new TreeNode(key, value, currentNode); } else { if (currentNode->rightChild != nullptr) put(key, value, currentNode->rightChild); else currentNode->rightChild = new TreeNode(key, value, currentNode); } }
build BST 的順序很重要 把 keys $70, 31, 93, 94, 14, 23, 73$ 依序插入會得到一棵漂亮的「平衡」BST；但若插入順序是 $14, 23, 31, 70, 73, 93, 94$（已排序），新樹會退化成一條鏈：高度從 $O(\log n)$ 變成 $O(n)$。試試上面的「隨機」按鈕和輸入排序的 keys 比較看看。這就是下一節要解決的問題。
講義 09 · BinarySearchTree 當 Map 用＋treeSort 練習
#include <iostream> #include <vector> #include "pythonds3/cppds/bst.hpp" // TreeNode + BinarySearchTree using namespace std; vector<string> treeSort(vector<string> values) { BinarySearchTree bst; vector<string> result; ____; // 1. 全部 put 進去（平均每次 O(log n)） ____; // 2. 中序走訪，鍵自動由小到大（O(n)） return result; } int main() { BinarySearchTree myTree; myTree.put("a", "a"); myTree.put("q", "quick"); myTree.put("b", "brown"); myTree.put("f", "fox"); myTree.put("j", "jumps"); myTree.put("o", "over"); myTree.put("t", "the"); myTree.put("l", "lazy"); myTree.put("d", "dog"); cout << myTree.get("q") << " " << myTree.get("l") << endl; cout << "There are " << myTree.length() << " items in this tree" << endl; myTree.remove("a"); cout << "There are " << myTree.length() << " items in this tree" << endl; myTree.inorder(myTree.root); // 依鍵序印出 value cout << endl; return 0; }
預期輸出
quick lazy
There are 9 items in this tree
There are 8 items in this tree
brown dog fox jumps lazy over quick the

中序走訪 BST 會依鍵排序。put 遇到重複 key 時更新 value、size 不變；protected virtual insertOrAssign hook 讓 AVL 延伸插入而不繞過 size 契約。remove 釋放節點，整棵樹使用 deep-copy/move ownership。

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
TreeNode* findSuccessor() { if (rightChild != NULL) { return rightChild->findMin(); } return NULL; } TreeNode* findMin() { TreeNode* 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、contains、remove 都沿 root-to-leaf path 前進，時間複雜度正比於樹高 $h$。所以關鍵問題是：給定 $n$ 個節點，$h$ 會是多少？

高度與節點數的關係 完美平衡二元樹（每層填滿）有 $2^{h+1}-1$ 個節點，所以 $h \approx \log_2 n$。
若 keys 隨機插入，高度期望也是 $O(\log n)$，因為大概一半 key 進左、一半進右。
但最差情況 $h = n - 1$：把已排序 keys 依序插入就會發生：每個新節點都比當前所有節點大（或小），永遠落到右（或左）這一支，BST 退化成連結串列。

隨機順序插入

height = —

已排序順序插入

height = —
複雜度對照
操作平均最差
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 < 1.44 \log_2(n+1)$
由 Fibonacci 樹（最瘦的 AVL 樹）推導
為什麼是 1.44 log n？ 最瘦的 AVL 樹滿足 $N_h = 1 + N_{h-1} + N_{h-2}$、$N_0=1$、$N_1=2$，所以 $N_h=F_{h+3}-1$。當 $h$ 很大時 $N_h \approx \Phi^{h+3}/\sqrt 5-1$。反解得到的是高度上界而非每棵 AVL 的精確等式： $$ h = O(\log n),\qquad h < 1.44\log_2(n+1) $$ 這比完美平衡的 $\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 的 insertOrAssign() 跟 BST 幾乎一樣，唯一差別是掛上新節點後多呼叫一次 updateBalance()：它沿著 parent 指標往上修正平衡因子， 一發現 |bf| > 1 就地 rebalance()。旋轉最多兩次、每次 O(1)， 往上修正最多走 log n 層，所以 put 整體仍是 O(log n)。 上面的動畫可以對照著看：四個按鈕（LL/RR/LR/RL）正是 rebalance 的四個分支。刪除後的重平衡，講義留作練習。

insertOrAssign() 的差異 ＋ updateBalance CODE
// insertOrAssign() 的差異：新葉掛上後多呼叫一次 updateBalance bool insertOrAssign(string key, string value, TreeNode*& slot, TreeNode* parent) override { if (slot == NULL) { auto* node = new AVLTreeNode(key, value, 0, parent); slot = node; updateBalance(node); return true; } auto* current = static_cast<AVLTreeNode*>(slot); if (key == current->key) { current->value = value; return false; } TreeNode*& child = (key < current->key) ? current->leftChild : current->rightChild; return insertOrAssign(key, value, child, current); } 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 Vector
(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)$
contains(key) $O(\log n)$ $O(1)$ $O(n)$ $O(\log n)$
remove(key) $O(n)$ $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)$ 操作。

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

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

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

QUIZ · 自我檢測

自我檢測：樹結構 課程題庫 ch9 · 8 題

題目取自課程題庫（已譯為繁體中文），每個選項都有解說：選錯也點開看看為什麼錯。全對之後再往下翻詞彙卡。

Q1.AVL 樹改良了標準二元搜尋樹的哪一點？
Q2.用二元堆積（Binary Heap）實作優先佇列，最主要的理由是什麼？
Q3.二元搜尋樹（BST）中，每個節點必須滿足什麼性質，搜尋才會有效率？
Q4.哪一種樹走訪方式，是等所有子樹都走完之後才造訪根節點？
Q5.關於樹的邊與節點，下列哪個敘述正確？
Q6.從 n 個 keys 建立 heap 時，逐一 insert 與 bottom-up buildHeap 的複雜度如何？
Q7.課程 BST map 的 put(key, value) 遇到既有 key 時應怎麼做？
Q8.以邊數定義 height 時，最瘦的 AVL tree 應滿足哪個敘述？
CARDS · 關鍵詞彙卡

關鍵詞彙卡：點卡片翻面 題庫 ch9.json · 33 張

詞彙卡取自本章課程題庫，已譯為繁體中文，正面附英文原名。先看正面術語，心中默想定義再翻面對答案；洗牌後再過一輪，直到每張都能不假思索說出來。

INDEX
章節總覽