二叉搜尋樹：雙刃劍

演算法背後的故事：岔路口

想像妳站在一個岔路口。路標上寫著一個數字，比如 50。

• 妳正在尋找 30 號房子。
• 路標上寫著：「較小的數字走左邊。較大的數字走右邊。」

於是妳向左走。妳遇到了另一個岔路口，上面寫著 25。

• 30 比 25 大。妳向右走。
• 妳到達了 30 號房子。

這就是 二叉搜尋樹 (BST)。它將「搜尋」這一行為轉化為一系列簡單的 是/否 決策。妳不需要走過 1000 棟房子，妳只需要做大約 10 次決定。

為什麼需要它？

BST 是以下技術的理論基礎：

• 資料庫： 如何在不掃描整張表的情況下找到一個用戶 ID？
• Set/Map： 以有序的方式儲存唯一項。
• 自動補全： 雖然 Trie 更好，但 BST 可以處理範圍查詢，如「找出所有年齡 > 18 且 < 25 的用戶」。

演算法是如何「思考」的

這個演算法是一個守門人。

1. 搜尋： 將目標與當前節點比較。如果小，向左。如果大，向右。如果相等，找到了。
2. 插入： 搜尋直到妳撞上死胡同 (None)。把新節點放在那裡。
3. 刪除： 最棘手的部分。
   • 如果是葉子：直接剪掉。
   • 如果有一個孩子：讓孩子接班。
   • 如果有兩個孩子：找到「繼承人」（右子樹中最小的節點），用它替換目標，然後刪除那個繼承人。

工程決策：致命缺陷

BST 有一個阿基里斯之踵：輸入順序。

• 場景 A (隨機)： 妳插入 [5, 3, 7, 2, 4]。樹很茂盛且平衡。高度約為 $\log N$。搜尋很快。
• 場景 B (有序)： 妳插入 [1, 2, 3, 4, 5]。
  • 1 成為根。
  • 2 跑到 1 的右邊。
  • 3 跑到 2 的右邊。
  • … 這棵樹變成了一條線。高度是 $N$。搜尋很慢 ($O(N)$)。

這就是為什麼原始 BST 在生產環境中很少使用。我們使用她們更聰明的表親：AVL 或 紅黑樹。

實作參考 (Python)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root

def search(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return search(root.left, val)
    return search(root.right, val)

# 使用範例
root = None
values = [50, 30, 20, 40, 70, 60, 80]
for v in values:
    root = insert(root, v)

result = search(root, 60)
print(f"找到: {result.val if result else 'None'}")

小結

BST 教會我們：結構取決於歷史。如果數據以良好的順序到達，結構就很堅固。如果數據以糟糕的順序到達，結構就會崩塌。它提醒我們，在工程中，我們不能依賴運氣；我們需要機制（平衡）來強制執行秩序，無論外界多麼混亂。