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

4. 二叉搜索树的查找

查找过程非常直观：

• 从根节点开始比较。
• 目标值 $x$ 比根大，往右找；比根小，往左找。
• 最多查找树的高度次。若走到空指针仍未找到，说明不存在。

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

5. 二叉搜索树的删除

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

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

代码实现策略：

实际上可以将'无孩子'和'只有一个孩子'合并处理（无孩子可视为有一个 nullptr 的孩子）。主要难点在于有两个孩子的情况。

对于有两个孩子的结点，无法直接删除，因为它的两个子树无处安放。我们采用替换法：

• 找到 N 左子树的最大结点 R（最右结点），或者 N 右子树的最小结点 R（最左结点）。
• 这两个结点中的任意一个放到 N 的位置，都能满足 BST 规则。
• 实际操作是将 N 和 R 的值交换，然后转为删除 R 结点（此时 R 最多只有一个孩子）。

6. Key 和 Key/Value 使用场景

6.1 Key 搜索场景

只存储 Key，用于判断 Key 是否存在。例如车牌识别、拼写检查、编译器语法检查等。此类场景通常对应 set/multiset，不支持修改 Key（会破坏结构）。

6.2 Key/Value 搜索场景

每个 Key 对应一个 Value。通过 Key 快速找到对应的 Value。例如中英文翻译、车库计费系统、词频统计等。此类场景对应 map/multimap，支持修改 Value，但不支持修改 Key。

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

下面提供完整的 C++ 实现，包含去重（Set 模型）和非去重（Multiset 模型）两种版本。

7.1 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) {}
    };

    // 去重版 set -> Key 模型
    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 {
                    // 已存在，不去重
                    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 {
                    // 找到目标，执行删除逻辑
                    // 情况 1: 只有右孩子或无孩子
                    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;
                    }
                    // 情况 2: 有两个孩子，使用替代法
                    else {
                        Node* rightMinf = cur;
                        Node* rightMin = cur->left;
                        while (rightMin->left) {
                            rightMinf = rightMin;
                            rightMin = rightMin->left;
                        }

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

                        rightMinf->left = rightMin->right;
                        rightMin->left = cur->left;
                        rightMin->right = cur->right;

                        delete cur;
                        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(const Node* root) {
            if (!root) return;
            inorder(root->left);
            cout << root->_key << endl;
            inorder(root->right);
        }

        Node* _root = nullptr;
    };
}

7.2 Key/Value 代码实现

Map 模型增加了 Value 的存储，并支持 operator[] 进行自动插入或取值。

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

        // 插入
        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 {
                    // 删除逻辑同 Key 模型
                    if (cur->right != 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 {
                        Node* leftMax = cur->left;
                        Node* leftMaxf = cur;
                        while (leftMax->right) {
                            leftMaxf = leftMax;
                            leftMax = leftMax->right;
                        }
                        cur->_key = leftMax->_key;
                        cur->_val = leftMax->_val;
                        leftMaxf->right = 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;
        }

    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 << endl;
            _inorder(root->right);
        }

        Node* _root = nullptr;
    };
}

结语

二叉搜索树的核心在于'左小右大'的特性，这使其在查询上优于普通链表，在插入删除上优于有序数组。理解其增删查改的边界处理，特别是删除时的替代法，是掌握后续平衡树（AVL、红黑树）的基础。建议读者结合代码实操不同数据插入场景，观察树的结构变化，体会性能差异。