当前位置：首页 > news >正文

C++笔记-二叉搜索树(包括key，key/value搜索场景等)

news 来源：原创 2025/8/21 14:52:15

1.二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1.若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值若它的右子树不为空，则2.右子树上所有结点的值都大于等于根结点的值
3.它的左右子树也分别为二叉搜索树
4.二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续我们要讲的map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。

这幅图呢就是一个基本的二叉搜索树，可以看出，每一棵树都是一个二叉搜索树。为什么叫二叉搜索树呢？

我们根据上面二叉搜索树的特点可以发现这个特殊的树非常适合搜索某个数据，比如：我们要查找10这个数，大家可以查查需要几次就可以找到。

并且大家可以用中序遍历的方法打印出二叉搜索树的值就会发现是有序的，这是基于二叉搜索树的特征来实现的。

二叉搜索树的特征就决定它查找数据效率很高，下面我们就来探讨一下二叉搜索树的性能。

2.二叉搜索树的性能分析

以上面这幅图为例，我们如果要查找10，经过查找就可以发现只需要查找树的高度次也就是：log2N，但现实每次效率都能做到这么高吗？
答案显然不是的，就比如：

就比如这样的单支树，我现在要找1这个数，我们发现查找次数是其高度次：N。

所以二叉搜索树的搜索效率也是根据树的类型而定，我们总结一下：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为:log2 N

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为:N所以综合而言二叉搜索树增删查改时间复杂度为:0(N)
那么这样的效率显然是无法满足我们需求的，所以在二叉搜索树的基础上发展出平衡二叉搜索树，也就是后面要讲的AVL树和红黑树。

为什么叫平衡二叉搜索树呢？

就是它会自动平衡左右子树结点的数量，让其左右子树的结点数量尽可能相等。我们设想一下，经过平衡操作后，是不是就可以保证效率就是log2N。

有人可能对时间复杂度log2N没什么概念，比如：在1000000个数据中查找某个值，最多才查找20次，在10亿个数据中查找某个值，最多也才查找30次，这个效率是很高的。
另外需要说明的是，二分查找也可以实现0(log2N)级别的查找效率，但是二分查找有两大缺陷:
1.需要存储在支持下标随机访问的结构中，并且有序。
2.插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
这里也就体现出了平衡二叉搜索树的价值。

3.二叉搜索树的实现

这里我实现的二叉搜索树是不支持插入相同的值的。

并且以这个二叉搜索树为例来进行下面的操作。

3.1二叉搜索树的初始化

相信看到这个初始化的基本模型，大家就能猜到我要用链表来实现二叉搜索树，这个模型和之前我们实现的list很相似，不过要比list简单许多。并且二叉树的结构在二叉树的章节已经讲过，所以这里就不过多赘述了。

这里没有写构造函数是因为此时默认的构造函数就够我们使用了，后面会有不得不写构造函数的情况，这里先暂时不写。

3.1二叉搜索树的插入

插入的思路很简单，根据二叉搜索树的特征，我们先跟根结点中的值进行比较，如果比它大，就走右边，比它小就走左边，然后更新cur的位置，直至找到空的位置。

那么我们又要思考一个问题：cur找到了相应的位置，并创建结点，那么怎么让其和树连接起来呢？

显然，我们要定义一个变量parent来记录cur上一个走的位置。找到以后判断cur和parent值的大小，这里其实就是判断cur是在parent的左边还是右边。

经过上述操作我们就能把一个值按照二叉搜索树的特征插入到树中。

注意：

1.这里把插入的返回值设置成bool类型，和之前不同的原因是我们要创建的不含重复值的二叉搜索树，所以要判断是否插入成功。当然不一定非要设置成这样，如果你不想得到这样的反馈，也可以设置为void类型，根据不同的需求做出不同的选择即可。

2.要先判断此时的树是否是空树，也就是判断根节点是否为空，如果为空就要先创建一个结点作为根结点，如果不是再执行下面的操作。

3.2二叉搜索树的查找

查找的逻辑就更为简单，直接把插入中间那一段拿下来即可。这里就不需要parent了，直接通过cur来找，判断是否存在即可，存在就返回true，不存在就返回false。

3.3二叉搜索树的删除

二叉搜索树的删除就是其中最难的地方了，大家设想一下，我能直接删除其中的某个结点吗？

显然是不能的，如果是叶子结点还好，如果是中间的结点呢？直接删的话它的左右子树怎么办呢？

所以在删除这里要分情况讨论：
首先查找元素是否在二叉搜索树中，如果不存在，则返回false。
如果查找元素存在则分以下四种情况分别处理:(假设要删除的结点为N)
1.要删除结点N左右孩子均为空
2.要删除的结点N左孩子位空，右孩子结点不为空
3.要删除的结点N右孩子位空，左孩子结点不为空
要删除的结点N左右孩子结点均不为空

对应以上四种情况的解决方案:
1.把N结点的父亲对应孩子指针指向空，直接删除N结点
2.把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点
3.把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点
4.无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点 R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点。

这里大家一定要自己画一下图来检验一下上述的解决方案，就像没有左子树，可能没有右子树也可能有；没有右子树，可能有左子树也可能没有，所以才会有这种解决方案，能完美解决这种问题。

依旧以这个图为例。1，4，7，14满足第一种情况，删起来也最为简单。

10符合第二种情况，14满足第三种情况。

3，6，8都满足第四种情况。

其实我们仔细思考一下，无非就两种情况，左右子树不全和左右子树完整，而根据这种思路我们来完成删除的代码实现：

虽然想到了上面的情况，但是实际在删除操作中还有许多要注意的地方：
1.前面的部分和之前差不多，这里我就不过多赘述

2.左子树为空：首先要判断是否删除的是根结点，比如：

这里拿这张图举个例子，就是根结点没有左子树，大家理解意思即可。

为什么要判断是否是根结点呢？

才开始删除根结点时它左子树和右子树都有的情况下不走这一步，但是如果我们一直删，直到把根结点的左子树给删完了，那么此时再删就要走这里了，所以才要判断，下面右子树是一样的道理。

此时根结点的左子树为空，这种情况下删除起来较为简单，直接更新cur的位置，使其指向它的右子树，再把根结点delete掉即可。

反之如果要删除的不是根结点，那么就要判断此时cur所在的结点是在parent的左边还是右边。

判断完成后如果是右边，那么就让parent的right指向cur的right；如果是左边，那么就让parent的left指向cur的right。

然后在delete掉cur所在节点即可。

3.右子树为空：首先要判断是否删除的是根结点，比如：

此时根结点的左子树为空，直接更新cur的位置，使其指向它的左子树，再把根结点delete掉即可。

反之如果要删除的不是根结点，那么就要判断此时cur所在的结点是在parent的左边还是右边。

判断完成后如果是右边，那么就让parent的right指向cur的left；如果是左边，那么就让parent的left指向cur的left。

然后在delete掉cur所在节点即可。

4.左右子树都有：

此事的解决方法就和上面两种不一样了，在这里我采用的是找右子树的最小结点来和对应结点进行交换，当然也可以找左子树的最大结点来交换，都可以。

我们之前的思路是找到相应结点，让其和右子树的最小结点进行交换在删除。

但是这其中还有一些问题，就比如：上面那颗二叉搜索树，我要删除8这个根结点，那么找右子树的最小结点就是10，就不会进入到while循环里面，那么我们如果不加以判断的话，直接删除，那么后面的结点就会和树断开联系，造成内存泄露。

所以基于上面这种情况，我们才要再定义一个pminright，来判断是否右子树第一个结点就是最小结点。如果不是，就说明进入while循环找到相应结点，交换后让pminright的left指向minright的right，最后delete掉minright节点即可；如果是，那么就直接让pminright的right指向minright的right，就是直接跳过minright指向它的右子树，再delete掉minright结点即可。

3.4而产生搜索树的析构函数

在二叉树的章节我们讲过，二叉树的销毁要用后续递归来实现，也就是先销毁左右子树，在销毁根结点。

但是呢析构函数不能直接进行递归调用，参数就不合适，所以我们要在创建一个函数Destory来实现析构的功能。

Destory函数的实现比较简单，首先判断此时结点是否为空，为空的情况下，直接返回即可；非空就利用递归先销毁左右子树，在销毁根结点即可。

3.5二叉搜索树的拷贝构造函数

拷贝构造函数和上面的析构函数一样，都需要在创建一个函数来完成相关功能。

而拷贝构造实现起来也比较简单，我们要利用的是中序递归，先构建根结点，在构建左右子树，最后返回copy，也就完成了拷贝构造功能。

但是此时代码写到这就会出问题，会报错：说你创建的对象没有默认的构造函数，其实也就是我们自己写了拷贝构造函数，而我们之前讲过，自己写构造函数后，编译器就不会自动生成默认的构造函数，所以此时我们就要自己写默认构造函数：

我们直接这样既可，因为我们已经给_root了缺省值，它会自动走初始化列表的，所以写成这样即可。

当然还有另外一种写法：

我们让构造函数=default关键字，这里的意思就是当前类中没有默认构造函数，我让其强制生成一个默认构造函数，也是一种解决办法。

3.6=符号重载

这种简单的方法我们之前就讲过，直接交换两者的根结点即可，这里要注意的是要是传值传参，不能是引用，因为我们不能改变=号右边的对象，传值传参就不会影响实参。

3.7二叉搜索树的中序遍历

中序遍历在二叉树章节就已经讲过，这里就不过多赘述，而我们可以利用中序遍历来检测数据是否插入成功：

这里通过中序遍历可以看到我们的数据都插入成功，并且也满足没有重复值的条件。

4.二叉搜索树的key和key/value使用场景

4.1key搜索场景

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断 key在不在。kely的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。
场景1:小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。
场景2:检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。

key搜索场景就是我们上面对二叉搜索树的实现。

4.2key/value搜索场景

每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。
场景1:简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输入英文，则同时查找到了英文对应的中文。
场景2:商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间-入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
场景3:统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，(单词，1)，单词存在，则++单词对应的次数。

key/value只需要对上面我们实现的代码中的一部分进行修改即可：

其实也就是把要创建结点的地方再多传入一个value即可。

这里我展示一下场景一：

使用起来就如上述所示，找到相应的key，我们就可以展示出对相应的value。

以上就是二叉搜索树的内容。

相关文章：