Tree 是從「線性」到「階層」的跳躍，也是理解資料庫索引和檔案系統的入口。
先講結論
BST（二元搜尋樹）靠「左小右大」的規則，把搜尋、插入、刪除都做到 O(log n)。但它有致命弱點——如果資料按順序插入，會退化成鏈表。所以才有了 AVL Tree 和 Red-Black Tree 這些自平衡變體。
樹的基本結構
50 ← root
/ \
30 70 ← 子節點
/ \ / \
20 40 60 80 ← leaf（葉節點）
每個節點有值、左子節點、右子節點。沒有子節點的叫 leaf。從 root 到最深 leaf 的距離叫 height。
BST 的核心規則：左小右大
Binary Search Tree 的每個節點都滿足：左子樹所有值 < 自己 < 右子樹所有值。
這個規則讓搜尋變得像翻字典——你不用從頭翻到尾，每次比較就能排除一半。
搜尋 40：
50 → 左（40 < 50）→ 30 → 右（40 > 30）→ 40 ✓
只比較了 3 次，而不是遍歷全部 7 個節點。
BST 刪除：三種情況
刪除是 BST 操作裡最麻煩的。
刪 leaf：直接拔掉。
刪只有一個子節點的：讓子節點頂替自己。
刪有兩個子節點的：找右子樹的最小值來替代（in-order successor），然後刪掉那個最小值節點。
刪除 50：
50 60（右子樹最小值頂替）
/ \ → / \
30 70 30 70
/
60
為什麼用右子樹最小值？因為它比左子樹所有值大、比右子樹其他值小，剛好滿足 BST 規則。
四種遍歷
50
/ \
30 70
| 方式 | 順序 | 結果 | 重點用途 |
|---|---|---|---|
| In-order | 左→根→右 | 30, 50, 70 | BST 排序輸出 |
| Pre-order | 根→左→右 | 50, 30, 70 | 序列化/複製樹 |
| Post-order | 左→右→根 | 30, 70, 50 | 刪除樹 |
| Level-order | 一層一層 | 50, 30, 70 | BFS |
最重要的是 In-order：BST 的 in-order traversal 會自動產生排序好的結果。這不是巧合，是 BST「左小右大」規則的直接結果。
退化問題：為什麼需要平衡
依序插入 1, 2, 3, 4, 5：
1
\
2
\
3 → 退化成鏈表
\ 搜尋變 O(n)
4
\
5
這就是為什麼面試官問你「BST 最差情況的複雜度」，答案是 O(n) 不是 O(log n)。
解法：讓樹自動維持平衡。AVL Tree 嚴格要求高度差 ⇐ 1，Red-Black Tree 寬鬆一點但插入刪除更快。Java 的 TreeMap 和 TreeSet 底層就是 Red-Black Tree。
Tree 的實際應用
你可能以為 Tree 是學術玩具，但它無處不在：
- 資料庫索引：MySQL 的 InnoDB 用 B+ Tree，每次查詢都在走樹
- 檔案系統：目錄結構就是一棵樹
- DOM：瀏覽器的 Document Object Model 是一棵樹
- AST：編譯器把你的程式碼解析成抽象語法樹
Tree 是程式設計師認識「分治法」的第一站——把大問題劈成兩半，再劈成兩半，直到簡單到可以直接解。