二元搜尋樹核心特性

二元樹平均深度為 O(log N)。二元搜尋樹在二元樹基礎上增加有序性質：對任意節點 X，左子樹所有鍵值 < X，右子樹所有鍵值 > X。此性質保證中序遍歷產生遞增序列，支援高效查找、插入、刪除操作。

節點資料結構設計

template <typename Comparable>
struct BinaryNode {
    Comparable element;        // 節點鍵值
    BinaryNode* left;          // 左子節點
    BinaryNode* right;         // 右子節點
    int count;                 // 相同鍵值出現次數（支援重複鍵）

    BinaryNode(const Comparable& e, BinaryNode* lt, BinaryNode* rt, int c)
        : element(e), left(lt), right(rt), count(c) {}
};

核心介面設計

template <typename Comparable>
class BinarySearchTree {
public:
    BinarySearchTree();                              // 預設建構
    BinarySearchTree(const vector<int>& v);        // 由向量建構
    BinarySearchTree(const BinarySearchTree& rhs); // 拷貝建構
    ~BinarySearchTree();                             // 解構函數

    const BinarySearchTree& operator=(const BinarySearchTree& rhs); // 賦值運算子

    void preOrderPrintTree() const;  // 遞增序列輸出（中序遍歷）
    void inOrderPrintTree() const;   // 遞減序列輸出（逆中序遍歷）

    Comparable findMin() const;      // 最小值
    Comparable findMax() const;      // 最大值
    bool contains(const Comparable& x) const; // 查找
    bool isEmpty() const;            // 空樹判斷
    void makeEmpty();                // 清空樹
    void insert(const Comparable& x); // 插入
    void remove(const Comparable& x); // 刪除

private:
    BinaryNode<Comparable>* root;
    // 內部遞迴輔助函數...
};

關鍵演算法深度解析

刪除操作：三種情況處理

template <typename Comparable>
void BinarySearchTree<Comparable>::remove(const Comparable& x, BinaryNode*& t) const {
    if (t == nullptr) return;                    // 空樹

    if (x < t->element)
        remove(x, t->left);                      // 往左子樹
    else if (x > t->element)
        remove(x, t->right);                     // 往右子樹
    else if (t->left != nullptr && t->right != nullptr) { // 兩個子節點
        t->element = findMin(t->right);          // 右子樹最小值覆蓋
        remove(t->element, t->right);            // 刪除該最小節點
    } else {                                     // 0 或 1 個子節點
        BinaryNode* oldNode = t;
        t = (t->left != nullptr) ? t->left : t->right; // 子節點頂替
        delete oldNode;
    }
}

插入操作：遞迴定位

template <typename Comparable>
void BinarySearchTree<Comparable>::insert(const Comparable& x, BinaryNode*& t) const {
    if (t == nullptr)
        t = new BinaryNode(x, nullptr, nullptr, 1); // 建立新節點
    else if (x < t->element)
        insert(x, t->left);
    else if (x > t->element)
        insert(x, t->right);
    else
        t->count++;                                // 重複鍵值計數器遞增
}

查找最小/最大值

template <typename Comparable>
const Comparable& BinarySearchTree<Comparable>::findMin(BinaryNode* t) const {
    if (t->left == nullptr) return t->element;
    return findMin(t->left);                     // 持續往左
}

template <typename Comparable>
const Comparable& BinarySearchTree<Comparable>::findMax(BinaryNode* t) const {
    if (t->right == nullptr) return t->element;
    return findMax(t->right);                    // 持續往右
}

深拷貝與資源管理

template <typename Comparable>
BinaryNode<Comparable>* BinarySearchTree<Comparable>::clone(BinaryNode* t) const {
    if (t == nullptr) return nullptr;
    return new BinaryNode(t->element, clone(t->left), clone(t->right), t->count);
}

template <typename Comparable>
const BinarySearchTree<Comparable>& BinarySearchTree<Comparable>::operator=(const BinarySearchTree& rhs) {
    if (this != &rhs) {
        makeEmpty();                    // 釋放舊資源
        root = clone(rhs.root);         // 深拷貝新資源
    }
    return *this;
}

遍歷輸出實作

// 中序遍歷：左-根-右，產生遞增序列
template <typename Comparable>
void BinarySearchTree<Comparable>::preOrder(BinaryNode* t) const {
    if (t != nullptr) {
        preOrder(t->left);
        for (int i = 0; i < t->count; ++i) cout << t->element << " ";
        preOrder(t->right);
    }
}

// 逆中序遍歷：右-根-左，產生遞減序列
template <typename Comparable>
void BinarySearchTree<Comparable>::inOrder(BinaryNode* t) const {
    if (t != nullptr) {
        inOrder(t->right);
        for (int i = 0; i < t->count; ++i) cout << t->element << " ";
        inOrder(t->left);
    }
}

測試驗證

int main() {
    // 測試基本操作
    BinarySearchTree<int> tree;
    vector<int> data = {6, 2, 1, 4, 3, 8};
    for (int x : data) tree.insert(x);
    
    cout << "中序遍歷(遞增): "; tree.preOrderPrintTree();  // 1 2 3 4 6 8
    cout << "逆中序(遞減): "; tree.inOrderPrintTree();     // 8 6 4 3 2 1
    
    // 測試刪除葉子節點
    tree.remove(4);
    tree.preOrderPrintTree();  // 1 2 3 6 8
    
    // 測試刪除單子節點
    BinarySearchTree<int> tree2;
    for (int x : {6, 2, 1, 5, 3, 4, 8}) tree2.insert(x);
    tree2.remove(2);           // 節點 2 有左子節點 1
    tree2.preOrderPrintTree(); // 1 3 4 5 6 8
    
    // 測試拷貝建構與賦值
    BinarySearchTree<int> tree3 = tree;  // 拷貝建構
    BinarySearchTree<int> tree4; tree4 = tree; // 賦值運算子
    
    return 0;
}

複雜度分析

最壞情況發生於樹退化為鏈表（有序插入），平衡樹（AVL、紅黑樹）可保證 O(log n)。

擴展方向

• 實作平衡機制：AVL 樹旋轉、紅黑樹著色規則
• 支援範圍查詢：lower_bound/upper_bound
• 持久化資料結構：函數式更新、版本控制
• 併發安全：細粒度鎖、無鎖演算法