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

4. 二叉搜索树的查找

从根节点开始比较目标值 $x$：

• $x$ 比根大，向右查找。
• $x$ 比根小，向左查找。
• 最多查找高度次，若走到空指针仍未找到，说明不存在。

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

5. 二叉搜索树的删除

删除操作相对复杂，假设要删除的结点为 $N$：

1. $N$ 左右孩子均为空：直接删除。
2. $N$ 左孩子为空，右孩子不为空：将 $N$ 替换为其右孩子。
3. $N$ 右孩子为空，左孩子不为空：将 $N$ 替换为其左孩子。
4. $N$ 左右孩子均不为空：这是难点。通常采用替换法。

在代码实现上，可以将前三种情况合并（没有孩子视为只有一个空孩子），主要分两类处理：

• 无孩子或只有一个孩子：直接调整父节点指针指向其非空子节点。
• 有两个孩子：无法直接删除，需用替代法。找 $N$ 左子树的最大结点（最右结点）或右子树的最小结点（最左结点）替代 $N$。因为这两个结点中的任意一个放到 $N$ 的位置，都满足 BST 规则。

替换法示意

以右子树的最小结点为例，交换值后，问题转化为删除那个最小结点（它必然没有左孩子，简化了删除逻辑）。

6. 二叉搜索树 Key 和 Key/Value 使用场景

6.1 Key 搜索场景

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

典型应用：

• 车牌识别系统：后台录入车牌号，快速判断是否存在。
• 拼写检查：词典录入二叉树，检查单词是否存在。
• 编译器语法检查：库、自定义标识符放入树中。

6.2 Key/Value 搜索场景

每个 Key 对应一个 Value，Value 可以是任意类型对象。增删查仍以 Key 为关键字，可以快速找到 Key 对应的 Value。支持修改 Value，但不支持修改 Key。

典型应用：

• 中英文互译系统：Key 为英文，Value 为中文。
• 车库收费系统：通过存车票号和入场时间计算租金。
• 词频统计：读取文章，统计单词出现次数。

7. 二叉搜索树的实现代码

7.1 Key 模型代码实现（Set 去重版）

这里展示基于 Key 的去重版本实现，模拟 STL 中 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;
                        }
                        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* rightMin = cur->right;
                        Node* rightMinParent = cur;
                        while (rightMin->left) {
                            rightMinParent = rightMin;
                            rightMin = rightMin->left;
                        }

                        cur->_key = rightMin->_key;
                        if (rightMinParent->left == rightMin) {
                            rightMinParent->left = rightMin->right;
                        } else {
                            rightMinParent->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);
        }

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

        Node* _root = nullptr;
    };
}

7.2 Key/Value 代码实现（Map 模型）

此版本支持 Key-Value 对，模拟 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:
        // 拷贝构造
        map(const map& other) {
            _root = Copy(other._root);
        }

        // 析构
        ~map() {
            Destory(_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 {
                    // 删除逻辑同 Set，此处省略重复代码，核心是替换法
                    if (cur->left == nullptr || cur->right == nullptr) {
                        Node* child = cur->left ? cur->left : cur->right;
                        if (parent == nullptr) _root = child;
                        else if (parent->left == cur) parent->left = child;
                        else parent->right = child;
                        delete cur;
                    } else {
                        Node* successor = cur->right;
                        Node* succParent = cur;
                        while (successor->left) {
                            succParent = successor;
                            successor = successor->left;
                        }
                        cur->_key = successor->_key;
                        cur->_val = successor->_val;
                        if (succParent->left == successor) succParent->left = successor->right;
                        else succParent->right = successor->right;
                        delete successor;
                    }
                    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:
        Node* Copy(const Node* root) {
            if (!root) 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) return;
            Destory(root->left);
            Destory(root->right);
            delete root;
        }

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

        Node* _root = nullptr;
    };
}

掌握双场景适配与增删查改的边界处理后，你已能应对简单数据存储需求。二叉搜索树是理解更高级数据结构（如 AVL、红黑树）的基础，建议结合不同数据插入场景实操观察树的结构变化。