二元搜尋樹 Binary Search Tree, BST

學習目標

理解二元搜尋樹的定義和性質
掌握 BST 的搜尋、插入、刪除操作
理解 BST 的優缺點
了解 BST 的平衡問題

1. 二元搜尋樹的基本概念

1.1 定義

二元搜尋樹 (Binary Search Tree, BST) 是一種特殊的二元樹，滿足以下性質：

左子樹性質: 左子樹中所有節點的值都小於根節點的值
右子樹性質: 右子樹中所有節點的值都大於根節點的值
遞迴性質: 左右子樹也都是二元搜尋樹

1.2 關鍵性質

對於 BST 中的任意節點： - 左子樹的所有節點值 < 當前節點值 - 右子樹的所有節點值 > 當前節點值

1.3 範例

以下是一個有效的 BST：

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

驗證: - 節點 8: 左子樹 (3,1,6,4,7) 都 < 8，右子樹 (10,14,13) 都 > 8 ✓ - 節點 3: 左子樹 (1) < 3，右子樹 (6,4,7) > 3 ✓ - 節點 6: 左子樹 (4) < 6，右子樹 (7) > 6 ✓

2. BST 的搜尋操作

2.1 演算法

Search(root, key):
    如果 root 為空 或 root.data == key:
        返回 root
    如果 key < root.data:
        返回 Search(root.left, key)
    否則:
        返回 Search(root.right, key)

2.2 範例

在以下 BST 中搜尋 6：

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

搜尋過程: 1. 從根節點 8 開始 2. 6 < 8，往左子樹搜尋（節點 3） 3. 6 > 3，往右子樹搜尋（節點 6） 4. 6 == 6，找到！

2.3 C 語言實作

struct Node* search(struct Node* root, int key) {
    // 基礎情況：節點為空或找到
    if (root == NULL || root->data == key)
        return root;

    // 如果 key 小於根，搜尋左子樹
    if (key < root->data)
        return search(root->left, key);

    // 否則搜尋右子樹
    return search(root->right, key);
}

2.4 迭代版本

struct Node* searchIterative(struct Node* root, int key) {
    while (root != NULL && root->data != key) {
        if (key < root->data)
            root = root->left;
        else
            root = root->right;
    }
    return root;
}

2.5 時間複雜度

平均情況: O(log n)
最壞情況: O(n)（當樹退化成鏈表時）

3. BST 的插入操作

3.1 演算法

Insert(root, key):
    如果 root 為空:
        建立新節點，值為 key，返回
    如果 key < root.data:
        root.left = Insert(root.left, key)
    否則如果 key > root.data:
        root.right = Insert(root.right, key)
    返回 root

3.2 範例

在以下 BST 中插入 5：

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

插入過程: 1. 從根節點 8 開始 2. 5 < 8，往左子樹（節點 3） 3. 5 > 3，往右子樹（節點 6） 4. 5 < 6，往左子樹（節點 4） 5. 5 > 4，應該插入到 4 的右子節點 6. 4 的右子節點為空，插入 5

插入後的樹:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13
        \
         5

3.3 C 語言實作

struct Node* insert(struct Node* root, int key) {
    // 如果樹為空，建立新節點
    if (root == NULL) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = key;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }

    // 否則遞迴插入
    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);

    return root;
}

3.4 時間複雜度

平均情況: O(log n)
最壞情況: O(n)

4. BST 的刪除操作

4.1 三種情況

刪除操作需要處理三種情況：

情況 1: 要刪除的節點是葉節點

方法: 直接刪除

範例: 刪除節點 7

刪除前:        刪除後:
    6              6
   / \            / \
  4   7          4  (空)

情況 2: 要刪除的節點只有一個子節點

方法: 用子節點取代該節點

範例: 刪除節點 6（只有左子節點 4）

刪除前:        刪除後:
    6              4
   /
  4

情況 3: 要刪除的節點有兩個子節點

方法: 1. 找到右子樹中的最小值（或左子樹中的最大值） 2. 用該值取代要刪除的節點 3. 刪除該最小值節點

範例: 刪除節點 3

刪除前:
        3
       / \
      1   6
         / \
        4   7

步驟 1: 找到右子樹最小值 4
步驟 2: 用 4 取代 3
步驟 3: 刪除原來的 4（情況 1 或 2）

刪除後:
        4
       / \
      1   6
           \
            7

4.2 演算法

Delete(root, key):
    如果 root 為空，返回 root

    如果 key < root.data:
        root.left = Delete(root.left, key)
    否則如果 key > root.data:
        root.right = Delete(root.right, key)
    否則:  // 找到要刪除的節點
        情況 1: 沒有左子節點
            返回 root.right
        情況 2: 沒有右子節點
            返回 root.left
        情況 3: 有兩個子節點
            temp = 找到右子樹最小值
            root.data = temp.data
            root.right = Delete(root.right, temp.data)

    返回 root

4.3 C 語言實作

// 找到最小值節點
struct Node* minValueNode(struct Node* node) {
    struct Node* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

struct Node* deleteNode(struct Node* root, int key) {
    if (root == NULL) return root;

    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        // 情況 1 和 2: 沒有子節點或只有一個子節點
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }

        // 情況 3: 有兩個子節點
        struct Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

    return root;
}

4.4 時間複雜度

平均情況: O(log n)
最壞情況: O(n)

5. BST 的優點

5.1 搜尋效率

平均情況下，搜尋時間為 O(log n)
比線性搜尋 O(n) 快得多

5.2 插入和刪除效率

平均情況下，插入和刪除時間為 O(log n)
比陣列插入/刪除 O(n) 快

5.3 中序走訪得到排序序列

中序走訪 BST 會得到遞增排序的序列
不需要額外的排序步驟

5.4 動態大小

可以動態插入和刪除元素
不需要預先知道資料大小

6. BST 的缺點

6.1 最壞情況效能

如果插入的資料是已排序的，BST 會退化成鏈表
搜尋、插入、刪除都變成 O(n)

範例: 依序插入 1, 2, 3, 4, 5

6.2 不平衡問題

BST 不保證平衡
可能出現左右子樹高度差異很大的情況

6.3 解決方案

使用平衡二元搜尋樹，如： - AVL 樹: 嚴格平衡 - 紅黑樹: 近似平衡 - B 樹: 用於資料庫

7. BST 的應用

7.1 資料庫索引

許多資料庫使用 BST 或其變體作為索引結構

7.2 符號表

編譯器使用 BST 管理符號表

7.3 優先權佇列

某些優先權佇列的實作使用 BST

7.4 排序

插入所有元素到 BST，然後中序走訪即可得到排序結果

8. 練習題

練習題 1

建立一個 BST，依序插入以下數值：50, 30, 70, 20, 40, 60, 80

解答：

插入過程: 1. 插入 50（根節點） 2. 插入 30（50 的左子節點） 3. 插入 70（50 的右子節點） 4. 插入 20（30 的左子節點） 5. 插入 40（30 的右子節點） 6. 插入 60（70 的左子節點） 7. 插入 80（70 的右子節點）

最終 BST:

        50
       /  \
     30    70
    /  \  /  \
  20  40 60  80

練習題 2

在練習題 1 的 BST 中，刪除節點 30。