跳到主要内容 C++ 二叉搜索树详解:概念、实现与场景应用 | 极客日志
C++ 算法
C++ 二叉搜索树详解:概念、实现与场景应用 本文介绍了 C++ 中二叉搜索树(BST)的概念、性质及性能分析。详细阐述了插入、查找、删除操作的逻辑与代码实现,包括处理左右子节点为空及非空的情况。同时对比了二分查找的优劣,并展示了 BST 在 Key 搜索及 Key/Value 映射场景中的应用示例,如车牌识别、单词统计等。
GitMaster 发布于 2026/3/29 更新于 2026/4/13 2 浏览在初阶数据结构中,我们学习了树基础的概念以及顺序结构的二叉树——堆和链式结构二叉树的实现。接下来将深入学习二叉搜索树、AVL 树、红黑树,以便更好地理解 set、map 等底层结构。本文将重点讲解二叉搜索树的概念及插入、删除等操作。
1. 二叉搜索树的概念
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
• 若它的左子树不为空,则左子树上所有结点的值都小于等于根结点的值
• 若它的右子树不为空,则右子树上所有结点的值都大于等于根结点的值
• 它的左右子树也分别为二叉搜索树
• 二叉搜索树中可以支持插入相等的值,也可以不支持插入相等的值,具体看使用场景定义,后续我们学习 map/set/multimap/multiset 系列容器底层就是二叉搜索树,其中 map/set 不支持插入相等值,multimap/multiset 支持插入相等值
例如以下左边图示的就是不支持插入相等值得二叉搜索树,右边就是支持插入相等值得二叉搜索树
2. 二叉搜索树的性能分析
最好情况下,在此在二叉搜索树当中最为完全二叉树 (或者接近完全二叉树),其高度为:
例如以下示例:
最差情况下,在此二叉搜索树退化为单支树 (或者类似单支),其高度为:
例如以下示例:
那么通过以上对二叉树最好和最坏情况的分析就可以得出综合而言二叉搜索树增删查改时间复杂度为:
微信扫一扫,关注极客日志 微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown 转 HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
那么通过以上的分析可以看出二叉搜索树这样的效率显然无法满足我们需求的,我们后续需要继续讲解二叉搜索树的变形,平衡二叉搜索树 AVL 树和红黑树,才能适用于我们在内存中存储和搜索数据。
在此你可能会想到在二叉搜索树中查找数据不就类似与二分查找吗,那么直接使用之前学习的二分查找不就可以了吗,二分查找的效率相比二叉搜索树还更好,那为什么还要学习了解二叉搜索树呢?
在此二分查找也可以实现 O(logN) 级别的查找效率,但是二分查找有两大缺陷:
1. 需要存储在支持下标随机访问的结构中,并且有序。
在使用到二分查找时我们使用的是数据对应的下标来实现查找,这就使得当被查找的一系列数据不是存储在数组里时就需要先将数据都存储在数组当中并且还要将数据排序成升序,在这个过程中就会有时间和空间上的损耗了
2. 插入和删除数据效率很低,因为存储在下标随机访问的结构中,插入和删除数据一般需要挪动数据。
在二分查找当中以上提到的缺点其实还不是最致命的,最要命的是当一组数据已经存储在数组当中时并且已经排序好时,如果之后我们要在这组数据当中再插入新的元素或者是要将原数据中的一个元素删除,那么通过之前顺序表的学习我们就知道每插入或者是删除一个元素时间复杂度都为 O(N),若多次进行操作这就使得时间复杂度非常高了
int a[] = {8 , 3 , 1 , 10 , 6 , 4 , 7 , 14 , 13 };
通过以上的分析这里也就体现出了平衡二叉搜索树的价值,在插入元素或者是删除元素都相比使用二分查找要有优势。
3. 二叉搜索树的插入
3.1 插入分析
在此在二叉搜索树当中插入新的节点就要按照以下步骤进行分析:
树为空,则直接新增结点,赋值给 root 指针
树不空,按二叉搜索树性质,插入值比当前结点大往右走,插入值比当前结点小往左走,找到空位置,插入新结点。
如果支持插入相等的值,插入值跟当前结点相等的值可以往右走,也可以往左走,找到空位置,插入新结点。(要注意的是要保持逻辑一致性,插入相等的值不要一会往右走,一会往左走)
例如以下示例:
假设我们要将以下的数组元素依次插入到二叉搜索树当中
int a[] = {8 , 3 , 1 , 10 , 6 , 4 , 7 , 14 , 13 };
这时如果我们要再插入值为 16 的元素在二叉搜索树中过程图就如下所示:
再插入值为 3 的元素在二叉搜索树中过程图就如下所示:
3.2 插入代码实现 在实现二叉搜索树的插入代码之前我们先要来实现二叉搜索树大体的结构代码
在此我们先创建一个 BSTree.h 的头文件在该文件当中来实现二叉搜索树的结构以及各个功能,再创建一个 test.cpp 的文件用于测试我们实现的二叉搜索树的各个功能是否能满足要求
实现了文件的创建之后接下来就来实现二叉搜索树的大体结构。在此由于二叉搜索树是由各个节点构成的,那么和之前实现链式结构的二叉树一样先要实现表示节点的结构体
在此就创建一个结构体 BSTreeNode 来表示二叉树内节点,在节点当中有三个变量分别是 _key 表示节点内的数据、_left 存储该节点左孩子节点的指针、_right 存储该节点右孩子节点的指针。并且将该结构体实现成模板这样就可以支持节点内的元素是任意类型的数据,还有在结构体当中还实现了构造函数。
实现了节点的结构体之后接下来就可以来实现表示二叉搜索树的类,在此我们将类命名为 BSTree,实现的是模板类,实现的大体结构如下所示:
template <class K > class BSTree { typedef BSTreeNode<K> Node; public :
注:以下实现的插入函数是数据不支持冗余的情况也就是二叉树当中不支持插入相等的值
bool Insert (const K& key) {
4. 二叉搜索树的查找
4.1 查找分析
在二叉搜索树中查找节点就要按照以下步骤进行分析:
从根开始比较,查找 x,x 比根的值大则往右边走查找,x 比根值小则往左边走查找。
最多查找高度次,走到到空,还没找到,这个值不存在。
如果不支持插入相等的值,找到 x 即可返回
如果支持持插入相等的值,意味着有多个 x 存在,一般要求查找中序的第一个 x。
当要查找 3 时,要找到 1 的右孩子的那个 3 值返回
4.2 查找代码实现 在进行了二叉搜索树的节点查找的分析之后接下来我们就来实现查找代码
注:以下实现的查找函数是数据不支持冗余的情况也就是二叉树当中不支持插入相等的值
Node* Find (const K& key) {
5. 二叉搜索树的删除
5.1 删除分析 在二叉搜索树当中节点的删除相比插入和查找就复杂一些了,在此会出现以下的多种情况接下来就来一一分析
当要删除节点的节点左右孩子节点都为空时就需要把 N 结点的父亲对应孩子指针指向空,直接删除 N 结点
在以上二叉搜索树当中要删除值为 1 的节点就需要将节点 1 删除之后再将其父节点的左孩子节点指向空
2. 要删除的结点 N 左孩子位空,右孩子结点不为空
当要删除节点的节点左孩子节点为空时就需要把 N 结点的父亲对应孩子指针指向 N 的右孩子,之后直接删除 N 结点
在以上二叉搜索树当中要删除值为 10 的节点就需要将其父节点的左孩子变为原节点的右孩子节点之后再将节点 10 删除
3. 要删除的结点 N 右孩子位空,左孩子结点不为空
当要删除节点的节点右孩子节点为空时就需要把 N 结点的父亲对应孩子指针指向 N 的左孩子,之后直接删除 N 结点
在以上二叉搜索树当中要删除值为 14 的节点就需要将其父节点的左孩子变为原节点的左孩子节点之后再将节点 14 删除
当要删除的节点左右孩子节点都不为空时,这是就不能像以上的情况一样简单的改变要删除节点的父节点指针,这时由于无法直接删除 N 结点,这是因为 N 的两个孩⼦无处安放,只能用替换法删除 。在此根据二叉搜索树的性质就需要找 N左子树的值最大结点 R(最右结点)或者 N 右子树的值最小结点 R(最左结点) 替代 N ,因为这两个结点中任意⼀个,放到 N 的位置,都满足⼆叉搜索树的规则。替代 N 的意思就是 N 和 R 的两个结点的值交换,转而变成删除 R 结点,R 结点符合情况 2 或情况 3,可以直接删除。
在以上二叉搜索树当中要删除节点值为 8 的节点和值为 3 的节点,由于这两个节点都是左右孩子节点都不为空的节点,因此要删除值为 8 的节点就需要找到其左子树最右的节点或者是右子树最左的节点(在此我们是找右子树最左的节点)
注:要删除值为 3 的节点和以上的方式也类型在此就不再细致的讲解
5.2 删除代码实现 bool Erase (const K& key) {
6. 二叉搜索树遍历 由于二叉搜索树的性质一棵二叉搜索树中序遍历输出的结果就是递增的,那么接下来我们就试着来实现中序遍历的代码
void Inorder () { _Inorder(_root); cout << endl; } void _Inorder(Node* root) { if (root == nullptr ) { return ; } _Inorder(root->left); cout << root->_key << " " ; _Inorder(root->right); }
在此我们实现的中序遍历代码如上所示,那么这时你可能就会有疑问了,为什么要实现两个中序遍历的函数,不是直接使用一个函数就可以满足要求了吗?
在此要考虑到的是在 BsTree 类以外用户是无法得到二叉搜索树的根节点的,但是在调用中序遍历的函数根据之前我们使用递归的方式是需要一开始就需要将二叉树的根结点作为中序遍历函数的参数的。因此为了解决该问题就再在 BSTree 类内实现一个函数来调用中序遍历的成员函数,由于是在类的内部在此是可以访问私有的成员变量的,在类外部用户要使用中序遍历时就只需要调用无参的成员函数 Inorder 就可以得到二叉搜索树中序遍历的结果了。
7. 二叉搜索树完整代码 #include <iostream> using namespace std; template<class K> struct BSTreeNode { K _key; BSTreeNode<K> * left; BSTreeNode<K> * right; BSTreeNode(const K& key) :_key(key) , left(nullptr) , right(nullptr) { } };
template <class K > class BSTree { typedef BSTreeNode<K> Node; public :
8. 二叉搜索树 key 和 key/value 使用场景
8.1 key 搜索场景
只有 key 作为关键码,结构中只需要存储 key 即可,关键码即为需要搜索到的值,搜索场景只需要判断 key 在不在。key 的搜索场景实现的二叉树搜索树支持增删查,但是不支持修改,修改 key 破坏搜索树结构了。
在以上我们了解实现的二叉搜索树其实是适用于 key 的场景,那么接下来就来看看那么场景是属于 key 的场景
**场景 1:**小区无人值守车库,小区车库买了车位的业主车才能进小区,那么物业会把买了车位的业主的车牌号录入后台系统,车辆进入时扫描车牌在不在系统中,在则抬杆,不在则提示非本小区车辆,无法进入。
**场景 2:**检查一篇英文文章单词拼写是否正确,将词库中所有单词放入二叉搜索树,读取文章中的单词,查找是否在二叉搜索树中,不在则波浪线标红提示。
8.2 key/value 搜索场景
每一个关键码 key,都有与之对应的值 value,value 可以任意类型对象。树的结构中 (结点) 除了需要存储 key 还要存储对应的 value,增/删/查还是以 key 为关键字走二叉搜索树的规则进行比较,可以快速查找到 key 对应的 value。key/value 的搜索场景实现的二叉树搜索树支持修改,但是不支持修改 key,修改 key 破坏搜索树结构了,可以修改 value。
接下来就来将以上我们实现的 key 二叉搜索树修改为 key/value 二叉搜索树代码,实现代码如下所示:
#include <iostream> using namespace std; template<class K,class V> struct BSTreeNode { K _key; V _value; BSTreeNode<K ,V> * left; BSTreeNode<K ,V> * right; BSTreeNode(const K& key, const V& value) :_key(key) ;_value(value) , left(nullptr) , right(nullptr) { } };
template <class K ,class V > class BSTree { typedef BSTreeNode<K,V> Node; public :
在以上我们了解实现的二叉搜索树其实是适用于 key 的场景,那么接下来就来看看那么场景是属于 key 的场景
**场景 1:**商场无人值守车库,入口进场时扫描车牌,记录车牌和入场时间,出口离场时,扫描牌,查找入场时间,用当前时间 - 入场时间计算出停车时长,计算出停车费用,缴费后抬杆,车辆离场。
**场景 1:**简单中英互译字典,树的结构中 (结点) 存储 key(文) 和 vlaue(中文),搜索时输入英文,则同时查找到了英文对应的中文。
**场景 3:**统计一篇文章中单词出现的次数,读取一个单词,查找单词是否存在,不存在这个说明第一次出现,(单词,1),单词存在,则++ 单词对应的次数。
以下的两个简单的示例就是使用二叉搜索树的 key/val 来解决
#include "BSTree.h" int main() {