第 16 章 中等 約 15 分鐘
二元搜尋樹：左小右大的樹
樹版本的二分搜尋，新增/查詢平均 O(log n)。但歪掉會變 O(n)，所以才有後來的 AVL/紅黑樹。
一棵「左小右大」的樹
二元搜尋樹 (BST) 是一種樹，每個節點有 ≤2 個子節點，而且：
- 左子樹的所有值 < 節點值
- 右子樹的所有值 > 節點值
例：依序插入 50, 30, 70, 20, 40, 60, 80：
注意 30 的左子樹（20）都 < 30，右子樹（40）> 30。整棵樹都符合這條規則。
查詢：跟二分搜尋一樣
要找 60，從根 50 開始：
50 → 60 比 50 大，往右
70 → 60 比 70 小，往左
60 → 找到！每一步把搜尋範圍減半——平均 O(log n)。
插入：找到位置塞下去
要插入 35：
50 → 35 < 50，往左到 30
30 → 35 > 30，往右到 40
40 → 35 < 40，往左→ 空 → 新節點 35 放這三種走訪
BST 有三種經典走訪順序（考試必考）：
| 走訪 | 順序 | 結果（上面那棵樹） |
|---|---|---|
| 中序 (Inorder) | 左 → 根 → 右 | 20, 30, 40, 50, 60, 70, 80 ← 排好序了！ |
| 前序 (Preorder) | 根 → 左 → 右 | 50, 30, 20, 40, 70, 60, 80 |
| 後序 (Postorder) | 左 → 右 → 根 | 20, 40, 30, 60, 80, 70, 50 |
💡關鍵性質
BST 的中序走訪 = 把所有值由小到大排出來。 這是 BST 最重要的性質，考試很愛問。
複雜度
| 操作 | 平均 | 最壞 |
|---|---|---|
| 查詢 / 插入 / 刪除 | O(log n) | O(n) ⚠️ |
最壞何時發生？樹歪掉變一條長鏈（例如按順序插入 1, 2, 3, 4, 5…）：
這個問題的解法是 自平衡 BST：AVL Tree、紅黑樹 (Red-Black Tree)。 它們會在插入時自動「轉一下」維持高度 O(log n)。
📝考試會這樣考
題型一：按順序插入一串數字，畫出 BST。
例：依序插入 50, 30, 70, 25, 40, 60, 80。畫出結果。 訣竅：一個一個來，每個都從根開始走「小左大右」直到空位。
題型二：給 BST，寫出三種走訪。 記訣竅：「中序左中右、前序中左右、後序左右中」。
題型三：BST 最壞情況什麼時候發生？怎麼避免？ 答：按已排序順序插入時，BST 退化成鏈，變 O(n)。 避免：用 AVL 樹或紅黑樹等自平衡 BST。
題型四：給前序 + 中序，重建 BST。 經典題。技巧：前序第一個是根，中序找根的位置，左邊是左子樹、右邊是右子樹，遞迴。
這章記住
- BST = 左小右大的樹，中序走訪會排序。
- 平均 O(log n)、最壞 O(n)（樹歪掉時）。
- 三種走訪（中、前、後序）背順序、會畫。
- 實務用 AVL / 紅黑樹保證平衡。
學習進度只存在你的瀏覽器，不會上傳。