一、前言

在C++STL容器中，map/set/multimap/multiset四大关联容器底层全部依托二叉搜索树及其优化版本（AVL树、红黑树）实现。想要吃透关联容器，第一步必须彻底弄懂基础版二叉搜索树（BST）。
本文结合手撕源码、图文逻辑、面试高频考点、从零讲解二叉搜索树，提供两份可直接编译运行的完整代码，适合零基础入门,源码学习。

二、二叉搜索树的概念

2.1 定义

二叉搜索树（Binary Search Tree，BST），也叫二叉排序树，是满足特殊规则的二叉树，空树也属于合法的二叉搜索树，三大核心性质：

• 左子树所有节点值≤ 根节点值
• 右子树所有节点值 ≥ 根节点值
• 左右子树必须同样满足二叉搜索树规则，递归定义

2.2 重复值处理规则

二叉搜索树是否允许重复节点，无强制标准，由业务场景决定：

• 不允许重复值：对应STL set、map，键值唯一，插入重复值直接失败
• 允许重复值：对应STL multiset、multimap，重复值统一放左子树/右子树，全程逻辑必须一致，不能左右随意切换

2.3 核心特性：中序遍历有序

二叉搜索树最关键的特点：中序遍历结果是严格升序序列，这也是它被称为排序树的核心原因，后续代码中会通过中序遍历验证树的合法性。

三、二叉搜索树性能分析

3.1 时间复杂度分两种极端情况

树形态	树高度	增删查时间复杂度	场景说明
最优：平衡二叉树（接近完全二叉树）	$$lo{g}_{2}N$$	$$O(lo{g}_{2}N)$$	数据随机插入，查询效率极高
最差：退化成单支树	N	O(N)	数据有序插入（1,2,3,4,5…），彻底退化成链表

3.2 和二分查找的对比

有序数组二分查找同样拥有$O(lo{g}_{2}N)$查询效率，但存在致命缺陷：

1. 依赖连续内存，必须支持下标随机访问，且数组全程有序
2. 插入、删除元素需要大批量挪动数组元素，增删效率极低O(N)

核心结论：普通二叉搜索树解决了二分查找增删慢的问题，但存在不平衡退化问题；所以衍生出AVL树、红黑树，兼顾查询和增删效率，也是STL容器真正底层实现。

四、二叉搜索树四大基础操作原理

4.1 插入操作 Insert

1. 树为空：直接新建节点，赋值给根节点
2. 树非空：从根节点开始遍历，比当前节点小往左走，比当前节点大往右走
3. 遇到空位置：挂载新节点；遇到相同key：禁止插入（本文代码实现无重复版本）

4.2 查找操作 Find

1. 从根节点开始比对，key更大向右查找，key更小向左查找
2. 遍历到空节点：查找失败；匹配到key：查找成功
3. 最多遍历树的高度次，效率由树的平衡度决定

4.3 删除操作 Erase

删除是二叉搜索树最难的操作，分为四种场景，可合并为三类处理逻辑：

1. 场景1：待删除节点左右孩子都为空（叶子节点）：直接让父节点指向空，释放当前节点
2. 场景2：待删除节点只有左孩子 / 只有右孩子：父节点直接指向该节点唯一的子节点，绕过当前节点后释放
3. 场景3：待删除节点左右孩子全部存在（最难）：采用替换法，不直接删除当前节点

• 方案一：找右子树最小值节点（右子树最左节点）
• 方案二：找左子树最大值节点（左子树最右节点）
• 交换当前节点和替代节点的key值，转而删除替代节点（替代节点一定满足前两种简单删除场景）

4.4 中序遍历 InOrder

递归顺序：左子树 → 根节点 → 右子树，输出结果升序，用来校验二叉搜索树构建是否合法。

五、二叉搜索树两种模型

实际开发中，二叉搜索树分为两类，对应不同业务场景，也是STL容器两种设计思想：

5.1 Key模型：只存关键字

节点仅存储key值，只需要判断元素是否存在，不存储额外数据。
业务场景：车牌门禁校验、英文单词拼写检测；特点：不支持修改key（破坏树结构），无value可修改。

5.2 Key-Value模型：关键字+映射值

节点存储key和value，key用于排序查找，value存储业务数据。
业务场景：中英字典翻译、停车计费系统、文章单词词频统计；特点：不可修改key，可以随意修改value。

六、完整可运行源码

6.1 Key版二叉搜索树源码

#include <iostream>
using namespace std;

// Key版本节点结构
template<class K>
struct BSTNode
{
    K _key;
    BSTNode<K>* _left;
    BSTNode<K>* _right;

    BSTNode(const K& key)
        :_key(key)
        ,_left(nullptr)
        ,_right(nullptr)
    {}
};

// Key版本二叉搜索树类
template<class K>
class BSTree
{
    typedef BSTNode<K> Node;
public:
    // 构造函数
    BSTree() = default;

    // 析构函数
    ~BSTree()
    {
        Destroy(_root);
        _root = nullptr;
    }

    // 插入节点
    bool Insert(const K& key)
    {
        if (_root == nullptr)
        {
            _root = new Node(key);
            return true;
        }

        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                // 存在重复key，插入失败
                return false;
            }
        }

        // 挂载新节点
        cur = new Node(key);
        if (parent->_key < key)
            parent->_right = cur;
        else
            parent->_left = cur;
        return true;
    }

    // 查找节点
    bool Find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key < key)
                cur = cur->_right;
            else if (cur->_key > key)
                cur = cur->_left;
            else
                return true;
        }
        return false;
    }

    // 删除节点
    bool Erase(const K& key)
    {
        Node* parent = nullptr;
        Node* cur = _root;
        // 先找到需要删除的节点
        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            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 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;
                }
                // 情况3：左右孩子都存在，替换法删除
                else
                {
                    // 找右子树最小节点
                    Node* rightMinP = cur;
                    Node* rightMin = cur->_right;
                    while (rightMin->_left)
                    {
                        rightMinP = rightMin;
                        rightMin = rightMin->_left;
                    }
                    // 数值交换
                    cur->_key = rightMin->_key;
                    // 删除替代节点
                    if (rightMinP->_left == rightMin)
                        rightMinP->_left = rightMin->_right;
                    else
                        rightMinP->_right = rightMin->_right;
                    delete rightMin;
                    return true;
                }
            }
        }
        return false;
    }

    // 公开中序遍历接口
    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }

private:
    // 递归中序遍历
    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;
        _InOrder(root->_left);
        cout << root->_key << " ";
        _InOrder(root->_right);
    }

    // 递归销毁树
    void Destroy(Node* root)
    {
        if (root == nullptr)
            return;
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }

    Node* _root = nullptr;
};

// Key版本测试用例
void TestBSTKey()
{
    int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
    BSTree<int> t;
    for (auto e : a)
        t.Insert(e);
    
    cout << "插入后中序遍历：";
    t.InOrder(); // 升序输出
    
    t.Erase(8);
    cout << "删除8后中序遍历：";
    t.InOrder();

    t.Erase(3);
    cout << "删除3后中序遍历：";
    t.InOrder();
}

int main()
{
    TestBSTKey();
    return 0;
}

6.2 Key-Value版二叉搜索树源码

#include <iostream>
#include <string>
using namespace std;

template<class K, class V>
struct BSTNode
{
    K _key;
    V _value;
    BSTNode<K, V>* _left;
    BSTNode<K, V>* _right;

    BSTNode(const K& key, const V& value)
        :_key(key)
        ,_value(value)
        ,_left(nullptr)
        ,_right(nullptr)
    {}
};

template<class K, class V>
class BSTree
{
    typedef BSTNode<K, V> Node;
public:
    BSTree() = default;

    // 拷贝构造
    BSTree(const BSTree<K, V>& t)
    {
        _root = Copy(t._root);
    }

    // 赋值运算符重载
    BSTree<K, V>& operator=(BSTree<K, V> t)
    {
        swap(_root, t._root);
        return *this;
    }

    // 析构
    ~BSTree()
    {
        Destroy(_root);
        _root = nullptr;
    }

    bool Insert(const K& key, const V& value)
    {
        if (_root == nullptr)
        {
            _root = new Node(key, value);
            return true;
        }

        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }

        cur = new Node(key, value);
        if (parent->_key < key)
            parent->_right = cur;
        else
            parent->_left = cur;
        return true;
    }

    Node* Find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key < key)
                cur = cur->_right;
            else if (cur->_key > key)
                cur = cur->_left;
            else
                return cur;
        }
        return nullptr;
    }

    bool Erase(const K& key)
    {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            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* rightMinP = cur;
                    Node* rightMin = cur->_right;
                    while (rightMin->_left)
                    {
                        rightMinP = rightMin;
                        rightMin = rightMin->_left;
                    }
                    // 交换key
                    cur->_key = rightMin->_key;
                    cur->_value = rightMin->_value;
                    // 删除最小节点
                    if (rightMinP->_left == rightMin)
                        rightMinP->_left = rightMin->_right;
                    else
                        rightMinP->_right = rightMin->_right;
                    delete rightMin;
                    return true;
                }
            }
        }
        return false;
    }

    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }

private:
    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;
        _InOrder(root->_left);
        cout << root->_key << ":" << root->_value << " ";
        _InOrder(root->_right);
    }

    void Destroy(Node* root)
    {
        if (root == nullptr)
            return;
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }

    Node* Copy(Node* root)
    {
        if (root == nullptr)
            return nullptr;
        Node* newRoot = new Node(root->_key, root->_value);
        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);
        return newRoot;
    }

    Node* _root = nullptr;
};

// 测试1：中英字典
void TestDict()
{
    BSTree<string, string> dict;
    dict.Insert("left", "左边");
    dict.Insert("right", "右边");
    dict.Insert("insert", "插入");
    dict.Insert("string", "字符串");

    string str;
    while (cin >> str)
    {
        auto ret = dict.Find(str);
        if (ret)
            cout << "释义：" << ret->_value << endl;
        else
            cout << "无此单词，请重新输入" << endl;
    }
}

// 测试2：水果词频统计
void TestCount()
{
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    BSTree<string, int> countTree;
    for (const auto& str : arr)
    {
        auto ret = countTree.Find(str);
        if (ret == nullptr)
            countTree.Insert(str, 1);
        else
            ret->_value++;
    }
    cout << "水果词频统计结果：" << endl;
    countTree.InOrder();
}

int main()
{
    TestCount();
    // TestDict();
    return 0;
}

七、易错点总结

1. 删除双孩子节点为什么选右子树最小值/左子树最大值？
   ：这两个节点是距离当前key最近的值，替换后不会破坏二叉搜索树有序规则，且这两个节点必然最多只有一个右/左孩子，删除简单
2. 为什么有序数组插入会退化？
   ：1,2,3,4顺序插入，所有节点全部挂在右子树，树高等于节点数，彻底退化成链表
3. key和value能否修改？
   ：绝对不能修改key，会直接破坏树的排序规则；value无限制，可以随意修改
4. 中序遍历一定有序吗？
   ：合法二叉搜索树中序遍历必然升序，这是校验树合法性最简单的方式

八、文末总结

二叉搜索树是树结构和STL关联容器的敲门砖，核心记住三点：

1. 规则：左小右大，递归定义，中序遍历升序
2. 痛点：有序数据插入退化成链表，最坏时间复杂度O(N)
3. 难点：双孩子节点替换删除法，面试手写代码核心考点
   弄懂基础BST之后，再学习AVL树和红黑树会事半功倍，彻底吃透STL关联容器底层原理。