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

4. 二叉搜索树的查找

查找过程直观高效：

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

对于支持重复值的场景，通常约定查找中序遍历的第一个匹配项。

5. 二叉搜索树的删除

删除是 BST 中最复杂的操作。首先定位到待删除节点 N，然后根据 N 的子节点情况分情况处理。

实际代码实现中可归纳为两类：

1. 无孩子或只有一个孩子：直接断开链接，用孩子节点填补空缺。
2. 有两个孩子：无法直接删除，需采用'替换法'。

替换法策略： 寻找 N 左子树的最大值节点（最右节点）或右子树的最小值节点（最左节点）替代 N。这两个节点中的任意一个放到 N 的位置，都能保持 BST 的性质。实际操作中通常是交换值，然后递归删除那个替代节点（因为它至多只有一个孩子）。

6. Key 和 Key/Value 使用场景

6.1 Key 搜索场景

仅存储 Key 作为关键码。适用于判断数据是否存在。

• 特点：支持增删查，不支持修改 Key（修改 Key 会破坏树结构）。
• 应用：车牌识别系统（判断车牌号）、拼写检查（词典查询）、编译器语法检查。

6.2 Key/Value 搜索场景

每个 Key 对应一个 Value。适用于映射关系。

• 特点：支持修改 Value，不支持修改 Key。
• 应用：中英文翻译系统（Key=英文，Value=中文）、车库计费系统（Key=车票号，Value=入场时间）、词频统计。

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

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

此版本模拟 std::set，不支持插入重复值。

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

namespace twg {
    template<class K>
    struct BSTnode {
        K _key;
        BSTnode* left = nullptr;
        BSTnode* right = nullptr;
        BSTnode(const K& key) : _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 {
                    // 已存在，不插入
                    return false;
                }
            }
            cur = new Node(key);
            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;
                    } 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* 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;
                    }
                    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);
            cout << endl;
        }

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

7.2 Key/Value 代码实现

此版本模拟 std::map，支持 Key/Value 映射及修改 Value。

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

namespace twg {
    template<class K, class V>
    struct BSTnode {
        K _key;
        V _val;
        BSTnode* left = nullptr;
        BSTnode* right = nullptr;
        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); }

        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;
                    } 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* leftMaxf = cur;
                        Node* leftMax = cur->left;
                        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;
                }
            }
            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 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、红黑树）的前提。建议读者结合不同数据序列进行实操，观察树的结构变化。