我們昨天介紹了二元樹的結構、分類和走訪，今天要來看二元搜尋樹 !

什麼是二元搜尋樹(Binary Search Tree)?

二元搜尋樹(BST)就是有排序規則的二元樹，樹中的每個節點，左子樹的值都比他小或相等，右子樹的值都比他大

以節點 9 為例：左子樹（7、2、8）都比 9 小，右子樹（10、14）都比 9 大
這個規則不只對根節點成立，對樹裡的每一個節點都成立
例如 : 以 7 為根來看，它的左子樹 2 比 8 小，右子樹 10 比 14 大，同樣的規則套用在每一層

為什麼需要 BST？

二元搜尋樹每次比較都能排除大約一半的剩餘節點，所以在尋找、插入、刪除資料可以節省很多時間

假設有以下資料：

2 7 8 9 10 14

如果用陣列儲存，要搜尋某個數字最壞情況要把每個數字都掃過一次 O(n)
但如果資料用 BST 儲存 ：

假設要找 8 :

1. 8 < 9 往左走
2. 8 > 7往右走
   找到 8

節點結構

跟昨天的二元樹一樣：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) {
        val = x;
        left = nullptr;
        right = nullptr;
    }
};

插入(Insert)

插入新值時，從根節點(root)開始比較：比新值大就往左走，比新值小就往右走，直到找到空位為止

#include<iostream>
using namespace std;
TreeNode* insert(TreeNode* node, int val) {
    if (node == nullptr) {
        return new TreeNode(val);   // 找到空位
    }
    if (val < node->val) {
        node->left = insert(node->left, val); // 比較小,往左子樹插入
    } else {
        node->right = insert(node->right, val);//比較大，往右子樹插入
    }
    return node;
}

完整程式碼 :

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) {
        val = x;
        left = nullptr;
        right = nullptr;
    }
};

// 插入節點
TreeNode* insert(TreeNode* node, int val) {
    if (node == nullptr) {
        return new TreeNode(val); // 找到空位
    }
    if (val < node->val) {
        node->left = insert(node->left, val); // 比較小，往左子樹插入
    } else {
        node->right = insert(node->right, val); // 比較大，往右子樹插入
    }
    return node;
}

// 中序走訪
void inorder(TreeNode* node) {
    if (node == nullptr) return;
    inorder(node->left);
    cout << node->val << " ";
    inorder(node->right);
}

int main() {
    TreeNode* root = nullptr;
    root = insert(root, 9);
    root = insert(root, 7);
    root = insert(root, 10);
    root = insert(root, 2);
    root = insert(root, 8);
    root = insert(root, 14);

    inorder(root);
    cout << endl;

    return 0;
}

搜尋(Search)

搜尋的概念跟插入很像，一樣是比較大小決定往左還是往右走：

bool search(TreeNode* node, int target) {
    if (node == nullptr) {
        return false;         // 走到底都沒找到,不存在
    }
    if (node->val == target) {
        return true;          // 找到了
    }
    if (target < node->val) {
        return search(node->left, target);   // 比較小,往左找
    } else {
        return search(node->right, target);  // 比較大,往右找
    }
}

完整程式碼 :

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) {
        val = x;
        left = nullptr;
        right = nullptr;
    }
};

// 插入節點
TreeNode* insert(TreeNode* node, int val) {
    if (node == nullptr) {
        return new TreeNode(val); // 找到空位
    }
    if (val < node->val) {
        node->left = insert(node->left, val); // 比較小，往左子樹插入
    } else {
        node->right = insert(node->right, val); // 比較大，往右子樹插入
    }
    return node;
}

// 搜尋節點
bool search(TreeNode* node, int target) {
    if (node == nullptr) {
        return false;         // 走到底都沒找到，不存在
    }
    if (node->val == target) {
        return true;          // 找到了
    }
    if (target < node->val) {
        return search(node->left, target);   // 比較小，往左找
    } else {
        return search(node->right, target);  // 比較大，往右找
    }
}

// 中序走訪
void inorder(TreeNode* node) {
    if (node == nullptr) return;
    inorder(node->left);
    cout << node->val << " ";
    inorder(node->right);
}

int main() {
    TreeNode* root = nullptr;
    root = insert(root, 9);
    root = insert(root, 7);
    root = insert(root, 10);
    root = insert(root, 2);
    root = insert(root, 8);
    root = insert(root, 14);

    cout << "走訪結果: ";
    inorder(root);
    cout << endl;

    // test
    int target1 = 8;
    int target2 = 5;

    if (search(root, target1)) {
        cout << target1 << ": 找到" << endl;
    } else {
        cout << target1 << ": 沒找到" << endl;
    }

    if (search(root, target2)) {
        cout << target2 << ": 找到" << endl;
    } else {
        cout <<target2 << ": 沒找到" << endl;
    }

    return 0;
}

走訪結果: 2 7 8 9 10 14 
8: 找到
5: 沒找到

複雜度

假設樹的高度為 h：

樹的形狀會影響效率

最佳情況

如果照 9、7、10、2、8、14的順序插入，左右兩邊會比較平衡，高度會較低
(O(log n))
樹接近平衡：

最壞情況

如果資料排序後插入 2、7、8、9、10、14
會變成這樣
因為每個新值都比前一個大，全部都往右子樹插入
樹會退化成單向鏈結串列，高度為n-1

BST須滿足 左子樹 < 根節點 < 右子樹
平均情況下 BST 的插入、搜尋效率是 O(log n)，比起一般二元樹（沒有排序，搜尋需要 O(n) 逐一比對）快很多
但這個優勢建立在樹的形狀平衡的前提上，如果插入順序恰好讓樹退化成鏈結串列，優勢就會消失

參考資料和書籍

1. https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9
2. https://www.geeksforgeeks.org/dsa/binary-search-tree-data-structure/
3. https://guide.ntucpc.org/BasicDataStructure/binary_tree/
4. https://hackmd.io/@LukeTseng/BkK5MULiWe