【C++】——二叉搜索树(详解)

一  二叉搜索树概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

✨若它的左子树不为空,则左子树上所有节点的值都小于根节点的值

✨若它的右子树不为空,则右子树上所有节点的值都大于根节点的值

✨它的左右子树也分别为二叉搜索树

二  二叉搜索树的操作 

和其他结构差不多,一般都为增删查改

2.1  二叉搜索树的查找

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

比如我们要查找6,那么就会先跟8比较,然后往左边走,比3大,就往右边走,然后就找到了所对应的值。

2.2  二叉搜索树的插入

插入的具体过程如下:
a. 树为空,则直接新增节点,赋值给root指针
b. 树不空,按二叉搜索树性质查找插入位置,插入新节点

 对于插入来说,也就是比查找多了一个插入的过程

2.3  二叉搜索树的删除

对于删除来说就很有讲究了,因为你要保证它删除完以后还是一个二叉搜索树,不然就扯蛋了

  ✨首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情况:
1. 要删除的结点无孩子结点
2. 要删除的结点只有左孩子结点
3. 要删除的结点只有右孩子结点
4. 要删除的结点有左、右孩子结点


看起来有待删除节点有4中情况,实际情况a可以与情况b或者c合并起来,因此真正的删除过程
如下:
情况2:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
情况3:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
情况4:在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点
中,再来处理该结点的删除问题--替换法删除

2.3 二叉搜索树的应用

K模型:K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到
的值。
比如:给一个单词word,判断该单词是否拼写正确,具体方式如下:
        以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树
        在二叉搜索树中检存在则拼写正确,不存在则拼写错误。

2. KV模型:每一个关键码key,都有与之对应索该单词是否存在,的值Value,即<Key, Value>的键值对。该种方式在现实生活中非常常见:
         比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英
         文单词与其对应的中文<word, chinese>就构成一种键值对;
         再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出
         现次数就是<word, count>就构成一种键值对。

对于容器map和set的底层就是二叉搜索树的优化,所以二叉搜索的应用是非常广泛的。

2.4  二叉搜索树的性能

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。

其实从表面上看二叉搜索树的效率是很高的,但是它也有极端情况

最优情况是第一个,类似完全二叉树,平均比较次数为lon(N),

最坏情况是第二个图,二叉搜索树退化为单支树(或者类似单支)

如果是第二个那么就让搜索二叉树没有了优势,但是后面会有对这个的改良。

三  二叉搜索树的实现

3.1  二叉搜索树结构

首先我们肯定得有一个结点用来存储内部结构

template<class T>
class BSTreeNode
{BSTreeNode<T> *left;//左指针BSTreeNode<T> *right;//右指针T val;BSTreeNode(const T&key):val(key),left(nullptr),right(nullptr){}
};

其次我们需要的一颗树,对于二叉搜索树来说,我们主要是删除和插入的操作,其他的其实都大同小于

template <class T>
class BSTree
{typedef BSTreeNode<T> Node;public:bool  insert(const T&key);bool  Find(const T&key);bool  Erase(const T&key);private:Node* root;
};

3.2   插入元素

对于插入元素,我们需要的是先找到那个可以插入的值,如果要插入的值已经存在,那么就插入失败,如果不存在,那么我就必须按照二叉搜索树的规则进行插入

如果不懂,那看看代码就应该会清晰了

bool insert(const T& key){if (root == nullptr)//特判,如果是跟,那么直接插入不需要去找{root = new Node(key);return true;}Node* cur = root;Node* parent = nullptr;//以便我们找到父亲结点while (cur){if (key>cur->val)//如果插入值大于当前值,往右走{parent = cur;cur = cur->right;}else if (key < cur->key)//同理,往左走{parent = cur;cur = cur->left;}else//相等,说明已经存在了,插入失败{return false;}}//这里说明找到位置了进行插入cur = new Node(key);if (parent -> val<key)//插入之前也要判断是插入到左边还是右边{parent->right = cur;}else{parent->left = cur;}return true;}

以上就是插入的代码,总结下来就是,先特判,然后去找位置,找到位置进行插入,插入的时候也要判断是插左边还是右边

3.3  寻找元素

寻找元素就是插入元素的简单版本,思路就是插入元素上面的,下面给出代码

bool Find(const T& key){if (root == nullptr) return false;Node* cur = root;Node* parent = nullptr;while (cur){if (key > cur->val){cur = cur->right;}else if (key < cur->val){cur = cur->left;}else{return true;}}return false;}

3.4  删除元素

对于删除元素,里面的细节就很多了

情况1:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
情况2:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
情况3:在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点
中,再来处理该结点的删除问题--替换法删除

下面我们就根据这些操作一步一步去完成

首先我们肯定是先去寻找要删除的元素在哪里

bool Erase(const T& key){if (root == nullptr) return false;Node* cur = root;Node* parent = nullptr;while (cur){if (key > cur->key){parent = cur;cur = cur->right;}else if (key < cur->key){parent = cur;cur = cur->left;}

后面找到了,就需要我们去删除了,所以这里就需要去判断那三种情况

else{if (cur->left == nullptr){if (cur == root)//特判是不是根节点{root = cur->right;}else{if (parent->left == cur){parent->left = cur->right;}else{parent->right = cur->right;}}delete cur;}

判断是不是左为空,如果是左为空,那么我就需要去把他的右孩子链接起来 

 同时我们还需要去判断他是在父亲的左还是右

 第二种情况就是如果是有为空的情况,和左为空是对称的

                else if (cur->right == nullptr){if (cur == root){root = cur->left;}else{if (parent->left == cur){parent->left = cur->left;}else{parent->right = cur->left;}}delete cur;}

 第三种情况也 是最为复杂的一种就是,左右都不为空

               else//都不为空,替代法{Node* parent = cur;//这里需要把parent置成curNode* subLeft = cur->right;//这里我们去右边找最小的,也就是右边最左值while (subLeft->left){parent = subLeft;subLeft = subLeft->left;}swap(cur->val, subLeft->val);//找到了交换if (parent->left == subLeft)//然后判断是在父亲的左边还是右边{parent->left = subLeft->right;//因为是最左边,所以他只会有右子树}else if (parent->right = subLeft){parent->right = subLeft - right;}delete subLeft;//链接上了,就直接删除}return true;}}return false;}

以上就是二叉搜索树的最关键的操作函数实现,其实不难,注意细节就行了

完整代码

#pragma once
template<class T>
class BSTreeNode
{BSTreeNode<T> *left;BSTreeNode<T>* right;T val;BSTreeNode(const T&key):val(key),left(nullptr),right(nullptr){}
};template <class T>
class BSTree
{typedef BSTreeNode<T> Node;
public:bool insert(const T& key){if (root == nullptr){root = new Node(key);return true;}Node* cur = root;Node* parent = nullptr;while (cur){if (key>cur->val){parent = cur;cur = cur->right;}else if (key < cur->key){parent = cur;cur = cur->left;}else{return false;}}cur = new Node(key);if (parent -> val<key){parent->right = cur;}else{parent->left = cur;}return true;}bool Find(const T& key){if (root == nullptr) return false;Node* cur = root;Node* parent = nullptr;while (cur){if (key > cur->val){cur = cur->right;}else if (key < cur->val){cur = cur->left;}else{return true;}}return false;}bool Erase(const T& key){if (root == nullptr) return false;Node* cur = root;Node* parent = nullptr;while (cur){if (key > cur->key){parent = cur;cur = cur->right;}else if (key < cur->key){parent = cur;cur = cur->left;}else{if (cur->left == nullptr){if (cur == root){root = cur->right;}else{if (parent->left == cur){parent->left = cur->right;}else{parent->right = cur->right;}}delete cur;}else if (cur->right == nullptr){if (cur == root){root = cur->left;}else{if (parent->left == cur){parent->left = cur->left;}else{parent->right = cur->left;}}delete cur;}else//都不为空,替代法{Node* parent = cur;Node* subLeft = cur->right;while (subLeft->left){parent = subLeft;subLeft = subLeft->left;}swap(cur->val, subLeft->val);if (parent->left == subLeft){parent->left = subLeft->right;}else if (parent->right = subLeft){parent->right = subLeft - right;}delete subLeft;}return true;}}return false;}void InOder(){_InOder(root);cout << endl;}private:bool _EraseR(Node*& root, const K& key){if (root == nullptr) return;if (root->val < key){return _EraseR(root->right, key);}else if (root->val > key){return _EraseR(root->left, key);}else{//删除if (root->left == nullptr){Node* del = root;root = root->right;delete del;return true;}else if (root->right == nullptr){Node* del = root;root = root->left;delete del;return true;}else{Node* subLeft = root->right;while (subLeft->left){subLeft = subLeft->left;}swap(subLeft->val, root->val);return _EraseR(root->right, key);}}}void _InOder(Node*root){if (root == nullptr)return;_InOder(root->left);cout << root->val << ' ';_InOder(root->right);}Node* root=nullptr;
};

四  二叉搜索树递归实现

对于二叉搜索树的递归实现,这里着重去解释删除操作的递归

bool _EraseR(Node*& root, const K& key){if (root == nullptr) return;if (root->val < key){return _EraseR(root->right, key);/递归去找删除的数}else if (root->val > key){return _EraseR(root->left, key);}else{//删除if (root->left == nullptr)//这里不需要特判根结点,因为用了引用,不需要父亲结点 //自然也不会出现空的情况{Node* del = root;root = root->right;delete del;return true;}else if (root->right == nullptr){Node* del = root;root = root->left;delete del;return true;}else{Node* subLeft = root->right;while (subLeft->left){subLeft = subLeft->left;}swap(subLeft->val, root->val);return _EraseR(root->right, key);//这里递归去右树删除,这样就省去很多麻烦}}

从上面代码中我们可以看出,其实少了很多的判断,尤其是父亲结点的链接判断,之所以会这样,就是因为我们用了引用这样可以直接改变指针指向的位置,在连接的时候,就直接连接上了,自然就不需要父亲结点。

有了上面删除的递归版本,那么其他的理解起来就很容易了

bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->val < key)return _InsertR(root->right, key);else if (root->val > key)return _InsertR(root->left, key);elsereturn false;}bool _FindR(Node* root, const K& key){if (root == nullptr){return false;}if (root->val < key){return _FindR(root->right, key);}else if (root->val > key){return _FindR(root->left, key);}else{return true;}}

五 总结

以上就是搜索二叉树的大概内容了,希望对你有用

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/361258.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

在数字化转型中,数字孪生技术的作用和价值几何?

引言&#xff1a;随着全球化和市场竞争的加剧&#xff0c;企业需要通过数字化转型来提高生产效率、优化产品质量、降低成本&#xff0c;以增强自身竞争力。企业需要通过数字化转型更好地理解客户需求&#xff0c;提供个性化、定制化的产品和服务&#xff0c;从而满足客户的多样…

Axios-入门

介绍 Axios对原生Ajax进行了封装&#xff0c;简化书写&#xff0c;快速开发 官网&#xff1a;Axios中文文档 | Axios中文网 (axios-http.cn) 入门 1引入Axios的js文件 <script src"js/axios.js"></script> 2使用Axios发送请求&#xff0c;并获取响应…

链式队列算法库构建

学习贺利坚老师课程,构建链式队列算法库 数据结构之自建算法库——链队&#xff08;链式队列&#xff09;_数据结构函数链队列的算法框架有哪些-CSDN博客文章浏览阅读6.2k次&#xff0c;点赞3次&#xff0c;收藏9次。本文针对数据结构基础系列网络课程(3)&#xff1a;栈和队列…

在win7系统电脑安装node16的版本(已成功安装运行)

很多银行的项目行方都要求内网开发&#xff0c;但是我遇到的几个银行基本都是win7系统的电脑&#xff0c;而前端的项目又是需要高版本的node才能跑起来&#xff0c;所有就记录此解决方案文章&#xff01; 这是下载node安装包的地址&#xff1a;Index of /dist/ 在这里先下载自…

树形结构的勾选、取消勾选、删除、清空已选、回显、禁用

树形结构的勾选、取消勾选、删除、清空已选、回显、禁用 基本页面&#xff1a; 分为上传文件和编辑的页面 代码实现要点&#xff1a; 上传文件页面&#xff1a; 点开选择范围弹窗&#xff0c;三个radio单选框都为可选状态&#xff0c;默认显示的是第一个单选框&#xff08;按…

晶方科技:台积电吃饱,封装迎春?

半导体产业链掀起涨价潮&#xff0c;先进封装迎接利好。 这里我们来聊国内先进封装企业——晶方科技。 近期&#xff0c;由于产能供不应求&#xff0c;台积电决定上调先进封装产品价格&#xff0c;还表示订单已经排到2026年。 大哥吃不下了&#xff0c;剩下的订单全都是空间。…

Shell编程规范与变量-01

一、Shell脚本概述 在一些复杂的 Linux 维护工作中&#xff0c;大量重复性的输入和交互操作不仅费时费力&#xff0c;而且容易出错&#xff0c;而编写一个恰到好处的 Shell 脚本程序&#xff0c;可以批量处理、自动化地完成一系列维护任务&#xff0c;大大减轻管理员的负担。 1…

在Ubuntu上安装Python3

安装 python3 pip sudo apt -y install python3 python3-pip升级 pip python3 -m pip install --upgrade pip验证查看版本 python3 --version

web渗透-SSRF漏洞及discuz论坛网站测试

一、简介 ssrf(server-side request forgery:服务器端请求伪造&#xff09;是一种由攻击者构造形成由服务端发起请求的一个安全漏洞。一般情况下&#xff0c;ssrf是要目标网站的内部系统。(因为他是从内部系统访问的&#xff0c;所有可以通过它攻击外网无法访问的内部系统&…

excel字符串列的文本合并

excel表有两列&#xff0c;第一列是“姓名”&#xff0c;第二列是“诊断”&#xff0c;有高血压、糖尿病等。我想出一个统计表&#xff0c;统计“姓名”&#xff0c;把某一个姓名的诊断不重复的用、拼接起来&#xff0c;比如“张三”的诊断为“点高血压”、糖尿病。我们可以用T…

适用于轨道交通专用的板卡式网管型工业以太网交换机

是网管型 CompactPCI板卡式冗余环网交换机。前面板带有6个 10/100/1000Base-T(X)M12接口。后面的CPCI接口有 8个10/100/1000Base-T (X) 以太网接口。 是特别为轨道交通行业EN50155标准要求而设计的坚固型交换机。它同时具有以下特性&#xff1a; ● 支持2线以太网距离扩展端口&…

springcloud第4季 springcloud-alibaba之nacos+openfegin+gateway+sentinel熔断限流【经典案例】

一 说明 1.1 架构说明 本案例实现原理&#xff1a; 采用alibaba的nacos&#xff0c;openfegin&#xff0c;sentinel&#xff0c;gateway等组件实现熔断限流。 主要理解sentinel的ResouceSentinel和fallback的区别联系。 ResourceSentinel 主要是页面配置熔断限流规则&#…

试析C#编程语言的特点及功能

行步骤&#xff0c;而不必创建新方法。其声明方法是在实例化委托基础上&#xff0c;加一对花括号以代表执行范围&#xff0c;再加一个分号终止语句。 2.3.3 工作原理 C#编译器在“匿名”委托时会自动把执行代码转换成惟一命名类里的惟一命名函数。再对存储代码块的委托进行设…

【干货】Vue3 组件通信方式详解

前言 毫无疑问&#xff0c;组件通信是Vue中非常重要的技术之一&#xff0c;它的出现能够使我们非常方便的在不同组件之间进行数据的传递&#xff0c;以达到数据交互的效果。所以&#xff0c;学习组件通信技术是非常有必要的&#xff0c;本文将总结Vue中关于组件通信的八种方式…

【博士每天一篇文献-算法】Fearnet Brain-inspired model for incremental learning

阅读时间&#xff1a;2023-12-16 1 介绍 年份&#xff1a;2017 作者&#xff1a;Ronald Kemker&#xff0c;美国太空部队&#xff1b;Christopher Kanan&#xff0c;罗切斯特大学 期刊&#xff1a; arXiv preprint 引用量&#xff1a;520 Kemker R, Kanan C. Fearnet: Brain-…

宠物领养救助管理系带万字文档java项目基于springboot+vue的宠物管理系统java课程设计java毕业设计

文章目录 宠物领养救助管理系统一、项目演示二、项目介绍三、万字项目文档四、部分功能截图五、部分代码展示六、底部获取项目源码带万字文档&#xff08;9.9&#xffe5;带走&#xff09; 宠物领养救助管理系统 一、项目演示 宠物领养救助系统 二、项目介绍 基于springbootv…

WEB与低代码:B/S架构在开发中的应用与优势

在互联网迅猛发展的今天&#xff0c;WEB应用已经成为人们日常生活和工作中不可或缺的一部分。随着技术的进步和需求的多样化&#xff0c;开发高效、灵活且易于维护的WEB应用变得尤为重要。B/S架构&#xff08;Browser/Server Architecture&#xff09;作为一种常见的WEB应用架构…

Chatopera 云服务实现类海尔服务智能客服的功能点比较 | Chatopera

在上一篇文章中&#xff0c;我分享了《智能客服体验分析&#xff0c;使用小程序海尔服务完成电器报修》。如果使用 Chatopera 云服务实现一个类似的应用&#xff0c;如何做呢&#xff1f;借助 Chatopera 云服务 可以实现一个智能客服&#xff0c;那么和现在的海尔服务小程序会有…

WordPress软件下载主题Inpandora

Inpandora&#xff08;中文名为潘多拉&#xff09;是一款基于软件下载站定制的WordPress主题&#xff0c;帮助站长使用WordPress快速搭建一个专业的WordPress软件博客。Inpandora这款WordPress主题可以说是因软件而生&#xff0c;从UI设计到后台设置功能&#xff0c;都充分体现…

云计算运维工程师的突发状况处理

云计算运维工程师在应对突发的故障和紧急情况时,需要采取一系列迅速而有效的措施来最小化服务中断的时间并恢复系统的稳定性。 以下是一些关键步骤和策略: 快速响应: 立即识别并确认故障的性质和范围。通知团队成员和相关的利益相关者,确保所有人了解当前情况。故障诊断:…