二元搜尋樹（BST）教學：原理、程式碼與時間複雜度

二元搜尋樹解決什麼問題

排序過的陣列可以快速做二分搜尋，但插入新元素時，後面所有元素都得搬移。雜湊表的查找與插入都很快，卻不保留順序，所以無法回答「比 42 大的最小鍵是什麼？」或「列出 10 到 20 之間的所有鍵」這類問題。二元搜尋樹讓鍵保持排序，同時仍能快速插入與刪除。它是有序映射與集合的基礎，例如 Java 的 TreeMap 和 C++ 的 std::map，這些實作使用的是自平衡的變體。

用白話說明規則

每個節點有一個鍵、一個可有可無的左子節點，以及一個可有可無的右子節點。對每個節點而言：左子樹的所有鍵都比它小，右子樹的所有鍵都比它大。要找某個鍵，從根節點開始比較：鍵比較小就往左，比較大就往右，相等就停下，或是走出樹外也停下。

實例演練：建立並搜尋一棵樹

依序插入 8、3、10、1、6、14、4。每個新鍵都從根節點往下走，在走出樹外的位置成為葉節點。

搜尋 4 時依序和 8、3、6、4 比較：在有七個鍵的樹中比較四次。搜尋 7 時依序和 8、3、6 比較，然後發現 6 沒有右子節點，所以 7 不在樹中。

Python 實作

插入與搜尋都是簡短的迴圈。刪除有三種情況：節點沒有子節點（直接移除）、有一個子節點（用該子節點取代它），或有兩個子節點（複製它的中序後繼節點，也就是右子樹中最小的鍵，然後刪除那個後繼節點）。

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored
def contains(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None
def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root
def inorder(root):
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []

root = None
for k in [8, 3, 10, 1, 6, 14, 4]:
    root = insert(root, k)
print(inorder(root))                 # [1, 3, 4, 6, 8, 10, 14]
print(contains(root, 4), contains(root, 7))  # True False
root = delete(root, 3)               # node with two children
print(inorder(root), root.left.key)  # [1, 4, 6, 8, 10, 14] 4

時間與空間複雜度

最差情況是真實存在的，不只是理論：把已排序的鍵（1, 2, 3, ...）依序插入一棵普通的 BST，每個節點都只會有右子節點，樹就變成了鏈結串列。隨機的插入順序則可得到期望高度 O(log n)。

平衡變體與常見錯誤

自平衡樹在插入與刪除後透過旋轉重整結構，讓高度維持在 O(log n)。

• 只檢查父節點與子節點就驗證 BST。應該改為向下傳遞合法的 (low, high) 範圍。
• 忘記從遞迴的插入與刪除回傳（可能是新的）根節點，導致修改遺失。
• 在退化的樹上遞迴過深：Python 預設的遞迴上限約為 1000，所以 5000 個節點的鏈會讓遞迴程式崩潰。請改用迴圈，或讓樹保持平衡。
• 沒有明確定義重複鍵的處理方式：要決定重複的鍵是被忽略、被計數，還是一律放在同一側。

何時使用 BST，以及常見的面試題

當你需要有序資料，並且頻繁插入與刪除時，請使用平衡的 BST：範圍查詢、floor 與 ceiling 查找、名次統計，或依排序順序迭代。如果只需要精確的鍵查找，請用雜湊表。Python 標準函式庫沒有樹形映射；常見的選擇是對小型或大多不變的資料使用排序串列搭配 bisect 模組，或使用第三方套件 sortedcontainers。

常見的面試題：驗證 BST、找第 k 小的元素（中序走訪）、最低共同祖先、把排序陣列轉成平衡 BST（選中間的元素當根），以及找出某個節點的中序後繼節點。