二叉搜索树

‎ദ്ദിᵔ.˛.ᵔ₎

440人浏览 · 2026-04-16 11:23:59

‎ദ്ദിᵔ.˛.ᵔ₎ · 2026-04-16 11:23:59 发布

二叉搜索树（BST）是数据结构中排序、查找、动态增删的核心结构，也是STL中map/set、multimap/multiset的底层实现基础。本文把课件里的全部知识点完整梳理，从定义到性能、四大操作、完整代码、两大应用场景

一、二叉搜索树（BST）核心定义

二叉搜索树又称二叉排序树，满足以下严格性质：

左子树不为空 → 左子树上所有节点值 ≤ 根节点值
右子树不为空 → 右子树上所有节点值 ≥ 根节点值
左右子树本身也必须是二叉搜索树

关于重复值的规则

支持重复值：插入时统一向左/向右，保持逻辑一致
不支持重复值：遇到相等直接返回插入失败
对应STL：
- map/set：不支持重复key
- multimap/multiset：支持重复key

二、二叉搜索树性能分析（必考点）

BST的效率完全由树的高度决定：

最优情况：完全二叉树/接近完全二叉树
高度 = log₂N，增删查改时间复杂度 O(logN)
最差情况：退化成单支树（链表）
高度 = N，增删查改时间复杂度 O(N)

为什么不用二分查找替代？

二分查找虽然也是O(logN)，但有致命缺陷：

必须放在支持下标随机访问的有序结构（数组）
插入/删除需要大量挪动数据，效率极低

因此：二叉搜索树适合动态数据，二分查找适合静态有序数据。
为了解决BST退化问题，后续会学习AVL树、红黑树（平衡二叉搜索树）。

三、二叉搜索树四大核心操作

1. 插入操作

步骤：

树为空 → 新建节点直接作为根节点
树不为空：
- 插入值 > 当前节点 → 向右走
- 插入值 < 当前节点 → 向左走
找到空位置，插入新节点
重复值：统一左/右插入，不可左右混用

2. 查找操作

步骤：

从根节点开始比较
目标值 > 当前节点 → 右子树查找
目标值 < 当前节点 → 左子树查找
走到空节点 → 说明不存在
不支持重复值：找到即返回
支持重复值：返回中序第一个匹配节点

3. 删除操作（最难，分4种情况）

设待删除节点为N，先查找是否存在，不存在直接返回false。

情况1：N左右孩子都为空

父节点对应孩子指针置空，直接删除N

情况2：N左孩子为空，右孩子不为空

父节点指向N的右孩子，删除N

情况3：N右孩子为空，左孩子不为空

父节点指向N的左孩子，删除N

情况4：N左右孩子都不为空（核心难点）

无法直接删除，使用替换法
选择两个替换节点之一：
1. N的左子树最大值（最右节点）
2. N的右子树最小值（最左节点）
交换N与替换节点的值
此时问题转化为删除替换节点（必属于情况1/2/3）

4. 中序遍历

二叉搜索树中序遍历结果一定是升序序列，这是判断BST的重要依据。

四、C++ 完整代码实现

1. 纯Key版二叉搜索树

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

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

template<class K>
class BSTree
{
    typedef BSTNode<K> Node;
public:
    // 插入
    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
            {
                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
            {
                // 左孩子为空
                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;
                    }

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

private:
    Node* _root = nullptr;
};

2. Key/Value版二叉搜索树（键值对）

支持key映射value，key不可改，value可改，是字典、统计、索引场景的标准结构。
完整包含：插入、查找、删除、拷贝构造、赋值重载、析构、销毁、拷贝。

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

                    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 << ":" << root->_value << endl;
        _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;
    }

private:
    Node* _root = nullptr;
};

五、二叉搜索树两大使用场景

场景1：纯Key模型（只判断存在与否）

只存key，用于存在性检查，不支持修改key。
典型例子：

小区车库：车牌白名单校验，在则放行
单词拼写检查：文章单词与词库比对，不存在标红

场景2：Key/Value模型（键值映射）

每个key对应一个value，按key查找，可修改value，不可修改key。
典型例子：

中英字典：英文key → 中文value
商场停车：车牌key → 入场时间value，计费使用
词频统计：单词key → 出现次数value

场景测试代码

字典示例

int main()
{
    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;
    }
    return 0;
}

词频统计示例

int main()
{
    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++;
    }

    countTree.InOrder();
    return 0;
}

六、全文总结

二叉搜索树核心：左小右大，中序有序
效率：最优O(logN)，最坏O(N)，退化是最大问题
操作难点：删除（替换法）
两种模型：
- 纯key：存在性检查
- key/value：键值映射、统计、索引
地位：STL关联容器底层基础，进阶平衡二叉树的前提

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

让AI推荐你，比让客户搜到你更高效

AtomGit开源社区

养老服务行业AI搜索优化服务商选型：4个技术评估标准

AtomGit开源社区

HoRain云--Python 命令模式

命令模式通过将操作封装成对象，实现了调用者与接收者的解耦，提供了强大的扩展能力。虽然会增加一些代码复杂度，但在需要撤销/重做、操作队列、日志记录等场景下，命令模式是不可或缺的设计模式。命令模式将"做什么"和"谁来做"分离支持撤销、重做、队列等高级功能易于扩展新的命令在 GUI 应用、事务系统、游戏开发中广泛应用❤️❤️❤️本人水平有限，如有纰漏，欢迎各位大佬评论批评指正！😄😄😄👍 👍 ?