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

基于上述数据的初始树结构如下：

继续插入 16 和 13 后的变化：

查找操作

查找逻辑非常直观：

1. 从根节点开始比较。
2. 若目标值 $x$ 大于当前根值，向右子树查找；若小于，向左子树查找。
3. 最多查找树的高度次，若走到空指针仍未找到，说明不存在。

对于不支持相等值的场景，找到即返回；对于支持相等值的场景（如 multiset），通常要求返回中序遍历的第一个匹配项。

删除操作

删除是 BST 中最复杂的操作。首先需要确认元素是否存在，若不存在直接返回。

假设要删除的结点为 $N$，根据孩子数量分为四种情况：

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

为了简化代码实现，我们可以将其归纳为两类：

• 没有孩子或只有一个孩子：可以直接调整父节点的指针指向其唯一的孩子（若无孩子则指向 nullptr）。
• 有两个孩子：无法直接删除，需采用替换法。找到 $N$ 左子树的最大结点（最右结点）或右子树的最小结点（最左结点）替代 $N$。这两个结点中的任意一个放到 $N$ 的位置，都能满足二叉搜索树的规则。实际操作中，通常是交换值，然后转为删除那个替代结点（该结点必然属于第一类情况）。

应用场景：Key 与 Key/Value

1. Key 搜索场景

只存储关键码 key，用于判断数据是否存在。此类 BST 支持增删查，但不支持修改 key（修改 key 会破坏树结构）。

典型应用：

• 车牌抬杆识别系统（后台录入车牌号）。
• 英文文章错别字检查（词典录入 BST）。
• 编译器语法检查（库、关键词放入 BST）。

2. Key/Value 搜索场景

每个 key 对应一个 value。增删查仍以 key 为关键字进行比较，快速定位对应的 value。此类 BST 支持修改 value，但不支持修改 key。

典型应用：

• 中英文互译系统（key=英文，value=中文）。
• 商场车库计费系统（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:
        // 插入：若已存在返回 false，否则插入并返回 true
        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 {
                    // 已存在，不去重
                    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;
                        }
                    } else {
                        // 有左孩子，找左子树最大值替代
                        Node* rightMinf = cur;
                        Node* rightMin = cur->left;
                        while (rightMin->right) {
                            rightMinf = rightMin;
                            rightMin = rightMin->right;
                        }

                        // 调整链接关系
                        if (parent == nullptr) {
                            _root = rightMin;
                        } else if (parent->left == cur) {
                            parent->left = rightMin;
                        } else {
                            parent->right = rightMin;
                        }

                        rightMinf->right = rightMin->left;
                        rightMin->left = cur->left;
                        rightMin->right = cur->right;
                    }
                    delete cur;
                    return true;
                }
            }
            cout << "没有该节点" << endl;
            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);
        }

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

        Node* _root = nullptr;
    };
}

Key/Value 模型实现（Map）

#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:
        map() = default;
        ~map() { Destory(_root); }

        // 拷贝构造
        map(const map& other) {
            _root = Copy(other._root);
        }

        // 赋值运算符重载
        map& operator=(map other) {
            swap(_root, other._root);
            return *this;
        }

        // 插入
        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 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;
        }

        // 删除
        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;
                    } 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;
                    }
                    delete cur;
                    return true;
                }
            }
            cout << "没有该节点，删除失败" << endl;
            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:
        Node* Copy(const Node* root) {
            if (root == nullptr) return nullptr;
            Node* newNode = new Node(root->_key, root->_val);
            newNode->left = Copy(root->left);
            newNode->right = Copy(root->right);
            return newNode;
        }

        void Destory(Node* root) {
            if (root == nullptr) return;
            Destory(root->left);
            Destory(root->right);
            delete root;
        }

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

        Node* _root = nullptr;
    };
}

掌握双场景适配与增删查改的边界处理后，你已能应对简单数据存储需求。二叉搜索树作为平衡树（AVL、红黑树）的基础，理解其退化痛点对后续学习至关重要。