C++ 二叉搜索树详解：增删查改与 Key/Value 场景实现

查找操作

从根开始比较：

• x 比根的值大，往右边找
• x 比根的值小，往左边找
• 最多查找高度次，走到空仍未找到则不存在

如果不支持插入相等值，找到即返回；如果支持，通常要求查找中序的第一个 x。

删除操作

删除是较复杂的操作。首先查找元素是否存在，若存在则分情况处理（假设待删除结点为 N）：

1. N 左右孩子均为空
2. N 左孩子为空，右孩子不为空
3. N 右孩子为空，左孩子不为空
4. N 左右孩子均不为空

代码实现上可简化为两种情况：

• 无孩子或只有一个孩子：视为一种情况（无孩子可看作有一个 nullptr 的孩子），直接将父节点指向其唯一的孩子指针。
• 有两个孩子：无法直接删除，需用替换法。找 N 左子树的最大结点 R（最右结点）或者 N 右子树的最小结点 R（最左结点）替代 N。这两个结点放到 N 的位置都满足二叉搜索树规则。替代意味着交换 N 和 R 的值，转而删除 R 结点。

使用场景

Key 搜索场景

只有 key 作为关键码，结构中只需要存储 key。关键码即为需要搜索到的值，只需判断 key 是否存在。

Key 模型实现的二叉搜索树支持增删查，但不支持修改 key（修改 key 会破坏搜索树结构）。

典型应用：

• 车牌抬杆识别系统（后台录入车牌号）
• 检查英文文章是否有错（词典录入）
• 编译器语法检查（库、自定义、关键词）

Key/Value 搜索场景

每个关键码 key 都有对应的值 value，value 可以是任意类型对象。树结构中除了存 key 还要存 value。增/删/查仍以 key 为关键字进行比较，快速找到 key 对应的 value。

Key/Value 模型支持修改 value，但不支持修改 key。

典型应用：

• 中英文互译系统（key 为英文，value 为中文）
• 商场车库收费系统（存车票号和入场时间计算租金）
• 统计文章中单词出现次数

完整代码实现

Key 模型实现

这里展示去重版 set 模型的底层实现。

#pragma once
#include <assert.h>
#include <iostream>
using namespace std;

namespace twg {
    template<class K>
    struct BSTnode {
        K _key;
        BSTnode* left;
        BSTnode* right;
        BSTnode(const K& key = K()) : _key(key), left(nullptr), right(nullptr) {}
    };

    template<class K>
    class Set {
        typedef BSTnode<K> Node;
    public:
        bool Insert(const K& key) {
            if (_root == nullptr) {
                _root = new Node(key);
                return true;
            }
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    // 已存在，不去重版本可在此处继续逻辑，此处模拟 set 去重
                    return false;
                }
            }
            cur = new Node(key);
            if (parent->_key > key) {
                parent->left = cur;
            } else {
                parent->right = cur;
            }
            return true;
        }

        bool Erase(const K& key) {
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    // 找到目标，执行删除逻辑
                    if (cur->left == nullptr) {
                        if (parent == nullptr) _root = cur->right;
                        else if (parent->left == cur) parent->left = cur->right;
                        else parent->right = cur->right;
                        delete cur;
                        return true;
                    } else if (cur->right == nullptr) {
                        if (parent == nullptr) _root = cur->left;
                        else if (parent->left == cur) parent->left = cur->left;
                        else parent->right = cur->left;
                        delete cur;
                        return true;
                    } else {
                        // 两个孩子的情况，用右子树最小结点替代
                        Node* rightMinf = cur;
                        Node* rightMin = cur->right;
                        while (rightMin->left) {
                            rightMinf = rightMin;
                            rightMin = rightMin->left;
                        }
                        cur->_key = rightMin->_key;
                        if (rightMinf->left == rightMin) rightMinf->left = rightMin->right;
                        else rightMinf->right = rightMin->right;
                        delete rightMin;
                        return true;
                    }
                }
            }
            return false;
        }

        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;
        }

        void Inorder() {
            assert(_root);
            inorder(_root);
            cout << endl;
        }

    private:
        void inorder(const Node* root) {
            if (root == nullptr) return;
            inorder(root->left);
            cout << root->_key << " ";
            inorder(root->right);
        }
        Node* _root = nullptr;
    };
}

Key/Val 模型实现

对应 map 模型的实现，支持修改 value。

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

namespace twg {
    template<class K, class V>
    struct BSTnode {
        K _key;
        V _val;
        BSTnode* left;
        BSTnode* right;
        BSTnode(const K& key, const V& val) : _key(key), _val(val), left(nullptr), right(nullptr) {}
    };

    template<class K, class V>
    class Map {
        typedef BSTnode<K, V> Node;
    public:
        bool Insert(const K& key, const V& val) {
            if (_root == nullptr) {
                _root = new Node(key, val);
                return true;
            }
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key <= cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else {
                    parent = cur;
                    cur = cur->right;
                }
            }
            cur = new Node(key, val);
            if (key <= parent->_key) parent->left = cur;
            else parent->right = cur;
            return true;
        }

        bool Erase(const K& key) {
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    if (cur->left == nullptr) {
                        if (parent == nullptr) _root = cur->right;
                        else if (parent->left == cur) parent->left = cur->right;
                        else parent->right = cur->right;
                        delete cur;
                        return true;
                    } else if (cur->right == nullptr) {
                        if (parent == nullptr) _root = cur->left;
                        else if (parent->left == cur) parent->left = cur->left;
                        else parent->right = cur->left;
                        delete cur;
                        return true;
                    } else {
                        Node* leftMax = cur->left;
                        Node* leftMaxf = cur;
                        while (leftMax->right) {
                            leftMaxf = leftMax;
                            leftMax = leftMax->right;
                        }
                        cur->_key = leftMax->_key;
                        cur->_val = leftMax->_val;
                        if (leftMaxf->right == leftMax) leftMaxf->right = leftMax->left;
                        else leftMaxf->left = leftMax->left;
                        delete leftMax;
                        return true;
                    }
                }
            }
            return false;
        }

        V& operator[](const K& key) {
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    return cur->_val;
                }
            }
            cur = new Node(key, V());
            if (parent == nullptr) _root = cur;
            else if (key < parent->_key) parent->left = cur;
            else parent->right = cur;
            return cur->_val;
        }

        void Inorder() {
            _inorder(_root);
            cout << endl;
        }

    private:
        void _inorder(const Node* root) {
            if (root == nullptr) return;
            _inorder(root->left);
            cout << root->_key << ":" << root->_val << " ";
            _inorder(root->right);
        }
        Node* _root = nullptr;
    };
}

掌握双场景适配与增删查改的边界处理后，你已能应对简单数据存储需求。理解二叉搜索树的退化痛点，有助于后续学习 AVL 树等平衡树结构，将性能稳定在 logN 级别。