Tree · 03 / 07

BST二元搜尋樹

插入、刪除、驗證、中序即有序。

用在：有序集合、範圍查詢、資料庫索引的原型

時間複雜度O(h)

空間複雜度O(h)

難度進階

前置知識Binary Tree Basics、Traversal、Binary Search

01為什麼需要它

既要快速查找，又要保持有序

雜湊表查找 O(1)，但問「比 50 大的最小鍵是誰」「範圍在 30 到 70 之間的有哪些」它答不出來；有序陣列能答，但插入要搬移 O(n)。

為什麼用它BST 兩者兼顧：查找、插入、刪除都是 O(h)，而且中序走訪就是有序序列，範圍查詢、前驅後繼都是自然的操作。Java 的 TreeMap、C++ 的 std::map、Redis 的 sorted set 都是這個家族。

資料庫索引的原型

資料庫要在幾千萬筆資料裡找 WHERE age BETWEEN 30 AND 40，還要隨時能插入新資料。

為什麼用它索引本質上是搜尋樹。實際用的 B-tree 是 BST 的多路版本，讓每個節點塞滿一個磁碟區塊，但「往左小、往右大、中序有序」的思路完全相同。

為什麼「只跟父節點比」是錯的

驗證一棵樹是不是 BST，很多人只檢查每個節點比左子大、比右子小，結果被一個藏在深處的節點打臉。

為什麼用它BST 的規則是整棵左子樹都小於自己，不只是左子節點。正確做法是把祖先給的上下界一路往下傳。這是理解 BST 定義最好的一道題。

看到這些關鍵字就想到它：有序集合、範圍查詢、前驅／後繼、第 k 小、既要插入又要查詢、中序有序。

02核心概念

二元搜尋樹只加一條規則：對每個節點，整棵左子樹的值都比它小，整棵右子樹的值都比它大。注意是整棵子樹，不只是直接的子節點。這條規則讓每次比較都能丟掉一整棵子樹：目標比自己小就只看左邊，比自己大就只看右邊，和二分搜尋是同一個想法。

搜尋從根開始往下比；插入就是搜尋到空位，把新節點掛在那裡，所以新節點一定是葉。刪除要分三種情況：沒有子節點直接拿掉；一個子節點就讓子節點頂上；兩個子節點時不能直接拿掉，找中序後繼（右子樹最左邊的節點，它一定沒有左子節點），把它的值複製過來，再去右子樹刪掉後繼。這樣左 < 自己 < 右依然成立。

所有操作的成本都是樹高 h。隨機順序插入時 h 大約是 log n，但如果依序插入已排序的資料，樹會退化成一條鏈，h = n，BST 就變成鏈結串列。這就是下一篇平衡樹要解決的問題。

中序走訪就是排序結果，這是 BST 最常被利用的性質。找第 k 小就是中序的第 k 個；驗證 BST 可以檢查中序是否嚴格遞增；範圍查詢就是中序加上「超出範圍就不往那邊走」的剪枝。

03演算法步驟

1搜尋 / 插入：從根開始，目標小於節點往左、大於往右。搜尋碰到相等就回傳，碰到空就是不存在；插入碰到空就放在那裡。
2刪除：先找到節點。0 或 1 個子節點，用那個子節點（或空）取代自己。
32 個子節點：往右子樹一路往左找到後繼，把後繼的值複製到自己，然後遞迴去右子樹刪除後繼（它最多只有一個右子節點，落入前一種情況）。
4驗證：帶著 (lo, hi) 範圍往下遞迴，往左時把 hi 換成自己，往右時把 lo 換成自己。每個節點必須嚴格落在範圍內。
5範圍查詢 / 第 k 小：用中序走訪，加上「值已經比 lo 小就不往左、比 hi 大就不往右」的剪枝，或計數到 k 就停。

04互動示範

依序插入七個值建樹，接著搜尋一個存在與一個不存在的值，再插入 45，最後刪除有兩個子節點的 30，看後繼 40 怎麼補上來。

開始插入 50, 30, 70, 20, 40, 60, 80 → 搜尋 60、65 → 插入 45 → 刪除 30

步驟 0/32二元搜尋樹的規則：左子樹全部 < 節點 < 右子樹全部。從空樹開始。

05程式碼

搜尋、插入、刪除三個基本操作，加上最常考的驗證與範圍查詢。刪除的遞迴寫法「回傳這棵子樹的新根」，讓父節點不用特別處理。

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


def search(node, key):
    """每次比較砍掉一整棵子樹。O(h)"""
    while node and node.key != key:
        node = node.left if key < node.key else node.right
    return node


def insert(node, key):
    """遞迴版：回傳插入後這棵子樹的根"""
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node                       # 相等就不重複插入


def delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        # 找到了，分三種情況
        if node.left is None:         # 0 或 1 個子節點：直接接上另一邊
            return node.right
        if node.right is None:
            return node.left
        succ = node.right             # 2 個子節點：找右子樹最小值（中序後繼）
        while succ.left:
            succ = succ.left
        node.key = succ.key           # 用後繼的值取代自己
        node.right = delete(node.right, succ.key)   # 再去右子樹刪掉後繼
    return node


def is_valid_bst(node, lo=float("-inf"), hi=float("inf")):
    """驗證：每個節點都要在祖先給的範圍內，只跟父節點比是不夠的"""
    if node is None:
        return True
    if not (lo < node.key < hi):
        return False
    return is_valid_bst(node.left, lo, node.key) and is_valid_bst(node.right, node.key, hi)


def range_query(node, lo, hi, out):
    """列出 [lo, hi] 內的所有鍵：中序走訪加剪枝"""
    if node is None:
        return
    if lo < node.key:
        range_query(node.left, lo, hi, out)
    if lo <= node.key <= hi:
        out.append(node.key)
    if node.key < hi:
        range_query(node.right, lo, hi, out)

06練習題

LeetCode 700Search in a Binary Search TreeEasy
LeetCode 701Insert into a Binary Search TreeMedium
LeetCode 450Delete Node in a BSTMedium
LeetCode 98Validate Binary Search TreeMedium
LeetCode 230Kth Smallest Element in a BSTMedium
LeetCode 235Lowest Common Ancestor of a BSTMedium
LeetCode 108Convert Sorted Array to BST（建一棵平衡的）Easy

上一篇Traversal 下一篇Balanced BST