跳轉到

5.2 二元搜尋樹BST#

概念說明#

二元搜尋樹（BST） 在每個節點上維護不變式：左子樹所有值 < 節點值 < 右子樹所有值。這條規則讓每次搜尋都能「比較一次、排除一半」——與二元搜尋同樣的邏輯，只是資料結構是樹而非陣列，因此插入刪除不需要搬移整段資料。

BST 同時提供三種能力：(1) O(log n) 的搜尋/插入/刪除（平衡時）；(2) 中序走訪得到排序序列；(3) 高效的範圍查詢與「找前驅/後繼」。這是雜湊表做不到的——雜湊表是無序的。

操作步驟#

  1. search(x)：從根出發，x 較小往左、較大往右；遇到 None 表示不存在。
  2. insert(x)：同樣往下走，走到 None 時就是新節點的位置。
  3. min / max：一路往左 / 一路往右。
  4. delete(x)：三種情況——
  5. 葉節點：直接移除。
  6. 只有一個小孩：用小孩頂替自己。
  7. 有兩個小孩：找右子樹的最小節點（後繼者），把它的值搬過來，再刪除後繼者原本的位置（後繼者至多一個小孩，轉化為前兩種情況）。

Python 實作#

class BST:
    def __init__(self):
        self.root = None

    def search(self, x):
        node = self.root
        while node:
            if x == node.val:
                return node
            node = node.left if x < node.val else node.right
        return None

    def insert(self, x):
        if self.root is None:
            self.root = TreeNode(x)
            return
        node = self.root
        while True:
            if x < node.val:
                if node.left is None:
                    node.left = TreeNode(x)
                    return
                node = node.left
            elif x > node.val:
                if node.right is None:
                    node.right = TreeNode(x)
                    return
                node = node.right
            else:
                return                        # 重複值不插入

    def delete(self, x):
        self.root = self._delete(self.root, x)

    def _delete(self, node, x):
        if node is None:
            return None
        if x < node.val:
            node.left = self._delete(node.left, x)
        elif x > node.val:
            node.right = self._delete(node.right, x)
        else:                                  # 找到了
            if node.left is None:  return node.right
            if node.right is None: return node.left
            succ = node.right                  # 右子樹最小者
            while succ.left:
                succ = succ.left
            node.val = succ.val
            node.right = self._delete(node.right, succ.val)
        return node

    def in_order(self):
        out = []
        def walk(n):
            if n:
                walk(n.left); out.append(n.val); walk(n.right)
        walk(self.root)
        return out

# 動手玩
t = BST()
for x in [50, 30, 70, 20, 40, 60, 80]:
    t.insert(x)
print(t.in_order())              # [20, 30, 40, 50, 60, 70, 80]（自動有序）
print(t.search(40) is not None)  # True
t.delete(30)                     # 刪有兩個小孩的節點
print(t.in_order())              # [20, 40, 50, 60, 70, 80]

退化問題#

按 1, 2, 3, 4, 5 的順序插入，BST 會變成一條向右的鏈，樹高 = n，所有操作退化为 O(n)——搜尋變成線性掃描。這是 BST 的致命傷：效能取決於插入順序。解法是「自動維持平衡」，即第6章的 AVL 樹與紅黑樹。順帶一提：把亂序資料插入 BST 得到的樹，與對該資料做快排的比較過程同構，期望深度仍是 O(log n)。

複雜度分析#

操作 平均（隨機插入） 最壞（退化成鏈）
search / insert / delete O(log n) O(n)
中序走訪 O(n) O(n)

練習#

  1. 實作 range_query(lo, hi)：回傳所有落在 [lo, hi] 的值，要求只拜訪必要子樹（剪枝），時間 O(h + k)。
  2. 實作 kth_smallest(k)：第 k 小的元素。提示：中序走訪數到第 k 個，或讓節點維護「子樹大小」。
  3. 給一串列，統計「依插入順序建 BST 後的樹高」，分別用升冪、降冪、亂序資料各測 1000 筆，印出樹高並與 log₂1000 ≈ 10 比較。