C++ 二叉搜索树原理与增删查操作实现

2.1. 查找节点

给定目标 val，可以声明一个节点 cur，从二叉搜索树的根节点 _root 出发，循环比较 cur->_key 和 val 之间的大小关系：

• 若 val < cur->_key，说明目标节点在 cur 的左子树，执行 cur = cur->_left
• 若 val > cur->_key，说明目标节点在 cur 的右子树，执行 cur = cur->_right
• 若 val == cur->_key，说明找到目标节点，跳出循环并返回该节点

与二分查找原理一致，每轮排除一半的情况，当二叉树平衡时，循环次数最多为二叉树的高度，O(logn)。

// 查找节点
Node* find(const K& val) {
    Node* cur = _root;
    while (cur) {
        if (val < cur->_key) cur = cur->_left;
        else if (val > cur->_key) cur = cur->_right;
        else break;
    }
    return cur;
}

2.2. 插入节点

给定一个待插入元素 val，为了保持左子树 < 根节点 < 右子树的性质，插入流程如下：

1. 查找插入位置： 与查找操作相同逻辑，从根节点出发，根据当前节点值和 val 的大小关系循环向下搜索，直到越过叶子节点（遍历到 nullptr）跳出循环
2. 在该位置插入节点： new一个新节点，将新节点置于 nullptr 的位置

注意：

• 二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
• 为了实现插入节点，我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 nullptr 时，我们可以获取到其父节点，从而完成节点插入操作。

bool insert(const K& val) {
    // 空树 直接插入
    if (_root == nullptr) {
        Node* newNode = new BSTNode(val);
        _root = newNode;
        return true;
    }
    // 非空树 先找待插入节点的位置
    Node* cur = _root;
    Node* curPre = nullptr; // 保存 cur 的父节点
    while (cur) {
        if (val == cur->_key) return false; // 重复值 不插入
        else if (val < cur->_key) { // 小于键值 往左走 同时更新 cur 的父节点
            curPre = cur;
            cur = cur->_left;
        } else { // 大于键值 往右走 同时更新 cur 的父节点
            curPre = cur;
            cur = cur->_right;
        }
    }
    // cur 的位置是待插入位置
    Node* newNode = new BSTNode(val);
    // 判断 cur 在 curPre 的左边还是右边 确定新节点位置
    if (curPre->_left == cur) curPre->_left = newNode;
    else curPre->_right = newNode;
    return true;
}

2.3. 删除节点

先在二叉树中查找到目标节点，再将其删除。与插入节点一样，我们需要保证在删除操作完成后，保证二叉搜索树的'左子树 < 根节点 < 右子树'的性质不变。

根据待删除节点的孩子数量，分 0、1 和 2 三种情况：

• 待删除结点是叶子节点，直接删除
• 待删除节点有一个孩子，将待删除节点的子节点和其替换即可
• 待删除节点 2 个孩子，不能直接删除，需要用一个节点替换该节点，保持'左子树 < 根节点 < 右子树'的性质不变，可以选择右子树最小节点或左子树最大节点

假设我们选择右子树最小节点，如下流程：

1. 找到待删除节点 cur 的右子树最小节点 rightMin
2. 用 rightMin 的值覆盖 cur，并删除 rightMin

总共有如下几种情况：

**cur 有两个孩子；rightMin 在更下方；rightMin 只有右孩子（B1）**触发：cur->_right有左孩子，沿左链找到 rightMin，且 rightMin->_right != nullptr。操作：cur->_key = rightMin->_key；令 rightMinPre->_left = rightMin->_right；删除 rightMin。

**cur 有两个孩子；rightMin 在更下方；rightMin 无右孩子（B0）**触发：cur->_right有左孩子，沿左链找到 rightMin，且 rightMin->_right == nullptr。操作：cur->_key = rightMin->_key；令 rightMinPre->_left = nullptr；删除 rightMin。

**cur 有两个孩子；rightMin 就是 cur->_right；rightMin 只有右孩子（A1）**触发：cur->_right没有左孩子，且 cur->_right->_right != nullptr。操作：cur->_key = rightMin->_key；令 cur->_right = rightMin->_right；删除 rightMin。

**cur 有两个孩子；右子树最小节点 rightMin 就是 cur->_right；rightMin 无右孩子（A0）**触发：cur->_right没有左孩子，且 cur->_right->_right == nullptr。操作：cur->_key = rightMin->_key；令 cur->_right = nullptr；删除 rightMin。

bool erase(const K& val) {
    // 空树无法删除
    if (_root == nullptr) return false;
    
    // 查找待删除节点
    Node* cur = _root;
    Node* curPre = nullptr;
    while (cur) {
        if (val < cur->_key) { // 向左找
            curPre = cur;
            cur = cur->_left;
        } else if (val > cur->_key) { // 向右找
            curPre = cur;
            cur = cur->_right;
        } else break; // 命中
    }
    
    // cur 为空 无法删除
    if (cur == nullptr) return false;
    
    // 找到 cur 了
    // 孩子 0/1 个的情况
    if (cur->_left == nullptr || cur->_right == nullptr) {
        // 找到待删除节点的孩子
        Node* curNext = cur->_left == nullptr ? cur->_right : cur->_left;
        if (cur != _root) { // 删除的不是根节点
            if (curPre->_left == cur) curPre->_left = curNext;
            else curPre->_right = curNext;
        } else { // 删除的是根节点
            _root = curNext;
        }
        delete cur;
    } else {
        // 2 个孩子
        // 1. 找右子树最小节点
        Node* rightMin = cur->_right;
        Node* rightMinPre = cur;
        while (rightMin->_left) {
            rightMinPre = rightMin;
            rightMin = rightMin->_left;
        }
        // 2. 用 rightMin 的值覆盖待删除节点的值
        cur->_key = rightMin->_key;
        // 3. 删除 rightMin 要处理 rightMin 的孩子
        Node* rightMinNext = rightMin->_right;
        if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
        else rightMinPre->_right = rightMinNext;
        // 右子树最小节点是 cur->_right 的情况
        delete rightMin;
    }
    return true;
}

再次总结：

查找阶段

• 用 cur 定位待删，curPre 记录父。
• 终止条件：命中或走到空。
• 注意：若支持自定义比较器，等价判断应为'!(val<key) && !(key<val)'。

0/1 个孩子：真正移除 cur 节点

• curNext = (cur->_left ? cur->_left : cur->_right)。
• 若 cur != _root：把 curPre 的相应孩子指向 curNext。
• 若 cur == _root：_root = curNext。
• delete cur。
• 要点：这是必须对'根'特判的地方（根没有父指针可改）。

2 个孩子：值覆盖 + 删后继（不移动 cur 本体）

• 覆盖键值：cur->_key = rightMin->_key;（若有 value，一并拷/搬移）。
• 要点：这里不需要根特判，因为根节点对象没被删除，只是'值被改写'。

删除 rightMin：

Node* rightMinNext = rightMin->_right; // 只可能有右孩子或空
if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
else rightMinPre->_right = rightMinNext;
// 当 rightMin 就是 cur->_right
delete rightMin;

找右子树最小：

Node* rightMin = cur->_right;
Node* rightMinPre = cur;
while (rightMin->_left) {
    rightMinPre = rightMin;
    rightMin = rightMin->_left;
}

3. 二叉搜索树的实现

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

namespace BSTKey {
template<class K>
struct BSTNode {
    BSTNode<K>* _left;
    BSTNode<K>* _right;
    K _key;
    // 构造
    BSTNode(const K& val) : _left(nullptr), _right(nullptr), _key(val) {}
};

template<class K>
class BSTree {
public:
    typedef BSTNode<K> Node;
    BSTree() = default;
    // 析构 需要辅助析构函数
    ~BSTree() {
        destroy(_root);
        _root = nullptr;
    }
    // 查找节点
    Node* find(const K& val) {
        Node* cur = _root;
        while (cur) {
            if (val < cur->_key) cur = cur->_left;
            else if (val > cur->_key) cur = cur->_right;
            else break;
        }
        return cur;
    }
    bool insert(const K& val) {
        // 空树 直接插入
        if (_root == nullptr) {
            Node* newNode = new BSTNode(val);
            _root = newNode;
            return true;
        }
        // 非空树 先找待插入节点的位置
        Node* cur = _root;
        Node* curPre = nullptr; // 保存 cur 的父节点
        while (cur) {
            if (val == cur->_key) return false; // 重复值 不插入
            else if (val < cur->_key) { // 小于键值 往左走 同时更新 cur 的父节点
                curPre = cur;
                cur = cur->_left;
            } else { // 大于键值 往右走 同时更新 cur 的父节点
                curPre = cur;
                cur = cur->_right;
            }
        }
        // cur 的位置是待插入位置
        Node* newNode = new BSTNode(val);
        // 判断 cur 在 curPre 的左边还是右边 确定新节点位置
        if (curPre->_left == cur) curPre->_left = newNode;
        else curPre->_right = newNode;
        return true;
    }
    bool erase(const K& val) {
        // 空树无法删除
        if (_root == nullptr) return false;
        // 查找待删除节点
        Node* cur = _root;
        Node* curPre = nullptr;
        while (cur) {
            if (val < cur->_key) { // 向左找
                curPre = cur;
                cur = cur->_left;
            } else if (val > cur->_key) { // 向右找
                curPre = cur;
                cur = cur->_right;
            } else break; // 命中
        }
        // cur 为空 无法删除
        if (cur == nullptr) return false;
        // 找到 cur 了
        // 孩子 0/1 个的情况
        if (cur->_left == nullptr || cur->_right == nullptr) {
            // 找到待删除节点的孩子
            Node* curNext = cur->_left == nullptr ? cur->_right : cur->_left;
            if (cur != _root) { // 删除的不是根节点
                if (curPre->_left == cur) curPre->_left = curNext;
                else curPre->_right = curNext;
            } else { // 删除的是根节点
                _root = curNext;
            }
            delete cur;
        } else {
            // 2 个孩子
            // 1. 找右子树最小节点
            Node* rightMin = cur->_right;
            Node* rightMinPre = cur;
            while (rightMin->_left) {
                rightMinPre = rightMin;
                rightMin = rightMin->_left;
            }
            // 2. 用 rightMin 的值覆盖待删除节点的值
            cur->_key = rightMin->_key;
            // 3. 删除 rightMin 要处理 rightMin 的孩子
            Node* rightMinNext = rightMin->_right;
            if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
            else rightMinPre->_right = rightMinNext;
            // 右子树最小节点是 cur->_right 的情况
            delete rightMin;
        }
        return true;
    }
    void inOrder() {
        _inOrder(_root);
        cout << endl;
    }
private:
    Node* _root;
    // 后续析构
    void destroy(Node* root) {
        if (root == nullptr) return;
        destroy(root->_left);
        destroy(root->_right);
        delete root;
    }
    void _inOrder(Node* root) {
        if (root == nullptr) return;
        _inOrder(root->_left);
        cout << root->_key << " ";
        _inOrder(root->_right);
    }
};

void testBST() {
    BSTree<int> bst;
    vector<int> arr = {8, 3, 10, 1, 6, 14, 5, 7, 13};
    cout << "=== 1. 创建二叉搜索树 ===\n";
    cout << "初始数据：-> ";
    for (const auto& e : arr) cout << e << " ";
    cout << "\n创建完成数据：-> ";
    for (const auto& e : arr) bst.insert(e);
    bst.inOrder();
    cout << "=== 2. 查找数据 ===\n";
    cout << "查找不存在数据：28 查找结果：" << bst.find(28) << endl;
    cout << "查找存在数据：14 查找结果：" << bst.find(14) << endl;
    cout << "\n=== 3. 删除数据 ===\n";
    cout << "删除前的序列：->"; bst.inOrder();
    cout << "删除节点 6 后的序列：->"; bst.erase(6); bst.inOrder();
    cout << "删除不存在的节点 86 后的序列：->"; bst.erase(86); bst.inOrder();
    cout << "\n销毁二叉树：->"; bst.~BSTree(); bst.inOrder();
}
}

4. 二叉搜索树的应用

4.1. K 模型

只有 key 作为关键码（需要搜索到的值），结构中只存储 key 即可

例如：给一个单词 word，判断该单词是否正确

• 以词库中所有单词集合中的每个单词作为 key，构建一颗二叉搜索树
• 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

又比如门禁系统，只关注对象在不在

第三节实现的就是 K 模型

4.2. KV 模型

每个关键码 key，都有与之对应的值 value，即<key，value>的键值对，例如：

• 简单英汉词典中英文和中文是相互对应的关系，通过英文可快速找到其对应的中文，例如：<book,书>就是一种键值对
• 车库收费系统，一个键值记录车牌号，另一个键值记录停留时间，随后交给收费系统处理缴费事宜
• 统计单词出现次数，统计成功之后，给定单词就可快速找到其出现的次数，单词与其出现的次数就是<word,count>一种键值对

我们将 K 模型改造成 KV 模型

template<class K, class V>
struct BSTNode {
    K _key;
    V _value;
    BSTNode<K, V>* _left;
    BSTNode<K, V>* _right;
    BSTNode(const K& k, const V& v) : _key(k), _value(v), _left(nullptr), _right(nullptr) {}
};

template<class K, class V>
class BSTree {
public:
    typedef BSTNode<K, V> Node;
    // ... 接口实现
private:
    Node* _root = nullptr;
    // ... 辅助接口实现
};

// 输入中文 输出对应英文
void dictionary() {
    BSTree<string, string> dict;
    dict.insert("书包", "bag");
    dict.insert("水果", "fruit");
    dict.insert("钢笔", "pen");
    dict.insert("书", "book");
    dict.insert("树", "tree");
    // 插入词库中所有单词
    string str;
    while (cin >> str) {
        auto ret = dict.find(str);
        if (ret == nullptr) cout << "输入错误或词库中未包含该词" << str << endl;
        else cout << str << "英文单词：->" << ret->_value << endl;
    }
}

// 计数
void count() {
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
    BSTree<string, int> cntTree;
    for (const auto& s : arr) {
        // 先查找水果在不在搜索树中
        // 1. 不在，说明水果第一次出现，则插入<水果，1>
        // 2. 在，则查找到的节点中水果对应的次数++
        auto ret = cntTree.find(s);
        if (ret == nullptr) cntTree.insert(s, 1);
        else ret->_value++;
    }
    cntTree.inOrder();
}

二叉搜索树的核心价值，在于用'左子树 < 根节点 < 右子树'的简单规则，换来了查找、插入、删除操作的高效性 —— 平衡状态下 O(logn) 的时间复杂度，让它成为处理动态数据查找场景的基础选择。无论是仅需判断'存在性'的 K 模型，还是需键值关联的 KV 模型，都能通过其核心操作快速适配，覆盖词典查询、计数统计等常见需求。

但需注意，二叉搜索树的性能依赖结构平衡：若插入数据有序，会退化为单链表，此时操作复杂度飙升至 O(n)。这也催生了 AVL 树、红黑树等平衡二叉搜索树 —— 它们通过自平衡机制维持树的高度，兼顾了二叉搜索树的简洁性与稳定高效的性能，是后续深入学习的重要方向。