二元搜尋樹

🎯 什麼情境該想到我

當你「既要有序、又要能動態增刪」的時候——雜湊表給你 $O (1)$ 但沒有順序，排序過的 slice 有順序但插入要 $O (n)$ 。
★ 但純 BST 在實務上幾乎不能直接用——它會退化。理解它的價值在於它是紅黑樹、B 樹、跳表的共同基礎。

⚙️ 怎麼用（機制與推導）

性質

對任一節點：左子樹所有值 < 它 < 右子樹所有值。

        8
      /   \
     3     10
    / \      \
   1   6      14
      / \     /
     4   7   13

★ 中序走訪（左 → 根 → 右）會得到排序好的序列 —— 這是 BST 一切能力的來源。

type Node struct {
    key         int
    left, right *Node
}
 
func (n *Node) Search(k int) *Node {
    for n != nil && n.key != k {
        if k < n.key { n = n.left } else { n = n.right }
    }
    return n
}
 
func Insert(n *Node, k int) *Node {
    if n == nil { return &Node{key: k} }
    if k < n.key {
        n.left = Insert(n.left, k)
    } else if k > n.key {
        n.right = Insert(n.right, k)
    }
    return n                     // 相等：視需求決定忽略或計數
}

★ 刪除：三種情況（必考）

① 葉節點           → 直接移除
② 只有一個子節點   → 用該子節點取代自己
③ ★ 有兩個子節點  → 用「中序後繼」（右子樹的最小值）取代自己的值，
                      再去右子樹刪掉那個後繼節點

為什麼用中序後繼：它是「所有比我大的值裡最小的那個」，
放到我的位置後，BST 性質對左右子樹都仍然成立。
（用「中序前驅」——左子樹的最大值——也一樣對。）

★ 而且中序後繼必定沒有左子節點（否則那個左子會更小），所以刪除它必定落入情況 ① 或 ②——遞迴不會無限下去。

func Delete(n *Node, k int) *Node {
    if n == nil { return nil }
    switch {
    case k < n.key:
        n.left = Delete(n.left, k)
    case k > n.key:
        n.right = Delete(n.right, k)
    default:
        if n.left == nil  { return n.right }   // ① ②
        if n.right == nil { return n.left }
        succ := n.right                        // ③ 找中序後繼
        for succ.left != nil { succ = succ.left }
        n.key = succ.key
        n.right = Delete(n.right, succ.key)
    }
    return n
}

支援的操作（這是它勝過雜湊表的地方）

操作	複雜度（平衡時）	雜湊表做得到嗎
查找／插入／刪除	$O (h)$	✅ $O (1)$
最小／最大	$O (h)$ （一路往左／右）	❌ $O (n)$
前驅／後繼	$O (h)$	❌
★ 範圍查詢 `[a, b]`	$O (h + k)$	❌
★ 有序走訪	$O (n)$	❌
第 k 小（加 size 欄位）	$O (h)$	❌

★ 致命問題：退化

所有操作都是 $O (h)$ ，而 $h$ 不保證是 $O (lo g n)$ 。

依序插入 1, 2, 3, 4, 5：

    1
     \
      2
       \
        3        ← ★ 退化成鏈結串列，h = n，所有操作變成 O(n)
         \
          4
           \
            5

而「已排序的輸入」在真實系統裡極其常見（資料庫匯出、遞增 ID、時間序列）——
所以純 BST 不是「偶爾會慢」，是「在最常見的輸入上一定會慢」。

情況	高度
完美平衡	$⌊ lo g_{2} n ⌋$
隨機插入（期望）	$O (lo g n)$
★ 已排序插入	$n - 1$

★ 這就是紅黑樹、AVL 樹、Treap、跳表存在的全部理由：用旋轉或隨機化強制維持 $O (lo g n)$ 的高度。

🧪 我實際套用的紀錄

（待填）

⚠️ 注意 / 什麼時候不適用

★ 不要在生產環境用純 BST。要嘛用自平衡版本，要嘛用別的結構。

★ Go 標準庫沒有有序 map/set。實務選項：

需求	做法
資料不常變	排序過的 slice + 二分搜尋（`slices.BinarySearch`）——最簡單且快取友善，多數情況的正解
頻繁增刪且要有序	第三方 B-tree（如 `google/btree`）或跳表
只要最小／最大	二元堆積（`container/heap`）

快取不友善。每個節點獨立配置，走訪時跳來跳去（同鏈結串列的問題）。
這是 B 樹在資料庫與檔案系統勝出的原因——一個節點裝很多鍵，一次 I/O 讀一整塊。
遞迴實作在退化時會爆堆疊。深度不可控時用迴圈版。
相等鍵要先想清楚：忽略？計數？掛成串列？不決定會產生微妙的 bug。
只要查找不要順序 → 用雜湊表， $O (1)$ 勝過 $O (lo g n)$ 。

🔗 相關工具

紅黑樹 —— 自平衡版本，解掉退化問題
雜湊表 —— 對照：更快但沒有順序
二分搜尋 —— 靜態資料的替代方案（排序 slice）
二元堆積 —— 只要極值時更輕量
鏈結串列 —— 退化後的樣子，以及共同的快取問題
工具-資料結構的選擇 —— 決策層
演算法導論

Quartz 5

Explorer