認識樹：到處都是的階層結構
從生物分類、Unix 檔案系統與 HTML 認識樹的三大性質。
先讀原文段落，旁邊就是白話
這是一本英文書。左邊放原文、右邊放白話導讀——你既讀得懂，也順手碰了原文。
從生物分類、Unix 檔案系統與 HTML 認識樹的三大性質。
樹是什麼？生活中的樹狀結構
從生物分類、Unix 檔案系統與 HTML 認識樹的三大性質。
深度探秘
把資料排成有階層的關係
樹不是一條線
我們之前學的堆疊、佇列都是線性結構：資料像排隊一樣一個接一個。但真實世界裡很多關係不是一條線，而是一層分出好幾支的階層關係，這就需要「樹」。
樹這個資料結構有趣的地方是：它的根 (root) 在最上面，葉子 (leaf) 在最下面，跟你窗外那棵樹剛好上下顛倒。
從根開始，你可以沿著一個個節點與箭頭往下走。每到一層就像在問一個問題、依答案選一條路。例如生物分類：先問「這動物是脊索動物還是節肢動物？」選了脊索動物，再問「是不是哺乳類？」一路問下去，最後走到最底層的物種名稱。
樹有三個關鍵性質：
- 子節點彼此獨立：某節點的孩子改了，不會影響另一個節點的孩子。
- 每個葉節點唯一：從根到任一葉節點有一條唯一的路徑可以辨認它。
- 可整段搬移：你可以把一整段子樹搬到別的位置，而不破壞它內部的結構。
樹是用來表達階層關係的非線性資料結構，根在上、葉在下。
生活妙喻
電腦裡的資料夾就是一棵樹
你每天都在爬樹
想想你電腦裡的檔案系統。最外層有一個根目錄（在 Unix 裡就是 /），裡面有 etc/、usr/ 這些資料夾，資料夾裡又有子資料夾與檔案——這完完全全就是一棵樹！
從根目錄走到任何一個資料夾，這條路徑唯一指出了它的位置，例如
/etc/httpd。
而「可整段搬移」這個性質也很直覺：你把 etc/ 整個資料夾從根目錄剪下、貼到 usr/ 底下，httpd 的路徑會從 /etc/httpd 變成 /usr/etc/httpd，但 httpd 裡面的內容與子資料夾完全不受影響。搬家換了地址，但家裡的傢俱還是原封不動。
graph TD root[根目錄] --> etc[etc] root --> usr[usr] root --> var[var] etc --> httpd[httpd] var --> log[log] var --> spool[spool]
檔案系統的資料夾階層就是一棵樹，搬移子樹不影響其內部內容。
實用超能力
從 HTML 看出網頁的樹
網頁也是一棵樹
你看到的每個網頁，背後的 HTML 標籤也是巢狀的階層。最外層是 <html>，裡面包 <head> 和 <body>，<body> 裡又包 <h1>、<ul>，<ul> 裡再包 <li>。
每一層巢狀，就對應樹的一層。瀏覽器把這棵樹叫做 DOM，靠它來排版與互動。
<html>
<head>
<title>simple</title>
</head>
<body>
<h1>A simple web page</h1>
<ul>
<li>List item one</li>
<li>List item two</li>
</ul>
</body>
</html>
當你能「看出」資料中的樹狀結構，就能用樹的演算法去處理它：搜尋、走訪、整段搬移都變得有章法可循。
凡是有巢狀、階層關係的資料（檔案、HTML、分類），都能用樹來表示與處理。
最上面是執行長（根），往下是各部門主管，再往下是組員（葉）。每個人只有一個直屬上司（一條進入的邊），但可以帶很多下屬。
張家的小明和李家的小明同名，但是兩個完全獨立的人。改張家小明的事，不會動到李家小明。
本節字彙
樹的詞彙：節點、邊、根、葉
認識 node、edge、root、path、children、parent、sibling、subtree、leaf、level、height 等術語。
深度探秘
先把零件名稱搞清楚
樹的零件清單
要談樹的演算法，得先有共同語言。以下是核心詞彙：
- 節點 (node)：樹的基本單位。它有一個名字叫鍵 (key)，還可能附帶額外資料叫酬載 (payload)。
- 邊 (edge)：連接兩個節點、表示它們有關係。除了根，每個節點恰有一條進入的邊；每個節點可以有多條外出的邊。
- 根 (root)：唯一沒有進入邊的節點。
- 路徑 (path)：用邊串起來的一串有序節點。
- 子節點 (children)：從同一個節點伸出邊所連到的那些節點。
- 父節點 (parent)：用外出邊連到某些節點的那個節點。
- 兄弟 (sibling)：同一個父節點下的節點。
- 子樹 (subtree)：一個父節點連同它所有後代。
- 葉節點 (leaf)：沒有子節點的節點。
節點是基本單位，邊表示關係；除了根，每個節點恰有一條進入的邊。
生活妙喻
家族族譜上的稱謂
樹的詞彙就是族譜稱謂
樹的術語幾乎照搬家族關係：
| 樹的術語 | 家族對應 |
|---|---|
| 根 (root) | 最年長的祖先 |
| 父節點 (parent) | 上一代 |
| 子節點 (children) | 下一代 |
| 兄弟 (sibling) | 同一對父母的孩子 |
| 葉節點 (leaf) | 還沒有後代的人 |
| 子樹 (subtree) | 某個人連同他所有後代組成的家族分支 |
唯一和真實家族不同的是：在樹裡每個人只有「一個」父親（一條進入的邊），不能有兩個父節點。
graph TD A[根 祖父] --> B[父 爸爸] A --> C[父 叔叔] B --> D[葉 我] B --> E[葉 妹妹]
把樹想成族譜，根是祖先、葉是最年輕一代、兄弟是同父節點的孩子。
實用超能力
算出層數與高度
層數與高度怎麼算
還有兩個常被搞混的詞：
- 層 (level)：節點 $n$ 的層數，是從根到 $n$ 這條路徑上的邊數。根的層數定義為 $0$。
- 高度 (height)：整棵樹中任一節點的最大層數。
舉例：若 Felis 從根走下來要經過 5 條邊，它的層數就是 $5$。若整棵樹最深的節點層數是 $2$，這棵樹的高度就是 $2$。
為什麼要關心高度？因為很多樹演算法的效率取決於高度。一棵平衡良好的樹高度大約是 $O(\log n)$，搜尋會很快；一棵歪斜的樹高度可能變成 $O(n)$，就退化得跟串列一樣慢。
所以記住：層數從 0 算起、是「邊數」；高度是最深的那個層數。
層數是從根到該節點的邊數（根為 0），高度是最大層數，決定演算法效率。
除了最初的祖先（根），每個人都恰好由一條邊從父節點連入，就像每個人都只有一位親生母親。
層數是從根走過的邊數，就像從起站算你經過了幾段鐵軌；起站本身是第 0 站。
本節字彙
兩種定義：節點邊定義與遞迴定義
用節點與邊的定義，以及更實用的遞迴定義來精確描述樹與二元樹。
深度探秘
用節點與邊正式定義樹
定義一：節點與邊
有了詞彙，我們可以正式定義樹。第一種定義用節點與邊：
一棵樹由一組節點與一組連接節點對的邊組成，且滿足：
- 其中一個節點被指定為根節點。
- 除了根，每個節點 $n$ 都由一條邊從恰好一個其他節點 $p$ 連入，$p$ 是 $n$ 的父節點。
- 從根到每個節點都有一條唯一路徑。
- 如果每個節點最多兩個子節點，我們就說這是一棵二元樹 (binary tree)。
邊上的箭頭指出連接的方向（由父指向子）。這個定義很直觀，但接下來那個遞迴定義，寫程式時會更好用。
定義一用節點、邊與唯一路徑描述樹；每節點最多兩子即為二元樹。
生活妙喻
俄羅斯娃娃裡還是娃娃
定義二：遞迴定義
第二種定義用遞迴來描述：
一棵樹要嘛是空的，要嘛由一個根加上零或多個子樹組成，而每個子樹本身也是一棵樹。每個子樹的根，用一條邊連到母樹的根。
這就像俄羅斯娃娃：打開一個娃娃，裡面還是一個娃娃；再打開，裡面還是娃娃……每一層都跟整體長得一樣。
樹也是如此：一棵樹的任何一根樹枝（子樹），自己看起來也是一棵完整的樹。
graph TD R[根] --> S1[子樹一也是一棵樹] R --> S2[子樹二也是一棵樹] R --> S3[子樹三也是一棵樹]
看著上圖，我們知道至少有 4 個節點：根加上三個子樹各自的根。但實際可能更多，要往裡看才知道。
遞迴定義：樹是空的，或由根加上若干「本身也是樹」的子樹組成。
實用超能力
遞迴定義讓程式碼變優雅
為什麼遞迴定義這麼好用
遞迴定義的威力在於：只要結構是遞迴的，處理它的演算法也能寫成遞迴，而且通常短得驚人。
例如要走訪整棵樹，你只要寫：
def visit(tree):
if tree is None: # 基底情形：空樹什麼都不做
return
process(tree) # 處理根
visit(tree.left) # 子樹也是樹，遞迴處理
visit(tree.right)
注意這段程式幾乎就是定義二的直接翻譯：「空樹就停，否則處理根、再處理每個子樹（它們也是樹）」。
後面我們實作堆積、剖析樹、二元搜尋樹時，會一再看到這種「把遞迴定義直接寫成遞迴函式」的優雅模式。先建立這個直覺，後面學起來會很順。
遞迴定義讓樹演算法能直接寫成遞迴：基底處理空樹，遞迴步驟處理各子樹。
打開娃娃裡面還是娃娃，每一層都和整體同構；樹的每個子樹也都是一棵完整的樹。
二元樹規定每個節點最多兩個子節點，就像一個限定最多兩個孩子的家庭。
本節字彙
親手實作二元樹
用 [根, 左子樹, 右子樹] 的巢狀串列來表示二元樹，並寫出操作函式。
先讀原文段落，旁邊就是白話
這是一本英文書。左邊放原文、右邊放白話導讀——你既讀得懂，也順手碰了原文。
用 [根, 左子樹, 右子樹] 的巢狀串列來表示二元樹，並寫出操作函式。
串列的串列表示法
用 [根, 左子樹, 右子樹] 的巢狀串列來表示二元樹，並寫出操作函式。
深度探秘
用三格的串列裝下一棵樹
一個串列，三個位置
第一種實作二元樹的方式叫「串列的串列 (list of lists)」。核心想法很簡單：用一個有三個位置的串列來代表一個節點：
- 位置
[0]：根節點的值 - 位置
[1]：左子樹（本身也是一個這種三格串列） - 位置
[2]：右子樹（同上）
例如這棵樹：
my_tree = ['a', # 根
['b', # 左子樹
['d', [], []],
['e', [], []]],
['c', # 右子樹
['f', [], []],
[]]]
要取用子樹就用一般的串列索引：my_tree[0] 是根、my_tree[1] 是左子樹、my_tree[2] 是右子樹。空的 [] 代表沒有子樹。一個有值且兩個子樹都空的串列，就是一個葉節點。
用 [根, 左子樹, 右子樹] 的三格串列表示節點，子樹本身也是同樣的三格串列。
生活妙喻
結構本身就會遞迴
自我相似的盒子
這個表示法最妙的地方是：結構本身就是遞迴的。代表子樹的那個串列，格式跟代表整棵樹的串列一模一樣——都是「值、左、右」三格。
這就像一個分隔成三格的便當盒：第一格放主菜（根），另外兩格各放一個一模一樣的小便當盒（左、右子樹），打開小盒又是三格……
而且它還能輕鬆推廣到「多元樹」：如果一個節點不只兩個子節點，再多塞幾個子串列進去就行。
graph TD a[a 根] --> b[b] a --> c[c] b --> d[d] b --> e[e] c --> f[f]
上圖這棵樹，就對應前一頁那個巢狀串列。看圖、看串列，兩者結構完全吻合。
子樹串列的格式與整棵樹相同，結構自我相似，而且容易推廣到多元樹。
實用超能力
寫出操作函式
用函式操作這個串列樹
我們不另外定義類別，只寫一些函式把普通串列當樹用。建構與插入左子節點如下：
def binary_tree(r):
return [r, [], []]
def insert_left(root, new_branch):
t = root.pop(1)
if len(t) > 1:
root.insert(1, [new_branch, t, []])
else:
root.insert(1, [new_branch, [], []])
return root
關鍵巧思在 insert_left：先把目前的左子樹取出來 t。如果它非空（len(t) > 1），就建立新節點、把舊的左子樹當成新節點的左子，再裝回去——也就是把舊子樹往下推一層。
insert_right 對稱地處理右邊。再加上 get_root_val、set_root_val、get_left_child、get_right_child 這些存取函式，就能完整地建構與走訪這棵串列樹了。
insert_left 取出舊左子樹，把它推到新節點底下，再插回位置 1。
主格放根的值，另外兩格各放一個格式相同的小便當盒（左右子樹），層層相套。
在父與舊左子之間插入新節點時，舊左子被推到新節點下方一層，而不是被丟掉。
本節字彙
節點與參照表示法
用 BinaryTree 類別，以 left_child 與 right_child 參照來表示樹，更貼近物件導向。
深度探秘
每個節點都是一個物件
用類別與參照表示樹
第二種實作方式叫「節點與參照 (nodes and references)」，更貼近物件導向的思維。我們定義一個 BinaryTree 類別，每個節點是一個物件，內含：
key：根節點的值left_child：對左子節點物件的參照（一開始是None）right_child：對右子節點物件的參照
class BinaryTree:
def __init__(self, root):
self.key = root
self.left_child = None
self.right_child = None
重點是：left_child 與 right_child 會變成指向其他 BinaryTree 實例的參照。當我們插入一個左子節點，就建立另一個 BinaryTree 物件，並讓根的 left_child 指向它。本章接下來都會用這種表示法。
每個節點是一個 BinaryTree 物件，left_child/right_child 是指向其他節點物件的參照。
生活妙喻
便利貼上寫著下一張的位置
參照就像便利貼上的指路
想像每個節點是一張便利貼，上面寫著自己的值，還寫著「左邊那張貼在哪裡、右邊那張貼在哪裡」。這個「貼在哪裡」就是參照——它不是子節點本身，而是指向子節點的箭頭。
graph TD a[a key] --> b[b left_child] a --> c[c right_child]
插入時要分兩種情況：
- 沒有左子：直接建一個新節點，讓
left_child指向它。 - 已有左子：建新節點，把舊的左子接到新節點的
left_child，再讓自己指向新節點——也就是把舊子節點往下推一層，跟串列版的巧思一模一樣。
def insert_left(self, new_node):
if self.left_child == None:
self.left_child = BinaryTree(new_node)
else:
t = BinaryTree(new_node)
t.left_child = self.left_child
self.left_child = t
插入分兩種情況：沒有子節點就直接接上，已有子節點就把舊的往下推一層。
實用超能力
子節點也是一棵完整的樹
任一子節點本身也是樹
補上存取方法後，類別就完整了：
def get_left_child(self):
return self.left_child
def get_right_child(self):
return self.right_child
def set_root_val(self, obj):
self.key = obj
def get_root_val(self):
return self.key
來建一棵小樹試試：
r = BinaryTree('a')
r.insert_left('b')
r.insert_right('c')
print(r.get_left_child().get_root_val()) # b
r.get_right_child().set_root_val('hello')
print(r.get_right_child().get_root_val()) # hello
注意 r.get_left_child() 回傳的本身就是一個 BinaryTree 物件，所以你可以對它再呼叫 get_root_val()、甚至再 insert_left()。
這正呼應了遞迴定義：任一子節點本身也是一棵完整的二元樹。這個性質讓後面的遞迴演算法寫起來特別自然。
存取方法回傳的子節點本身是 BinaryTree 物件，可繼續對它操作，呼應遞迴定義。
left_child 不是子節點本身，而是指向子節點物件的箭頭，就像便利貼上指路的字條。
已有左子時，新節點成為中間人，舊的左子被掛到新節點底下，整體往下移一層。
本節字彙
優先佇列與二元堆積
認識優先佇列，以及為什麼用二元堆積能比排序串列更有效率。
先讀原文段落，旁邊就是白話
這是一本英文書。左邊放原文、右邊放白話導讀——你既讀得懂，也順手碰了原文。
認識優先佇列，以及為什麼用二元堆積能比排序串列更有效率。
優先佇列與二元堆積的概念
認識優先佇列，以及為什麼用二元堆積能比排序串列更有效率。
深度探秘
依優先序而非到達順序
不照先來後到，照優先序
之前學的佇列 (queue) 是先進先出 (FIFO)：誰先排隊誰先出。優先佇列 (priority queue) 也是從前端取出，但「誰在前端」不是看誰先到，而是看優先序：
- 最高優先序的項目永遠在最前面，最低優先序在最後面。
- 因此 enqueue（加入）一個新項目時，它可能會一路插到最前面。
你可能會想：用排序加串列不就好了？確實可以，但：
- 在串列中插入是 $O(n)$
- 對串列排序是 $O(n \log n)$
我們可以做得更好。經典做法是用一種叫二元堆積 (binary heap) 的資料結構，它能讓 enqueue 與 dequeue 都只要 $O(\log n)$。
優先佇列依優先序取出；二元堆積讓加入與取出都達到 O(log n)，勝過排序串列。
生活妙喻
醫院急診的檢傷分類
急診室不是先到先看
優先佇列最貼切的比喻是醫院急診的檢傷分類。你不是按掛號順序看診，而是按病情嚴重程度：心臟病發的人就算最後到，也會被立刻推到最前面；輕微感冒的人就算先到，也得等。
這就是優先佇列：到達順序不重要，優先序才決定誰先被處理。
二元堆積有兩種常見變體：
| 變體 | 誰在最前面 |
|---|---|
| 最小堆積 (min heap) | 最小的鍵 |
| 最大堆積 (max heap) | 最大的鍵 |
本章我們實作最小堆積（min heap），最大堆積留作練習。要注意：「最小」或「最大」是指鍵值，可以把鍵想成優先序的數字（例如越小越緊急）。
優先佇列像急診檢傷：嚴重程度（優先序）決定先後；堆積分 min 與 max 兩種。
實用超能力
看堆積怎麼運作
不管怎麼放進去，最小的先出來
二元堆積的介面長這樣：
BinaryHeap()：建立空堆積insert(k)：加入一個項目find_min()：回傳最小鍵的項目，但不移除del_min()：回傳並移除最小鍵的項目is_empty()、size()、build_heap(list)
來看一段示範：
bh = BinHeap()
bh.insert(5)
bh.insert(7)
bh.insert(3)
bh.insert(11)
print(bh.del_min()) # 3
print(bh.del_min()) # 5
print(bh.del_min()) # 7
print(bh.del_min()) # 11
注意：不管我們以什麼順序丟進去（5、7、3、11），del_min 每次都取出當前最小的。這正是優先佇列要的行為。下一節我們就來看它內部如何用一個串列就辦到這件事。
二元堆積在下一章的圖演算法（如最短路徑）會非常有用，先打好底子。
不論插入順序為何，del_min 每次都取出當前最小鍵，正是優先佇列的核心行為。
病人不是按到達順序看診，而是按病情嚴重程度；最緊急的就算最後到也先被處理。
排序串列每次插入要 O(n) 或排序 O(n log n)；堆積只沿一條路徑調整，達到 O(log n)。
本節字彙
結構性質與順序性質
完全二元樹可用單一串列表示，並用 2p、2p+1 找子節點；堆積順序性質保證父節點不大於子節點。
深度探秘
完全二元樹與一個串列
結構性質：完全二元樹
要讓堆積有效率，我們利用二元樹的對數特性，但前提是要讓樹平衡。堆積的做法是維持一棵完全二元樹 (complete binary tree)：
每一層都被節點填滿，唯一的例外是最底層，而最底層也要從左到右依序填。
完全二元樹有個迷人的性質：可以只用一個串列來表示，不需要節點與參照，也不需要串列的串列。因為樹是完全的，我們能用簡單的數學在串列中找到父子關係：
- 父節點在位置 $p$，它的左子在位置 $2p$，右子在位置 $2p+1$。
- 反過來，某節點在位置 $n$，它的父節點在位置 $n // 2$（整數除法）。
這幾條算式讓我們只用一個串列，就能在堆積裡快速上下移動。
完全二元樹每層填滿、底層從左到右填，可用單一串列表示：左子 2p、右子 2p+1、父 n//2。
生活妙喻
整齊的劇院座位編號
像劇院座位一樣有規律
把完全二元樹想成一座從上往下、從左往右坐滿的劇院：第一排坐 1 個（根），第二排坐 2 個，第三排坐 4 個……每排都坐滿才開放下一排，且每排都從左邊開始坐。
因為座位這麼規律，我們只要知道座號（串列位置），就能用算式直接算出父母與子女的座號——完全不必畫箭頭。
graph TD p1[位置 1 根] --> p2[位置 2 左子] p1 --> p3[位置 3 右子] p2 --> p4[位置 4] p2 --> p5[位置 5] p3 --> p6[位置 6]
注意：堆積串列的第 0 格放一個沒用到的 0，從位置 1 才開始放真正的資料。這個小技巧讓 $2p$、$2p+1$、$n//2$ 這些整數除法算得乾淨俐落。
完全二元樹像從上到下、從左到右坐滿的劇院，座號即串列位置，父子關係可直接算。
實用超能力
堆積順序性質
順序性質：父不大於子
光有形狀還不夠，堆積還要維持堆積順序性質 (heap order property)：
在最小堆積中，對於每個節點 $x$ 及其父節點 $p$，$p$ 的鍵小於或等於 $x$ 的鍵。
換句話說，父節點永遠不會比子節點大。這條規則一路傳遞下去，就保證了整棵樹的最小值一定在根（位置 1）——這就是為什麼 find_min 可以是 $O(1)$，直接看根就好。
注意堆積順序性質只規範父子之間，不規範兄弟之間的大小，也不像二元搜尋樹那樣左小右大。所以同一組資料可以對應多種合法的堆積排列。
把兩件事合起來記：
| 性質 | 規範什麼 | 帶來什麼好處 |
|---|---|---|
| 結構性質 | 形狀是完全二元樹 | 高度約 log n、可用串列表示 |
| 順序性質 | 父鍵 ≤ 子鍵 | 最小值永遠在根 |
堆積順序性質要求父鍵不大於子鍵，於是最小值必在根，find_min 為 O(1)。
每排坐滿才開放下一排，且都從左邊開始坐，只有最後一排可能沒坐滿。
每位主管（父）的『緊急程度數字』都不大於其下屬（子），所以最緊急的（最小值）一定坐在金字塔頂端。
本節字彙
堆積操作：上浮、下沉與建堆
用 perc_up、perc_down 與 build_heap 維持堆積性質，並理解 build_heap 的 O(n)。
深度探秘
插入靠上浮 perc_up
insert：先附加，再上浮
建構子很簡單：堆積就是一個串列，第 0 格放沒用到的 0，再加一個 current_size：
class BinHeap:
def __init__(self):
self.heap_list = [0]
self.current_size = 0
插入時最快的做法是把新項目附加到串列尾端——這保證仍是完全二元樹（結構性質沒破）。壞消息是它可能破壞順序性質。解法是上浮 (percolate up)：把新項目和它的父節點比較，如果比父節點小就交換，一路往上浮到正確位置。
def perc_up(self, i):
while i // 2 > 0:
if self.heap_list[i] < self.heap_list[i // 2]:
tmp = self.heap_list[i // 2]
self.heap_list[i // 2] = self.heap_list[i]
self.heap_list[i] = tmp
i = i // 2
def insert(self, k):
self.heap_list.append(k)
self.current_size += 1
self.perc_up(self.current_size)
因為只沿著一條路往上，最多走樹的高度層，所以 insert 是 $O(\log n)$。
insert 先把新項目附加到尾端（保結構），再用 perc_up 與父節點比較交換往上浮（保順序）。
生活妙喻
刪除最小值靠下沉 perc_down
del_min：搬尾端到根，再下沉
最小值就在根（位置 1），取出很容易；難的是取走後怎麼修復。做法分兩步：
- 把串列最後一個項目搬到根的位置——這維持了完全二元樹的結構，但很可能破壞順序性質。
- 用下沉 (percolate down) 把這個新根往下推到正確位置。
下沉時每一步都和較小的那個子節點交換，直到它比兩個子節點都小為止。
def perc_down(self, i):
while (i * 2) <= self.current_size:
mc = self.min_child(i)
if self.heap_list[i] > self.heap_list[mc]:
tmp = self.heap_list[i]
self.heap_list[i] = self.heap_list[mc]
self.heap_list[mc] = tmp
i = mc
def min_child(self, i):
if i * 2 + 1 > self.current_size:
return i * 2
elif self.heap_list[i*2] < self.heap_list[i*2 + 1]:
return i * 2
else:
return i * 2 + 1
為什麼要跟較小的子交換？因為交上去的那個會變成新父節點，必須比另一個子小，才不會又違反順序性質。這就像公司升職：要升就升兩個下屬中比較資深（鍵較小）的，否則又得重來。
del_min 把尾端搬到根，再 perc_down 與較小的子節點逐層交換，直到比兩子都小。
實用超能力
建堆 build_heap 的 O(n) 魔法
從一整串資料一次建好堆積
如果手上已有一整個串列，要怎麼變成堆積？直覺做法是逐一 insert，但那要 $O(n \log n)$。更聰明的是 build_heap：
def build_heap(self, a_list):
i = len(a_list) // 2
self.current_size = len(a_list)
self.heap_list = [0] + a_list[:]
while i > 0:
self.perc_down(i)
i = i - 1
關鍵在於從中間往根節點方向、對每個節點做 perc_down。為什麼從 len // 2 開始？因為超過一半位置的節點全是葉節點，沒有子節點，不需要下沉。
令人驚訝的是，這樣建堆只要 $O(n)$，比逐一插入快！直覺是：$\log n$ 來自樹的高度，但 build_heap 大部分的工作發生在接近底部、樹很矮的地方，所以總成本遠低於 $n \log n$。
之後你會在練習中用 build_heap 寫出一個 $O(n \log n)$ 的排序演算法（堆積排序）。
build_heap 從中間位置往根對每個節點 perc_down，葉節點免做，總成本只要 O(n)。
新加入的小項目像氣泡，只要比上面的父節點輕（小）就往上冒，直到浮到合適的深度。
把根往下換時必須和較小（較資深）的子交換，新父才會比另一個子小，避免再度違反順序。
底層節點又多又矮，下沉沒幾步；高的工作很少。整體加起來只要 O(n) 而非 O(n log n)。
本節字彙
樹的應用與走訪
把完全加括號的運算式變成剖析樹，再遞迴求值。
先讀原文段落，旁邊就是白話
這是一本英文書。左邊放原文、右邊放白話導讀——你既讀得懂，也順手碰了原文。
把完全加括號的運算式變成剖析樹，再遞迴求值。
剖析樹：建立與求值
把完全加括號的運算式變成剖析樹，再遞迴求值。
深度探秘
把運算式變成一棵樹
剖析樹是什麼
剖析樹 (parse tree) 能把真實世界的結構（句子、數學運算式）表示成樹。以數學運算式為例，$((7 + 3) * (5 - 2))$ 可以畫成一棵樹：根是 *，左子樹是 +（7 與 3），右子樹是 -（5 與 2）。
樹的階層自然反映了運算順序：要算頂層的乘法，得先算兩個括號裡的加法與減法。先把左子樹算成 10、右子樹算成 3，再相乘得 30。
建立剖析樹用四條規則，逐一讀取詞元 (token)：
- 讀到
(：在目前節點新增一個左子，往左子下降。 - 讀到運算子
+ - * /：把目前節點的值設為該運算子，新增一個右子，往右子下降。 - 讀到數字：把目前節點的值設為該數字，回到父節點。
- 讀到
)：回到父節點。
剖析樹把運算式表示成樹，階層反映運算順序；建立時依四條規則處理括號、運算子、數字。
生活妙喻
用堆疊記住回家的路
麵包屑與堆疊
建樹時我們會一直往子節點下降，但「回到父節點」時怎麼知道父節點是誰？樹介面只給我們往下找子節點的方法，沒有往上找父節點的方法。
解法是用一個堆疊 (stack)：每次要下降到子節點前，先把目前節點 push 進堆疊；要回到父節點時，就從堆疊 pop 出來。
這就像走迷宮時沿路撒麵包屑：往深處走時一路留記號，要回頭時照著麵包屑倒著走回去。
flowchart TD A[讀左括號 下降到左子 並把目前節點推入堆疊] --> B[讀數字 設值 從堆疊彈出回到父節點] B --> C[讀運算子 設值 新增右子並下降 推入堆疊] C --> D[讀右括號 從堆疊彈出回到父節點]
程式碼大致如下（節錄）：
if i == '(':
current_tree.insert_left('')
p_stack.push(current_tree)
current_tree = current_tree.get_left_child()
elif i in ['+', '-', '*', '/']:
current_tree.set_root_val(i)
current_tree.insert_right('')
p_stack.push(current_tree)
current_tree = current_tree.get_right_child()
elif i == ')':
current_tree = p_stack.pop()
用堆疊追蹤父節點：下降前 push 目前節點，回到父節點時 pop，就像撒麵包屑找回家的路。
實用超能力
遞迴求值剖析樹
建好之後，遞迴求值
樹建好後，我們用遞迴來求值。基底情形是葉節點——在剖析樹裡，葉節點一定是運算元（數字），直接回傳它的值。遞迴步驟則是對左、右子節點各自呼叫 evaluate，再把兩個結果套上父節點的運算子。
運算子用一個字典對應到 Python operator 模組的函式：
import operator
def evaluate(parse_tree):
opers = {'+': operator.add, '-': operator.sub,
'*': operator.mul, '/': operator.truediv}
left = parse_tree.get_left_child()
right = parse_tree.get_right_child()
if left and right:
fn = opers[parse_tree.get_root_val()]
return fn(evaluate(left), evaluate(right))
else:
return parse_tree.get_root_val()
以 $(3 + (4 * 5))$ 為例：左子 evaluate 得 3，右子 evaluate 先算 $4 * 5 = 20$，最後 $3 + 20 = 23$。整個過程就是「先算子樹、再合併到根」，與我們後面要學的後序走訪不謀而合。
求值的基底情形是葉節點（直接回傳值），遞迴步驟對左右子求值後套上父節點運算子。
深入時沿路留記號（push），要回頭時照麵包屑倒走回去（pop），就能找到父節點。
先算出左子樹與右子樹的答案，再用根上的運算子把兩個小答案合成一個大答案。
本節字彙
三種走訪：前序、中序、後序
差別只在於拜訪根節點的時機，用遞迴寫起來非常優雅。
深度探秘
差別只在拜訪根的時機
三種走訪，差在何時看根
走訪 (traversal) 是指拜訪樹裡所有節點的固定模式。三種常見走訪的差別，只在於什麼時候拜訪根節點：
- 前序 (preorder)：先拜訪根 → 遞迴走左子樹 → 遞迴走右子樹。
- 中序 (inorder)：遞迴走左子樹 → 拜訪根 → 遞迴走右子樹。
- 後序 (postorder)：遞迴走左子樹 → 遞迴走右子樹 → 最後拜訪根。
注意三者左、右子樹的順序都一樣（先左後右），唯一移動的是「印出/拜訪根」這一行的位置。寫成程式碼時優雅得驚人，因為都是遞迴：
def preorder(tree):
if tree:
print(tree.get_root_val()) # 根放最前
preorder(tree.get_left_child())
preorder(tree.get_right_child())
把那行 print 往下挪，就變成中序或後序。
前序、中序、後序的唯一差別是拜訪根的時機（最前、中間、最後），左右子樹順序相同。
生活妙喻
前序就像從頭讀一本書
把整本書當成一棵樹
把一本書想成樹：書是根，每一章是子節點，每章下面有節，節下面有小節……
如果你想從頭到尾讀這本書，那順序正好就是前序走訪：先看書名（根），再進第一章，章裡先看 1.1、再看 1.2……讀完第一章才回到書、進第二章。
graph TD Book[書] --> C1[第一章] Book --> C2[第二章] C1 --> S11[第 1.1 節] C1 --> S12[第 1.2 節] C2 --> S21[第 2.1 節]
前序＝先看自己再往下，正是「先讀標題再讀內容」的閱讀順序。
而把走訪寫成「外部函式」（傳入樹當參數）比寫成「方法」更俐落，因為外部函式的基底情形只要檢查 if tree:（樹是否存在）即可；寫成方法則要在呼叫前先檢查左右子是否存在。所以本章其餘走訪都寫成外部函式。
前序走訪等同從頭讀一本書的順序：先看標題（根）再依序深入各章節。
實用超能力
後序求值，中序還原運算式
走訪的真實用途
後序走訪和我們上一節的剖析樹求值幾乎一模一樣：先算左子樹、再算右子樹、最後在根用運算子合併。把 print 改成 return，就成了 postorder_eval：
def postorder_eval(tree):
opers = {'+': operator.add, '-': operator.sub,
'*': operator.mul, '/': operator.truediv}
res1 = res2 = None
if tree:
res1 = postorder_eval(tree.get_left_child())
res2 = postorder_eval(tree.get_right_child())
if res1 and res2:
return opers[tree.get_root_val()](res1, res2)
else:
return tree.get_root_val()
中序走訪則能把剖析樹還原成運算式。只要在走左子樹前印 (、走右子樹後印 )，就能還原出完全加括號的版本：
def print_exp(tree):
str_val = ""
if tree:
str_val = '(' + print_exp(tree.get_left_child())
str_val = str_val + str(tree.get_root_val())
str_val = str_val + print_exp(tree.get_right_child()) + ')'
return str_val
所以走訪不只是「逛一圈」，而是解決求值、還原、排序等真實問題的骨架。
後序走訪天生適合求值剖析樹；中序走訪加上括號能還原原始運算式。
先看書名與章標題（根），再依序深入每一節，正是先根後子的前序順序。
左右子樹的行走順序都一樣，只是『在根拍照』的時機放在出發前、中途或回程，就成了前、中、後序。
本節字彙
二元搜尋樹與 Map
二元搜尋樹靠 bst 性質：左子樹的鍵都比父小、右子樹都比父大。
先讀原文段落，旁邊就是白話
這是一本英文書。左邊放原文、右邊放白話導讀——你既讀得懂，也順手碰了原文。
二元搜尋樹靠 bst 性質：左子樹的鍵都比父小、右子樹都比父大。
Map ADT 與 BST 性質
二元搜尋樹靠 bst 性質：左子樹的鍵都比父小、右子樹都比父大。
深度探秘
用樹來實作鍵值對照表
Map ADT：鍵對應到值
我們之前看過兩種實作 Map（對照表） 的方式：在串列上做二元搜尋，以及雜湊表。這一章用二元搜尋樹 (binary search tree, BST) 當作第三種方式，把鍵 (key) 對應到值 (value)。Map 的介面和 Python 字典幾乎一樣：
Map()：建立空 Map。put(key, val)：加入鍵值對；鍵若已存在則更新值。get(key)：依鍵取值，找不到回None。del map[key]：刪除鍵值對。len()：鍵值對數量。key in map：判斷鍵是否存在。
和堆積不同，這裡我們不在意節點的確切位置，而是想利用二元樹的結構來做有效率的搜尋。
二元搜尋樹是實作 Map ADT 的第三種方式，介面像字典，目標是有效率地依鍵搜尋值。
生活妙喻
左小右大的猜數字遊戲
BST 性質：左小右大
二元搜尋樹的核心是 bst 性質：
對每個節點，左子樹裡的所有鍵都比它小，右子樹裡的所有鍵都比它大。
這就像玩猜數字遊戲：對方說「比 50 小」，你就只往左邊找；說「比 50 大」，就只往右邊找——每問一次，搜尋範圍就砍半。
graph TD n70[70] --> n31[31] n70 --> n93[93] n31 --> n14[14] n93 --> n94[94] n14 --> n23[23]
上圖是依序插入 70、31、93、94、14、23 後的樹。注意這個性質對每一對父子都成立：往任何節點看，它左邊的子孫都比它小、右邊的都比它大。正因如此，搜尋時可以像翻字典一樣不斷縮小範圍。
bst 性質：左子樹全部比父小、右子樹全部比父大，搜尋時每步都能砍半範圍。
實用超能力
插入順序決定樹的形狀
插入順序很重要
建立 BST 時，鍵的插入順序會決定樹長什麼樣子。第一個插入的鍵成為根，之後每個鍵都從根開始比較：比目前節點小就往左、大就往右，直到找到一個空位掛上去。
例如依序插入 70、31、93、94、14、23、73：
- 70 是第一個，成為根。
- 31 < 70，成為 70 的左子。
- 93 > 70，成為 70 的右子。
- 94 > 70 且 > 93，成為 93 的右子。
- 14 < 70 且 < 31，成為 31 的左子。
- 23 < 31 但 > 14，成為 14 的右子。
警告：如果你照排序好的順序插入（例如 1, 2, 3, 4, 5），每個都比前一個大，全部往右掛，樹就退化成一條歪斜的串列！這時搜尋效率會從 $O(\log n)$ 掉到 $O(n)$。
所以同樣一組鍵，插入順序不同，可能得到漂亮平衡的樹，也可能得到糟糕的歪斜樹。
插入順序決定 BST 形狀；照排序順序插入會退化成歪斜串列，搜尋掉到 O(n)。
每次得到『比某數大或小』的提示就往對應方向走，搜尋範圍每步砍半，就像 BST 沿左右子樹下降。
先到的人佔據關鍵位置（根），後面的人只能依規則往左或往右找空位，順序不同分佈就不同。
本節字彙
BST 的實作與效能
用 BinarySearchTree 與 TreeNode 兩個類別實作，並理解平衡與否對效能的影響。
深度探秘
兩個類別分工合作
為什麼用兩個類別
實作 BST 時，我們用兩個類別分工：
BinarySearchTree：外層門面，持有一個指向根TreeNode的參照，還有size。TreeNode：真正的節點，存key、payload，以及left_child、right_child、parent參照。
為什麼要分兩個？因為我們必須能處理「空樹」：剛建立時根是 None。外層方法通常先檢查樹是否為空，若有節點就把工作委派給以根為起點的私有遞迴輔助函式（如 _put、_get）。空樹或要刪除根這種特殊情況，才在外層特別處理。
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
TreeNode 還提供 is_leaf()、has_both_children()、is_left_child() 等許多輔助函式，並且明確記錄 parent——這在實作 del 刪除時特別重要。
BinarySearchTree 是門面、TreeNode 是節點；分兩類別才好處理空樹，TreeNode 記 parent 方便刪除。
生活妙喻
put 與 get 像翻電話簿
插入與查找：沿路比較
put 從根開始，把新鍵和目前節點比較：比較小往左、比較大往右，直到遇到一個空位（沒有對應的子節點）就把新節點掛上去。插入時把目前節點當作新節點的 parent 傳進去。
def _put(self, key, val, current_node):
if key < current_node.key:
if current_node.has_left_child():
self._put(key, val, current_node.left_child)
else:
current_node.left_child = TreeNode(key, val, parent=current_node)
else:
if current_node.has_right_child():
self._put(key, val, current_node.right_child)
else:
current_node.right_child = TreeNode(key, val, parent=current_node)
get 更簡單，用同樣的左右判斷邏輯一路找下去，找到相符的鍵就回傳其 payload，走到底還沒找到就回 None。
這就像翻紙本電話簿：翻到中間看看姓氏，太前面就往後翻、太後面就往前翻，每翻一次範圍就縮小一半。
透過 __setitem__、__getitem__、__contains__ 多載運算子，我們就能寫出 my_tree['Fargo'] = 55446 與 'Fargo' in my_tree 這種像字典的語法。
put/get 從根沿左右子下降比較鍵，找到空位掛上或找到相符鍵回傳值，像翻電話簿縮小範圍。
實用超能力
效能取決於是否平衡
BST 的效能：平衡是關鍵
BST 的操作成本，取決於從根走到目標所經過的路徑長度，也就是樹的高度。
| 情況 | 樹的形狀 | put / get / in 的成本 |
|---|---|---|
| 平衡良好 | 高度約 $\log n$ | $O(\log n)$ |
| 最差（歪斜） | 高度約 $n$ | $O(n)$ |
當鍵以隨機順序插入時，樹通常相當平衡，操作接近 $O(\log n)$，非常快。但若鍵以排序順序插入，樹會退化成一條斜線，操作退化成 $O(n)$，跟普通串列一樣慢。
flowchart TD A[插入順序隨機] --> B[樹大致平衡 高度約 log n] --> C[查找快 O log n] D[插入順序已排序] --> E[樹歪斜成串列 高度約 n] --> F[查找慢 O n]
這就是為什麼會發展出 AVL 樹這類「自我平衡」的二元搜尋樹：它們在每次插入後自動旋轉調整，保證高度始終維持在 $O(\log n)$，避免退化。
記住核心觀念：BST 快不快，全看它平不平衡。
BST 操作成本等於樹高；平衡時 O(log n)，歪斜時退化 O(n)，AVL 樹靠自動旋轉維持平衡。
BinarySearchTree 像櫃檯處理『有沒有人在』這類門面問題，再把實際工作轉給內部員工 TreeNode 的遞迴輔助函式。
平衡的樹像分類整齊的書架，幾步就找到；歪斜的樹像把書全疊成一落，只能從頭一本本翻。