二叉搜索树（BST）核心原理与 C++ 实战

初始化和销毁

构造函数初始化根节点为空。析构函数需要递归释放内存，防止泄漏。

~BSTree() { Destroy(_root); }
void Destroy(Node*& root) {
    if (root == nullptr) return;
    Destroy(root->_left);
    Destroy(root->_right);
    delete root;
    root = nullptr;
}

拷贝构造和赋值运算符重载通常利用深拷贝和交换法来实现，这里省略细节，重点看核心逻辑。

插入操作

插入分为递归和循环两种方式。递归写法简洁，但栈空间开销大；循环写法空间效率高，适合深层树。

递归实现：

bool InsertR(const K& key) { return _InsertR(_root, key); }
bool _InsertR(Node*& root, const K& key) {
    if (root == nullptr) {
        root = new Node(key);
        return true;
    }
    if (key < root->_key) return _InsertR(root->_left, key);
    else if (key > root->_key) return _InsertR(root->_right, key);
    else return false; // 不允许重复值
}

循环实现：

bool Insert(const K& key) {
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (key < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (key > cur->_key) { // 注意补全条件
            parent = cur;
            cur = cur->_right;
        } else {
            return false;
        }
    }
    cur = new Node(key);
    if (key < parent->_key) parent->_left = cur;
    else parent->_right = cur;
    return true;
}

查找操作

查找逻辑很直观，从根节点开始比较，根据大小决定向左还是向右走。

bool Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (key < cur->_key) cur = cur->_left;
        else if (key > cur->_key) cur = cur->_right;
        else return true;
    }
    return false;
}

删除操作

删除是最复杂的，分三种情况讨论：

1. 叶子节点：直接删除。
2. 有一个子节点：用子节点替换当前节点。
3. 有两个子节点：找到中序后继（右子树最小）或前驱（左子树最大），替换值后递归删除该后继/前驱。

递归删除示例：

bool EraseR(const K& key) { return _EraseR(_root, key); }
bool _EraseR(Node*& root, const K& key) {
    if (root == nullptr) return false;
    if (key < root->_key) return _EraseR(root->_left, key);
    else if (key > root->_key) return _EraseR(root->_right, key);
    
    // 找到目标节点
    Node* del = root;
    if (root->_left == nullptr) {
        root = root->_right;
    } else if (root->_right == nullptr) {
        root = root->_left;
    } else {
        // 找左子树最大节点
        Node* maxleft = root->_left;
        while (maxleft->_right) maxleft = maxleft->_right;
        swap(maxleft->_key, root->_key);
        return _EraseR(root->_left, key);
    }
    delete del;
    return true;
}

应用场景

K 模型

只存储 Key，用于快速判断某个值是否存在。比如字典去重。

KV 模型

Key 对应 Value，典型的键值对存储。比如英汉词典，Key 是单词，Value 是翻译。

在 KV 模型中，节点结构增加 V _val 字段，其余逻辑与 K 模型一致。

完整源码参考

以下是整合后的 K 模型与 KV 模型代码框架，包含头文件与测试逻辑。

K 模型头文件 (BST.h)

#pragma once
#include<iostream>
#include <utility>
using namespace std;

namespace K {
template<class K> struct BSTNode {
    BSTNode(const K& key) :_left(nullptr), _right(nullptr), _key(key) {}
    BSTNode<K>* _left;
    BSTNode<K>* _right;
    K _key;
};

template<class K> class BSTree {
    typedef BSTNode<K> Node;
public:
    BSTree() {}
    ~BSTree() { Destroy(_root); }
    bool Insert(const K& key) { /* 见上文 */ }
    bool Find(const K& key) { /* 见上文 */ }
    bool Erase(const K& key) { /* 见上文 */ }
    void InOrder() { InOrder(_root); }
    void InOrder(Node* root) {
        if (!root) return;
        InOrder(root->_left);
        cout << root->_key << " ";
        InOrder(root->_right);
    }
private:
    Node* _root = nullptr;
    // 辅助函数略...
};
}

KV 模型测试示例

#include "BST.h"
int main() {
    KV::BSTree<string, string> dictionary;
    dictionary.Insert("apple", "苹果");
    dictionary.Insert("banana", "香蕉");
    dictionary.InOrder(); // 输出单词顺序
    dictionary.Erase("banana");
    dictionary.InOrder();
    return 0;
}

总结

二叉搜索树是数据结构中的基石之一。虽然基础版在极端情况下性能会退化，但它为理解平衡树（如 AVL、红黑树）奠定了坚实基础。在实际工程中，C++ STL 的 map/set 底层正是基于红黑树实现的，它们保证了稳定的对数级性能。