跳轉至

建立 2026-11-12 更新 2026-11-12 HL only

樹、集合與雜湊表

樹、集合與雜湊表是 B4 中的非線性抽象資料型別：二元搜尋樹（Binary Search Tree, BST）讓資料保持排序並能快速搜尋，集合（set）處理不重複元素與集合運算，雜湊表（hash table）則用雜湊函式達到平均 O(1) 的查詢速度。本頁屬於 HL 專屬的 B4 單元。

HL 專屬內容

本頁屬於 B4.1，只有 HL 需要學。

樹的基本名詞

名詞 意義
根（root） 最上層的節點，沒有父節點
父節點／子節點（parent／child） 直接相連的上下層節點
葉節點（leaf） 沒有子節點的節點
子樹（subtree） 某節點與其所有後代
高度（height） 從根到最深葉節點的邊數
二元樹（binary tree） 每個節點最多兩個子節點

二元搜尋樹如何保持排序？

BST 的規則：對每個節點，左子樹所有值 < 節點值 < 右子樹所有值。依序插入 50, 30, 70, 20, 40, 60, 80 得到：

flowchart TD
    A((50)) --> B((30))
    A --> C((70))
    B --> D((20))
    B --> E((40))
    C --> F((60))
    C --> G((80))
  • 搜尋：從根開始，比目標小往左、比目標大往右。平衡時每一步排除一半，O(log n)。
  • 最差情況：依序插入已排序資料（10, 20, 30, …），樹退化成一條鏈，搜尋變成 O(n)。實務上用自我平衡樹（AVL 樹、紅黑樹）避免。
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


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

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return TreeNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node                      # 重複值不插入

    def contains(self, value):
        cur = self.root
        while cur is not None:
            if value == cur.value:
                return True
            cur = cur.left if value < cur.value else cur.right
        return False

樹有哪三種走訪方式？

走訪（traversal）是依特定順序拜訪每個節點，三種深度優先走訪的差別在「何時處理根節點」：

走訪 順序 上圖結果 用途
前序（pre-order） 根 → 左 → 右 50 30 20 40 70 60 80 複製樹、輸出樹結構
中序（in-order） 左 → 根 → 右 20 30 40 50 60 70 80 BST 依大小排序輸出
後序（post-order） 左 → 右 → 根 20 40 30 60 80 70 50 刪除整棵樹、計算運算式樹 
def in_order(node):
    if node is None:
        return
    in_order(node.left)
    print(node.value, end=" ")
    in_order(node.right)

如何刪除 BST 節點？

  1. 葉節點：直接移除。
  2. 只有一個子節點：讓子節點取代它的位置。
  3. 有兩個子節點：用 中序後繼（in-order successor，右子樹中最小的值） 取代它，再刪除那個後繼節點。

集合有哪些運算？

集合（set）是 不含重複元素、沒有順序 的 ADT，主要操作：

運算 意義 Python
成員判斷 x 是否在集合中 x in A
聯集（union） 在 A 或 B A \| B
交集（intersection） 同時在 A 和 B A & B
差集（difference） 在 A 但不在 B A - B
子集（subset） A 的元素都在 B A <= B 
cs = {"Amy", "Ben", "Chris"}
math = {"Ben", "Dora"}
print(cs & math)    # {'Ben'}：同時修兩科
print(cs - math)    # {'Amy', 'Chris'}：只修 CS

集合通常用雜湊表實作，成員判斷平均 O(1)；用 BST 實作則能依序列出元素。

雜湊表如何快速查詢？

雜湊表用 雜湊函式（hash function） 把鍵（key）轉成陣列索引，直接到該位置存取資料：

index = hash(key) mod 表格大小

例如表格大小 10，用學號除以 10 的餘數當索引：學號 1234 → 索引 4。

碰撞怎麼處理？

兩個不同的鍵算出同一個索引稱為 碰撞（collision），例如 1234 與 5674 都對應索引 4。

  • 鏈結法（chaining）：每個位置放一個串列，碰撞的資料串在同一個串列中。
  • 開放定址法（open addressing）／線性探測（linear probing）：位置被佔就往下一格找空位，搜尋時也依同樣規則往下找。
class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]    # 鏈結法

    def _hash(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value        # 已存在就更新
                return
        bucket.append([key, value])

    def get(self, key):
        for k, v in self.buckets[self._hash(key)]:
            if k == key:
                return v
        return None

好的雜湊函式要 計算快、分布均勻。負載因子（load factor） = 資料筆數 ÷ 表格大小；負載因子太高時碰撞增加，通常會擴大表格並重新雜湊（rehash）。

各結構的效率比較

操作 未排序陣列 已排序陣列 平衡 BST 雜湊表（平均）
搜尋 O(n) O(log n) O(log n) O(1)
插入 O(1)（尾端） O(n) O(log n) O(1)
依序輸出 需先排序 O(n) O(n) 需先排序

推薦影音

樹與二元搜尋樹（HackerRank）

簡述：說明二元搜尋樹的插入、搜尋與三種走訪方式，並以 Java 實作，對應本頁 BST 與走訪兩節。

雜湊表（HackerRank）

簡述：說明雜湊函式如何把鍵對應到索引、碰撞發生的原因，以及用鏈結法處理碰撞，對應本頁雜湊表一節。

雜湊演算法與安全（Computerphile）

簡述：從另一個角度介紹雜湊函式在資訊安全中的應用（密碼儲存、檔案完整性），可連結 A2.4 網路安全。

練習題

練習 1：建立 BST

依序插入 45, 20, 60, 10, 30, 55, 70, 25，畫出 BST，並寫出中序與前序走訪結果。

參考答案

樹：45 的左子為 20、右子為 60；20 的左子 10、右子 30；30 的左子 25；60 的左子 55、右子 70。

中序：10 20 25 30 45 55 60 70；前序：45 20 10 30 25 60 55 70。

練習 2：BST 高度

寫一個遞迴函式 height(node) 計算 BST 的高度（空樹高度為 −1，只有根為 0）。

參考答案 
def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))
練習 3：刪除節點

在練習 1 的樹中刪除 20，應用哪個值取代它？刪除後 20 的位置變成什麼？

參考答案

20 有兩個子節點，用中序後繼（右子樹 30 中最小的值）25 取代。刪除後該位置為 25，左子為 10、右子為 30，30 不再有左子節點。

練習 4：雜湊與碰撞

表格大小 7，雜湊函式為 key mod 7，使用線性探測。依序插入 15, 22, 8, 29，寫出每個鍵存放的索引。

參考答案

15 mod 7 = 1 → 索引 1。22 mod 7 = 1，碰撞 → 索引 2。8 mod 7 = 1，碰撞 → 2 被佔 → 索引 3。29 mod 7 = 1，碰撞 → 1、2、3 都被佔 → 索引 4。

練習 5：集合運算

A = {1, 2, 3, 4}、B = {3, 4, 5}，寫出 A ∪ B、A ∩ B、A − B、B − A。

參考答案

A ∪ B = {1, 2, 3, 4, 5}；A ∩ B = {3, 4}；A − B = {1, 2}；B − A = {5}。