【数据结构】——二叉搜索树
前言
在c++中的容器里map和set的学习需要二叉搜索树的铺垫，也为后边的的红黑树和AVL树做铺垫，也就是说，今天主要讲搜索树的基本结构和应用。
二叉搜索树的概念
所有的根节点大于左子树的节点，小于右子树的节点的二叉树就叫做二叉搜索树。
二叉搜索的性质：
如果左子树不为空，则左子树上的所有节点都小于根节点。如果右子树不为空，则右子树上的所有节点都大于根节点。左右子树也为搜索二叉树。
假设我们要查找8，我们从根节点开始查找，这该怎样查找呢？
首先我们先与根节点5对比，发现比根节点5大，所以我们就到它的右子树查找，根节点就变为7，然后我们再与根节点7对比，发现比根节点大，再到根节点7的右子树查找，根节点就变为8，找到该节点之后我们在返回。
二叉搜索树的搜索的时间复杂度：
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对于同一个元素的集合，如果元素的插入顺序不同的，则会出现不同结构的二叉搜索树，也就是说树的结构与元素插入的顺序有关。
搜索效率最优的情况下:完全二叉树，其平均比较的次数是O (logN)。搜索效率最坏的情况:单支二叉树，其平均的比较次数是O（N)
所以搜索二叉树的搜索的时间复杂度是O(N),时间复杂度看的是最坏的情况。树的搜索次数与树的层次有关.
二叉搜索树的操作
树的节点实现
搜索树的基本结构
插入数据
a.树为空，则直接插入
b.树不为空，按二叉树搜索的性质插入的位置，插入的位置都会是叶子节点。 
c.如果插入的数据在树中已存在，则不将数据插入到树中，并返回false。搜索树的数据都是独一无二的。
代码实现：
非递归版本
递归的版本：
查找
找到了就返回该节点的地址，找不到就返回空。
删除
当我们要删除搜索树中某个节点的时候，删除后的树的结构也需要保持着搜索的性质，所以删除有有以下4种情况、要删除的节点无孩子节点。例如 0 4 6 9
只要我们找到该值，直接删除掉就行。
要删除的节点有左孩子的节点。例如 1
找到该值，先让该值的父亲节点区连接它的左孩子节点，然后再删除掉。父亲节点要连接该值的左孩子节点时，需要判断孩子节点是连接在父亲的左边还是右边
要删除的节点有右孩子的节点。例如 8
找到该值，先让该值的父亲节点区连接它的右孩子节点，然后再删除掉。父亲节点要连接该值的右孩子节点时，需要判断孩子节点是连接在父亲的左边还是右边
要删除的节点有左右孩子的节点。例如 3 5 7
如果我们直接删除这样的节点时，就会让使它的左右子树没有根节点，所以我们怎样删除这样的节点，并保持搜索二叉树的特性？
我们可以找出该值左子树最大的节点或者右子树最小的节点，去替换根节点，然后将替换的节点给删除掉。（左子树最大的节点或者右子树最小的节点去替换的根节点依旧可以保持着搜索二叉树的性质）。删除5这个数据的过程;，找出左子树最大的值，也就是左子树最右的值，替换到根节点，然后直接将 替换的节点删除即可。
删除3的过程，找出左子树最大的值，也就是左子树最右的值。
【文章福利】：C/C++Linux服务器开发/后台架构师【公开课学习】（C/C++，Linux，golang技术，内核，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg，大厂面试题 等）有需要的可以点击793599096加群领取哦~
代码：
这段代码的含义：
递归版本：
_eraseR是private里面的，eraseR是public里面的。 
eraseR是对_eraseR的封装，方便被调用。
拷贝构造函数
赋值重载函数
析构函数：
2.4 二叉搜索树的应用
1.K模型：K模型只有key作为关键码，也就是定义树的节点只需要存_key一个即可，关键码即为搜索到的值。如上我们写的搜索树就是k模型，因为树的节点就只有一个key可以存储数据。
比如：我们要进学校的图书馆就需要刷我们的学生卡，通过磁感应将门打开。
此时我们就需要先将学生的学号录入到该门的管理系统，然后将数据建立起搜索树，我们的学号在学校是唯一的，当我们刷卡的时候，就会去管理系统快速查找我们的学号，找到了门就开了。
k模型在实际应用中就是就是查找在不在的问题。
2.kv模型:每一个关键码key都有一个对应的value值，也就是说树的节点中有两个值，一个是key，一个是value的值，我们通过key找到对应的节点，然后将相对应的value给映射出来。也就是说，我们增删查改的时候也是按key进行插入或者删除。只是创建节点，增加了一个value值。
场景1：我们去网上买高铁票，每张高铁票的信息都有与一个身份证号绑定在一起的，当我们进高铁站都需要刷身份证在搜索树中查找有没有你的身份证号，找到了，通过身份证号映射你的高铁信息，看看有没有你的班次，门才是否可以被开。在这里_key是身份证，它是独一无二的，_value是高铁信息，通过身份证将它给映射出来。
场景2：
英汉词典就是英文与中文的对应关系，我们只需要查找有没有该英文，找到了，就通过映射关系，将该英文的单词的中文给映射出来。
用kv模型的搜索树写一个简单的词典：
运行结果： 
场景3：
统计水果次数。
如下
输出结果：
其中Inorder是将树中所有的节点都给打印出来，代码如下：
_Inorder是private里面的，而Inorder是public里面的。
原文链接：https://blog.csdn.net/sjp11/article/details/121058735
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/97853.html
