【考試向】資料結構筆記（二元搜尋樹）

歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～

（自平衡二元搜尋樹如 AVL Tree 跟紅黑樹會在後續單獨撰寫）

二元搜尋樹（BST, Binary Search Tree）定義

簡單來說，二元搜尋樹就是一棵「自帶排序規則」的二元樹。

在二元搜尋樹中，對於樹上的每一個節點，都必須嚴格遵守以下四條規則：

1. 左子樹中所有節點的值，都小於根節點的值。
2. 右子樹中所有節點的值，都大於根節點的值。
3. 左右子樹本身也必須各自是一棵二元搜尋樹。
4. 每個節點的值都不同。

另外，二元搜尋樹也可以是一個空集合，上述為非空集合所要遵循的規則。

如下圖是一棵二元搜尋樹：

Image Source：二元搜尋樹 - 維基百科，自由的百科全書

右子樹（根節點的右邊：10、14、13）皆大於根節點的值，而至於那個 13，因為他在左子樹，所以得要小於他的樹根 14，符合 BST 的定義。

左子樹（根節點的左邊：3、1、6、4、7）皆小於根節點的值，其下的左右子樹也都符合 BST 的定義。

為什麼需要 BST？

二元搜尋樹（BST）好用的地方在於，他同時兼顧了快速搜尋與彈性插入、刪除，這是其他資料結構各自的弱點。

資料結構	搜尋	插入／刪除
已排序陣列	$O(log n)$	$O(n)$（需搬移元素）
鏈結串列	$O(n)$（需逐一走訪）	$O(1)$
BST（平衡）	$O(log n)$	$O(log n)$

BST 唯一的弱點是：若插入順序不好（例如依序插入 $1, 2, 3, 4, 5$），樹會退化成一條鏈結串列（看起來像是往右邊長成一條偏斜的直線），複雜度變回 $O(n)$。

因此後續衍生出許多自平衡的 BST，例如 AVL Tree、Red-Black Tree 等等，強制維持 $O(logn)$ 的高度。

常見的應用如 C++ 的 STL 容器： std::set 跟 std::map 兩者的底層都是基於紅黑樹（Red-Black Tree）實作的。

BST 的加入與刪除操作

加入操作

加入操作很簡單，只要照著 BST 定義的規則走就可以了。

假設有棵樹長以下這樣，然後我們要加入節點 7：

首先與根節點做比較：7 > 5，所以 7 要往右子樹走。

接著在跟右子樹的根節點 8 比，7 < 8，因此 7 要往左子樹走，且左子樹沒東西，就直接加入進去即可。

練習題

:::info
假設有十筆資料：25, 35, 15, 55, 65, 40, 45, 10, 20, 30，請利用這些資料建立一棵二元搜尋樹。
:::

先看到第一個 25，由於目前二元搜尋樹是空的，因此直接加入成為根節點：

接下來看到 35，因為 35 > 25，所以加入到右子樹那邊去：

接下來 15，因為 15 < 25，所以加到左子樹：

再來看 55，因為 55 > 25，跳到右子樹，接著再跟 35 比較，55 > 35，因此成為 35 的右子節點。

之後就以此類推，最後可以得出以下這棵樹：

刪除操作

情況 1：要刪的是葉節點

直接刪除。

情況 2：要刪除的是非葉節點

在左子樹找一最大的節點，或於右子樹找一個最小的節點，取代要被刪除的節點。

舉例：假設有棵樹長以下這樣，要刪除根節點 50。

可以找右子樹最小的節點 60，把 50 給取代，但此時會有個問題，就是會出現兩個 60，所以要把原本的 60 給他刪掉。

把 60 刪掉會多出一個 65，按照 BST 定義的規則，把他歸順於 70 的左子節點就 ok 了。

C 語言程式實作：二元搜尋樹

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 建立新節點的輔助函式
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct Node* insert(struct Node* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    
    // 小於往左
    // 大於往右
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    // 如果值等於 root->data 不處理直接回傳
    
    return root;
}

// 尋找整棵樹中最小的節點
struct Node* findMin(struct Node* root) {
    // 一路向左走到底
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

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

    // 先在地圖上尋找目標節點
    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } else {

        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root); // 釋放記憶體
            return temp; // 把剩下的小孩（或 NULL）回傳給祖先節點接手
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }

        // 去右子樹找最小的節點
        struct Node* temp = findMin(root->right);
        
        // 覆蓋數值
        root->data = temp->data;
        
        // 到右子樹將原本的節點刪除
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// 中序遍歷
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    struct Node* root = NULL;

    printf("插入節點: 50, 30, 70, 20, 40, 60, 80, 65\n");
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);
    root = insert(root, 65);

    printf("當前的 BST (中序遍歷排序): ");
    inorderTraversal(root);
    printf("\n\n");

    printf("刪除根節點 50\n");
    root = deleteNode(root, 50);

    printf("刪除後的 BST (中序遍歷排序): ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

總整理

定義（4大規則）

BST 是一棵「自帶排序規則」的二元樹（允許為空集合），對於樹上的任何一個節點，都必須嚴格遵守：

1. 左小：左子樹所有節點的值 < 根節點的值。
2. 右大：右子樹所有節點的值 > 根節點的值。
3. 遞迴性：左右子樹本身也必須各自是一棵 BST。
4. 唯一性：每個節點的值都不重複。

為什麼需要 BST？（優缺比較）

BST 結合了已排序陣列搜尋快與鏈結串列新增/刪除快的優點。

資料結構	搜尋	插入／刪除	備註
已排序陣列	$O(logn)$	$O(n)$	需搬移大量元素
鏈結串列	$O(n)$	$O(1)$	需逐一走訪尋找
平衡的 BST	$O(logn)$	$O(logn)$	兼顧兩者優勢

致命弱點（退化問題）：若插入順序極端（例如依序插入 1, 2, 3, 4, 5），樹會往單邊長，退化成類似鏈結串列的直線，此時所有操作的時間複雜度都會跌回 $O(n)$。

解決方案：發展出自平衡的 BST（強制維持 $O(\log n)$ 的樹高），如 AVL Tree、紅黑樹（Red-Black Tree）。

應用：C++ STL 中的 std::set 與 std::map 底層即是紅黑樹。

基本操作邏輯

1. 新增（Insert）
   • 從根節點開始比較：
     • 比節點小 -> 往左找。
     • 比節點大 -> 往右找。
     • 一直走到「空位（無子節點）」時，直接放入該位置。
2. 刪除（Delete）
   • 情況 A（要刪除的是葉節點）：
     • 最底層沒有子節點，直接刪除即可。
   • 情況 B（要刪除的是非葉節點）：
     • 為了維持 BST 的大小規則，必須找一個替身來補位。
     • 做法：在左子樹中找最大值或右子樹中找最小值來取代該節點。
     • 後續處理：將替身上位後，把替身本身的節點刪除（若該替身底下還有子節點，則依 BST 規則將其順勢往上接合）。