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

应用场景：Key vs Key/Value

Key 模型

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

• 典型场景：车牌识别系统、拼写检查词典、编译器语法检查。

Key/Value 模型

每个 Key 对应一个 Value，Value 可以是任意类型对象。以 Key 为基准进行增删查，支持修改 Value，但不支持修改 Key。

• 典型场景：中英文翻译系统、车库计费系统（存车牌号 + 入场时间）、词频统计。

代码实现

下面提供完整的 C++ 实现，包含去重版（类似 set）和可重复版（类似 multiset）两种逻辑，以及 Key/Value 模型（类似 map）的实现。

1. Key 模型实现（去重）

#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 {
                    // 已存在，不去重版本才允许插入，这里模拟 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;
                    } 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;
                    } 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;
                    }
                    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 << " ";
            inorder(root->right);
        }

        Node* _root = nullptr;
    };
}

2. Key 模型实现（可重复）

此版本允许插入相同 Key，逻辑上类似于 multiset。当遇到相等值时，统一往左走（或往右，需保持一致）。

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 {
                    parent = cur;
                    cur = cur->right;
                }
            }

            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 if (cur->right == nullptr) {
                        if (parent == nullptr) _root = cur->left;
                        else if (parent->left == cur) parent->left = cur->left;
                        else parent->right = cur->left;
                    } 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;
                    }
                    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 << " ";
            inorder(root->right);
        }

        Node* _root = nullptr;
    };
}

3. Key/Value 模型实现

这是更通用的场景，每个节点存储一对 <K, V>。

#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(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 if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    // Key 已存在，更新 Value
                    cur->_val = val;
                    return false;
                }
            }

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

        // 重载 [] 操作符
        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;
        }

        // 删除
        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 if (cur->right == nullptr) {
                        if (parent == nullptr) _root = cur->left;
                        else if (parent->left == cur) parent->left = cur->left;
                        else parent->right = cur->left;
                    } else {
                        Node* leftMax = cur->left;
                        Node* leftMaxParent = cur;
                        while (leftMax->right) {
                            leftMaxParent = leftMax;
                            leftMax = leftMax->right;
                        }
                        cur->_key = leftMax->_key;
                        cur->_val = leftMax->_val;
                        if (leftMaxParent->right == leftMax) leftMaxParent->right = leftMax->left;
                        else leftMaxParent->left = leftMax->left;
                        delete leftMax;
                    }
                    delete cur;
                    return true;
                }
            }
            return false;
        }

        void Inorder() {
            if (_root) 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、红黑树）的基础。通过对比 Key 模型与 Key/Value 模型，可以更清晰地把握不同业务场景下的数据结构选型。在实际工程中，STL 容器底层多采用平衡树变体以保证性能稳定性，但理解基础 BST 的原理始终是进阶的必经之路。