@TOC

前言

前面我们讲了C语言的基础知识，也了解了一些初阶数据结构，并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载，引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ，也了解了C++中的模版，以及学习了几个STL的结构也相信大家都掌握的不错，接下来博主将会带领大家继续学习有关C++比较重要的知识点——搜索二叉树（二叉树进阶） 。下面话不多说坐稳扶好咱们要开车了😍

一、搜索二叉树简介

1. 概念

搜索二叉树，也称为二叉搜索树（Binary Search Tree，BST），是一种二叉树的特殊形式。它满足以下条件：

1. 有序性：对于任意节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。
2. 唯一性：每个节点的值唯一，不存在相同值的节点。
3. 递归结构：整个树的结构由左子树、右子树和根节点组成，其中左子树和右子树也是搜索二叉树。

2. 基本操作

⭕搜索操作

• 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
• 最多查找高度次，走到到空，还没找到，这个值不存在。

在搜索二叉树中查找一个特定值的操作很简单。从根节点开始，如果目标值等于当前节点的值，则找到了目标节点；如果目标值小于当前节点的值，则在左子树中继续搜索；如果目标值大于当前节点的值，则在右子树中继续搜索。通过递归或循环，可以在树中进行有效的搜索。

🍪搜索操作基本代码（非递归）

bool Find(const K& key)
{
   
    Node* ret = _root;

    // 循环查找节点，直到找到与 key 匹配的节点或遍历完整个树
    while (ret)
    {
   
        // 如果当前节点的键值大于 key，继续在左子树中查找
        if (ret->_key > key)
        {
   
            ret = ret->_left;
        }
        // 如果当前节点的键值小于 key，继续在右子树中查找
        else if (ret->_key < key)
        {
   
            ret = ret->_right;
        }
        // 如果当前节点的键值等于 key，找到匹配节点，返回 true
        else
        {
   
            return true;
        }
    }

    // 遍历完整个树仍未找到匹配节点，返回 false
    return false;
}

该函数接收一个键值 key，表示需要查找的值。函数首先将根节点指针 _root 赋值给临时指针变量 ret。然后通过循环遍历树进行查找，直到找到与 key 匹配的节点或遍历完整个树。

在循环中，根据当前节点的键值与 key 的比较结果决定下一步的查找方向：

• 如果当前节点的键值大于 key，继续在左子树中查找；
• 如果当前节点的键值小于 key，继续在右子树中查找；
• 如果当前节点的键值等于 key，找到匹配节点，返回 true。

当遍历完整个树仍未找到匹配节点时，返回 false 表示未找到。

⭕插入操作

• 树为空，则直接新增节点，赋值给root指针
• 树不空，按二叉搜索树性质查找插入位置，插入新节点

要向搜索二叉树中插入新节点，需要找到合适的位置。从根节点开始，与当前节点的值比较，根据值的大小决定是在左子树还是右子树中进行插入。重复这个过程，直到找到一个空的位置，然后将新节点插入其中。

🍪插入操作基本代码（非递归）

bool Insert(const K& key)
{
   
    // 如果根节点为空，直接将 key 作为根节点创建
    if (_root == nullptr)
    {
   
        _root = new Node(key);
        return true;
    }
    Node* ret = _root;
    Node* parent = nullptr;

    // 找到 key 应该插入的位置
    while (ret)
    {
   
        // 如果 key 小于当前节点的键值，继续在左子树查找
        if (key < ret->_key)
        {
   
            parent = ret;
            ret = ret->_left;
        }
        // 如果 key 大于当前节点的键值，继续在右子树查找
        else if (key > ret->_key)
        {
   
            parent = ret;
            ret = ret->_right;
        }
        // 如果 key 已经存在于树中，返回 false
        else
        {
   
            return false;
        }
    }

    // 创建新节点，将其插入正确的位置
    Node* cur = new Node(key);
    if (parent->_key > key)
    {
   
        parent->_left = cur;
    }
    else
    {
   
        parent->_right = cur;
    }
    return true;
}

该函数接收一个键值 key，表示需要插入的值。函数首先判断根节点是否为空，如果为空，则直接将 key 作为根节点插入并返回 true。否则，使用循环找到 key 需要插入的位置：

• 如果 key 小于当前节点的键值，继续在左子树查找；
• 如果 key 大于当前节点的键值，继续在右子树查找；
• 如果 key 等于当前节点的键值，则说明值已经存在于树中，返回 false。

当找到正确的位置时，创建一个新的节点 cur，并将其插入到树中。具体实现如下：

• 如果 key 小于父亲节点的键值，将 cur 插入父节点的左子树中；
• 如果 key 大于父亲节点的键值，将 cur 插入父节点的右子树中。

插入完成后，返回 true 表示插入成功。

⭕删除操作

删除节点的过程相对复杂，需要考虑不同的情况，主要分为以下三种情况处理：

1. 删除节点没有子节点（叶子节点）：直接将该节点删除即可，将其父节点指向它的指针置为 NULL。

2. 删除节点有一个子节点：将该节点的子节点替代该节点的位置，将该节点的父节点指向它的指针直接指向子节点。

3. 删除节点有两个子节点：这是最复杂的情况。需要找到该节点的后继节点或者前驱节点来替代该节点的位置。后继节点是指比当前节点大的最小节点，前驱节点是指比当前节点小的最大节点。

   • 找到后继节点的方法是：在当前节点的右子树中找到值最小的节点，即右子树中最左边的节点，然后将其值复制到待删除节点的位置，再删除后继节点。

   • 找到前驱节点的方法是：在当前节点的左子树中找到值最大的节点，即左子树中最右边的节点，然后将其值复制到待删除节点的位置，再删除前驱节点。

     🍪删除操作基本代码（非递归）

bool Erase(const K& key)
{
   
    Node* ret = _root;
    Node* parent = nullptr;

    // 循环查找节点，直到找到匹配的节点或遍历完整个树
    while (ret)
    {
   
        // 如果 key 小于当前节点的键值，继续在左子树查找
        if (key < ret->_key)
        {
   
            parent = ret;
            ret = ret->_left;
        }
        // 如果 key 大于当前节点的键值，继续在右子树查找
        else if (key > ret->_key)
        {
   
            parent = ret;
            ret = ret->_right;
        }
        // 如果找到匹配的节点
        else
        {
   
            // 删除节点
            // 1. 如果当前节点的左子树为空
            if (ret->_left == nullptr)
            {
   
                // 如果是根节点
                if (_root->_key == key)
                {
   
                    Node* tmp = _root;
                    _root = _root->_right;
                    delete tmp;
                    return true;
                }
                else
                {
   
                    // 如果是父节点的左子节点
                    if (parent->_left == ret)
                    {
   
                        parent->_left = ret->_right;
                    }
                    // 如果是父节点的右子节点
                    else
                    {
   
                        parent->_right = ret->_right;
                    }
                    delete ret;
                }
            }
            // 2. 如果当前节点的右子树为空
            else if (ret->_right == nullptr)
            {
   
                // 如果是根节点
                if (_root->_key == key)
                {
   
                    Node* tmp = _root;
                    _root = _root->_left;
                    delete tmp;
                    return true;
                }
                else
                {
   
                    // 如果是父节点的左子节点
                    if (parent->_left == ret)
                    {
   
                        parent->_left = ret->_left;
                    }
                    // 如果是父节点的右子节点
                    else
                    {
   
                        parent->_right = ret->_left;
                    }
                    delete ret;
                }
            }
            // 3. 如果当前节点的左右子树都不为空
            else
            {
   
                // 找到右子树中最小的节点，用来替代当前节点
                Node* pminRight = ret;
                Node* minRight = ret->_right;
                while (minRight->_left)
                {
   
                    pminRight = minRight;
                    minRight = minRight->_left;
                }
                // 将右子树中最小节点的值赋给当前节点，并删除最小节点
                ret->_key = minRight->_key;
                if (pminRight->_left == minRight)
                {
   
                    pminRight->_left = minRight->_right;
                }
                else
                {
   
                    pminRight->_right = minRight->_right;
                }
                delete minRight;
            }
            return true;
        }
    }

    // 遍历完整个树仍未找到匹配节点，返回 false
    return false;
}

该函数接收一个键值 key，表示需要删除的值。函数首先将根节点指针 _root 赋值给临时指针变量 ret，并初始化父节点指针 parent 为 nullptr。然后通过循环遍历树进行查找，直到找到与 key 匹配的节点或遍历完整个树。

在循环中，根据待删除节点的键值与 key 的比较结果决定下一步的查找方向：

• 如果 key 小于当前节点的键值，继续在左子树中查找；
• 如果 key 大于当前节点的键值，继续在右子树中查找；
• 如果当前节点的键值等于 key，找到匹配节点，并执行删除操作。

删除操作分为以下三种情况：

1. 如果当前节点的左子树为空：将当前节点的右子树链接到父节点的对应位置，并删除当前节点。
2. 如果当前节点的右子树为空：将当前节点的左子树链接到父节点的对应位置，并删除当前节点。
3. 如果当前节点的左右子树都不为空：需要找到当前节点右子树中最小的节点（即右子树的最左下角节点），将该节点的值赋给当前节点，然后删除最小节点。

在执行删除操作时，可能存在以下两种特殊情况：

• 如果当前节点是根节点：需要更新 _root 指针，让其指向新的根节点。
• 如果当前节点是某个节点的左子节点或右子节点：需要将该节点的父节点链接到删除节点的子节点，与该节点相邻的子树会被删除，然后释放删除节点的内存。

最后，如果遍历整个树仍未找到匹配节点，说明该节点不存在，函数返回 false。

二、搜索二叉树的实现

1. 非递归实现

namespace yws
{
   
template<class K>
    struct BSTreeNode
    {
   
        // 二叉搜索树节点的定义
        BSTreeNode(const K& key)
               : _left(nullptr)
            , _right(nullptr)
            , _key(key)
        {
   }

        BSTreeNode<K>* _left;   // 左子节点指针
        BSTreeNode<K>* _right;  // 右子节点指针
        K _key;                 // 节点存储的键值
    };
    template<class K>
    class BSTree
    {
   
        typedef BSTreeNode<K> Node;
    public:
        //构造
        BSTree()
            :_root(nullptr)
            {
   }

        //拷贝构造
        BSTree(const BSTree<K>& t)
        {
   
            _root = Copy(t._root);
        }
        //赋值构造
        BSTree<K>& operator=(BSTree<K> t)
        {
   
            std::swap(_root, t._root);
            return *this;
        }

        //析构
        ~BSTree()
        {
   
            Destory(_root);
        }
        bool Insert(const K& key)
        {
   
           // 如果根节点为空，直接将 key 作为根节点创建
           if (_root == nullptr)
           {
   
               _root = new Node(key);
               return true;
           }
           Node* ret = _root;
           Node* parent = nullptr;

           // 找到 key 应该插入的位置
           while (ret)
           {
   
               // 如果 key 小于当前节点的键值，继续在左子树查找
               if (key < ret->_key)
               {
   
                   parent = ret;
                   ret = ret->_left;
               }
               // 如果 key 大于当前节点的键值，继续在右子树查找
               else if (key > ret->_key)
               {
   
                   parent = ret;
                   ret = ret->_right;
               }
               // 如果 key 已经存在于树中，返回 false
               else
               {
   
                   return false;
               }
           }

           // 创建新节点，将其插入正确的位置
           Node* cur = new Node(key);
           if (parent->_key > key)
           {
   
               parent->_left = cur;
           }
           else
           {
   
               parent->_right = cur;
           }
           return true;
        }
        bool Find(const K& key)
        {
   
            Node* ret = _root;

            // 循环查找节点，直到找到与 key 匹配的节点或遍历完整个树
            while (ret)
            {
   
                // 如果当前节点的键值大于 key，继续在左子树中查找
                if (ret->_key > key)
                {
   
                    ret = ret->_left;
                }
                // 如果当前节点的键值小于 key，继续在右子树中查找
                else if (ret->_key < key)
                {
   
                    ret = ret->_right;
                }
                // 如果当前节点的键值等于 key，找到匹配节点，返回 true
                else
                {
   
                    return true;
                }
            }

            // 遍历完整个树仍未找到匹配节点，返回 false
            return false;
        }
        bool Erase(const K& key)
        {
   
            Node* ret = _root;
            Node* parent = nullptr;

            // 循环查找节点，直到找到匹配的节点或遍历完整个树
            while (ret)
            {
   
                // 如果 key 小于当前节点的键值，继续在左子树查找
                if (key < ret->_key)
                {
   
                    parent = ret;
                    ret = ret->_left;
                }
                // 如果 key 大于当前节点的键值，继续在右子树查找
                else if (key > ret->_key)
                {
   
                    parent = ret;
                    ret = ret->_right;
                }
                // 如果找到匹配的节点
                else
                {
   
                    // 删除节点
                    // 1. 如果当前节点的左子树为空
                    if (ret->_left == nullptr)
                    {
   
                        // 如果是根节点
                        if (_root->_key == key)
                        {
   
                            Node* tmp = _root;
                            _root = _root->_right;
                            delete tmp;
                            return true;
                        }
                        else
                        {
   
                            // 如果是父节点的左子节点
                            if (parent->_left == ret)
                            {
   
                                parent->_left = ret->_right;
                            }
                            // 如果是父节点的右子节点
                            else
                            {
   
                                parent->_right = ret->_right;
                            }
                            delete ret;
                        }
                    }
                    // 2. 如果当前节点的右子树为空
                    else if (ret->_right == nullptr)
                    {
   
                        // 如果是根节点
                        if (_root->_key == key)
                        {
   
                            Node* tmp = _root;
                            _root = _root->_left;
                            delete tmp;
                            return true;
                        }
                        else
                        {
   
                            // 如果是父节点的左子节点
                            if (parent->_left == ret)
                            {
   
                                parent->_left = ret->_left;
                            }
                            // 如果是父节点的右子节点
                            else
                            {
   
                                parent->_right = ret->_left;
                            }
                            delete ret;
                        }
                    }
                    // 3. 如果当前节点的左右子树都不为空
                    else
                    {
   
                        // 找到右子树中最小的节点，用来替代当前节点
                        Node* pminRight = ret;
                        Node* minRight = ret->_right;
                        while (minRight->_left)
                        {
   
                            pminRight = minRight;
                            minRight = minRight->_left;
                        }
                        // 将右子树中最小节点的值赋给当前节点，并删除最小节点
                        ret->_key = minRight->_key;
                        if (pminRight->_left == minRight)
                        {
   
                            pminRight->_left = minRight->_right;
                        }
                        else
                        {
   
                            pminRight->_right = minRight->_right;
                        }
                        delete minRight;
                    }
                    return true;
                }
            }

            // 遍历完整个树仍未找到匹配节点，返回 false
            return false;
        }
    protected:
        Node* Copy(Node* root)
        {
   
            if (root == nullptr)
            {
   
                return nullptr;
            }
            Node newnode = new Node(root->_key);
            newnode->_left = Copy(root->_left);
            newnode->_right = Copy(root->_right);
            return newnode;
        }

        void Destory(Node*& root)
        {
   
            if (root == nullptr)
                return;
            Destory(root->_right);
            Destory(root->_left);
            delete root;
            root = nullptr;
        }
    }
    private:
        Node* _root = nullptr;
    };
}

2. 递归实现

namespace yws
{
   
    template<class K>
    struct BSTreeNode
    {
   
        BSTreeNode(const K& key)
            : _left(nullptr)
            , _right(nullptr)
            , _key(key)
        {
   }

        BSTreeNode<K>* _left;
        BSTreeNode<K>* _right;
        K _key;
    };
    template<class K>
    class BSTree
    {
   
        typedef BSTreeNode<K> Node;
    public:

        //构造
        BSTree()
            :_root(nullptr)
            {
   }

        //拷贝构造
        BSTree(const BSTree<K>& t)
        {
   
            _root = Copy(t._root);
        }
        //赋值构造
        BSTree<K>& operator=(BSTree<K> t)
        {
   
            std::swap(_root, t._root);
            return *this;
        }

        //析构
        ~BSTree()
        {
   
            Destory(_root);
        }

        void Inorder() // 中序遍历
        {
   
            _Inorder(_root);
            cout << endl;
        }

        //递归版本实现
        bool FindR(const K& key)
        {
   
            return _FindR(_root, key);
        }
        bool InsertR(const K& key)
        {
   
            return _InsertR(_root, key);
        }
        bool EraseR(const K& key)
        {
   
            return _EraseR(_root, key);
        }


    protected:
        Node* Copy(Node* root)
        {
   
            if (root == nullptr)
            {
   
                return nullptr;
            }
            Node newnode = new Node(root->_key);
            newnode->_left = Copy(root->_left);
            newnode->_right = Copy(root->_right);
            return newnode;
        }

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


        void _Inorder(Node* root)
        {
   
            if (root == nullptr)
            {
   
                return;
            }
            _Inorder(root->_left);
            cout << root->_key << ' ';
            _Inorder(root->_right);
        }


        bool _FindR(Node* root, const K& key)
        {
   
            if (root == nullptr)
            {
   
                return false;
            }
            if (key < root->_key)
            {
   
                _FindR(root->_left, key);
            }
            else if (key > root->_key)
            {
   
                _FindR(root->_right, key);
            }
            else
            {
   
                return true;
            }
        }
        bool _InsertR(Node*& root, const K& key)
        {
   
            if (root == nullptr)
            {
   
                root = new Node(key);
                return true;
            }
            if (key < root->_key)
            {
   
                _InsertR(root->_left, key);
            }
            else if (key > root->_key)
            {
   
                _InsertR(root->_right, key);
            }
            else
            {
   
                return false;
            }
        }

        bool _EraseR(Node*& root, const K& key)
        {
   
            if (root == nullptr)
            {
   
                return false;
            }
            if (key > root->_key)
            {
   
                return _EraseR(root->_right, key);
            }
            else if (key < root->_key)
            {
   
                return _EraseR(root->_left, key);
            }
            else
            {
   
                //开始删除
                Node* del = root;
                //1.左节点为空
                if (root->_left == nullptr)
                {
   
                    root = root->_right;
                }
                //2.右节点为空
                else if (root->_right == nullptr)
                {
   
                    root = root->_left;
                }
                //3.左右节点都不为空
                else
                {
   
                    //找右树的最小节点，代替

                    Node* minRight = root->_right;
                    while (minRight->_left)
                    {
   
                        minRight = minRight->_left;
                    }
                    root->_key = minRight->_key;
                    return _EraseR(root->_right, root->_key);

                }
                delete del;
                return true;
            }
        }

    private:
        Node* _root = nullptr;
    };
}

三、搜索二叉树的应用

1. K模型

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。因此，K模型对于不需要复杂数据处理功能的应用来说是一种轻量级的数据管理方案。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

• 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树。
• 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

  2. KV模型

  KV模型：每一个关键码key，都有与之对应的值Value，即 <Key, Value> 的键值对。该种方式在现实生活中非常常见

假设有一个存储学生信息的系统，每个学生信息仅包括学生的唯一ID和学生的姓名。这种情况下，我们可以使用K模型进行存储，其中学生的ID作为key，学生姓名作为value。

如下所示是几个学生的数据：

使用KV模型存储这些数据时，只需要记录学生ID作为key，对应的学生姓名作为value。例如，使用搜索二叉树来存储学生信息，可以根据学生ID快速查找到对应的学生姓名。这个例子展示了如何将KV模型与搜索二叉树结合，实现数据存储和检索的需求。

当需要查询某个学生的姓名时，只需要在二叉树中查找对应的学生ID，然后返回该学生的姓名即可。

四、搜索二叉树的性能分析

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$log_2 N$
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\frac{N}{2}$

如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后面的AVL树和红黑树就可以完美解决上面的问题了。

总结

搜索二叉树是一种常用的数据结构，用于存储和检索数据。搜索二叉树的应用，包括K模型和KV模型。K模型指的是只存储键而不存储关联值的数据模型。KV模型则是使用键值对来存储和访问数据的一种模型，可以用搜索二叉树实现。

最后，搜索二叉树的性能取决于树的平衡程度，理想情况下的时间复杂度为O(log n)，但如果树不平衡，性能会下降至O(n)。为了保持树的平衡，可以采用平衡二叉树的变种，如红黑树或AVL树。

综上所述，搜索二叉树是一种重要的数据结构，具有广泛的应用。了解搜索二叉树的基本操作、实现方法和性能分析，对于合理选择和使用数据结构，提高数据操作效率具有重要意义。

温馨提示

感谢您对博主文章的关注与支持！另外，我计划在未来的更新中持续探讨与本文相关的内容，会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新，不要错过任何精彩内容！

再次感谢您的支持和关注。期待与您建立更紧密的互动，共同探索C++、算法和编程的奥秘。祝您生活愉快，排便顺畅！