c++二叉搜索树

⼆叉搜索树的概念

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

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

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

• 它的左右子树也分别为⼆叉搜索树

• 二叉搜索树中可以支持插入相等的值,也可以不支持插入相等的值,具体看使用场景定义

⼆叉搜索树的性能分析

最优情况下,⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树),其高度为:O(log2 N)

最差情况下,二叉搜索树退化为单支树(或者类似单支),其⾼度为:O(N/2)

所以综合而言⼆叉搜索树增删查改时间复杂度为:O(N) 那么这样的效率显然是无法满足我们需求的,平衡⼆叉搜索树AVL树和红黑树,才能适用于我们在内存中存储和搜索数据。

另外需要说明的是,⼆分查找也可以实现O(logN) 级别的查找效率,但是⼆分查找有两大缺陷:

1. 需要存储在支持下标随机访问的结构中,并且有序。

2. 插⼊和删除数据效率很低,因为存储在下标随机访问的结构中,插⼊和删除数据⼀般需要挪动数 据。

这里也就体现出了平衡⼆叉搜索树的价值。 

⼆叉搜索树模拟实现

结点

template<class K>
struct treenode
{
	K _key;
	treenode<K>* _left;
	treenode<K>* _right;

	treenode(const K& x)
		:_key(x)
		, _left(nullptr)
		,_right(nullptr)

	{}
};

这里我们使用模板来创建树结点,模板可以匹配任意类型的数值。 

插入

插入的具体过程如下:

1. 树为空,则直接新增结点,赋值给root指针

2. 树不空,按⼆叉搜索树性质,插⼊值⽐当前结点大往右走,插⼊值比当前结点小往左走,找到空位置,插入新结点。

3. 如果支持插入相等的值,插入值跟当前结点相等的值可以往右走,也可以往左走,找到空位置,插入新结点。(要注意的是要保持逻辑⼀致性,插⼊相等的值不要⼀会往右走,⼀会往左走)

bool Insert(const T& key)
{
	if (root == nullptr)
	{
		root = new Node(key);
		return true;
	}
	
	Node* parent = nullptr;
	Node* child = root;
	while (child)
	{
		if (key > root->_key)
		{
			parent = child;
			child = child->_right;
		}
		else if (key < root->_key)
		{
			parent = child;
			child = child->_left;
		}
		else
		{
			return false;
		}
	}
    child = new Node(key);
	if (key > parent->_key)
	{
		parent->_right = child;
	}
	else
	{
		parent->_left = child;
	}

	return true;
}

 这里的插入同样使用模板来处理,这里我们创建一个parent来存储循环中遍历结点的父母,child用来寻找树中空位置,之后在循环中不断遍历,查找空结点,一旦child为空,退出循环,利用parent的key来判断key的值是要存储在左边还是右边

查找

1. 从根开始比较,查找x,x比根的值大则往右边走查找,x比根值小则往左边走查找。

2. 最多查找高度次,走到到空,还没找到,这个值不存在。

3. 如果不支持插⼊相等的值,找到x即可返回

4. 如果支持插⼊相等的值,意味着有多个x存在,⼀般要求查找中序的第⼀个x。

Node* find(const T& x)
{
	Node* cur = root;
	while(cur)
	{
		if (x > cur->_key)
		{
			cur = cur->_right;
		}
		else if (x < cur->_key)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}

这里通过if语句来判断是否查找到相等的值,最后一个else对应的就是找到相等的值,如果找不到的话就在最后返回空。

删除

⾸先查找元素是否在⼆叉搜索树中,如果不存在,则返回false。

如果查找元素存在则分以下四种情况分别处理:(假设要删除的结点为N)

1. 要删除结点N左右孩子均为空

2. 要删除的结点N左孩子位空,右孩子结点不为空

3. 要删除的结点N右孩子位空,左孩子结点不为空

4. 要删除的结点N左右孩子结点均不为空

对应以上四种情况的解决方案:

1. 把N结点的父亲对应孩子指针指向空,直接删除N结点(情况1可以当成2或者3处理,效果是⼀样 的)

2. 把N结点的父亲对应孩子指针指向N的右孩子,直接删除N结点

3. 把N结点的父亲对应孩子指针指向N的左孩子,直接删除N结点

4. 无法直接删除N结点,因为N的两个孩子无处安放,只能用替换法删除。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N,因为这两个结点中任意⼀个,放到N的位置,都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换,转⽽变成删除R结点,R结点符合情况2或情况3,可以直接删除。

bool Erase(const T& key)
{
	Node* parent = nullptr;
	Node* child = root;
	while (child)
	{
		if (key > child->_key)
		{
			parent = child;
			child = child->_right;
		}
		else if (key < child->_key)
		{
			parent = child;
			child = child->_left;
		}
		else//找到cur的位置了
		{
			//左为空
			if (child->_left == nullptr)
			{
				if (child == root)//树中只有一个结点的情况
				{
					root = child->_right;
				}
				else
				{
					if (child->_key > parent->_key)
					{
						parent->_right = child->_right;
					}
					else
					{
						parent->_left = child->_right;
					}
				}
				delete child;
			}
			else if (child->_right == nullptr)//右为空
			{
				if (child == root)
				{
					root = child->_left;
				}
				else
				{
					if (child->_key > parent->_key)
					{
						parent->_right = child->_left;
					}
					else
					{
						parent->_left = child->_left;
					}
					delete child;
				}
			}
			else
			{
				Node* rplace = child;
				Node* rchild = child->_right;

				while (rchild->_left)
				{
					rplace = rchild;
					rchild = rchild->_left;
				}

				child->_key = rchild->_key;

				if (rplace->_left == rchild)
				{
					rplace->_left = rchild->_right;
				}
				else
				{
					rplace->_right = rchild->_right;
				}
				
				delete rchild;
				return true;
			}
		}
	}
	return false;
}

删除通过while循环来寻找需要删除的位置,删除的情况大体分为3种,左为空,右为空,左右不为空,因为左右孩子均为空的情况也可以通过作为空和右为空的情况去处理。

左为空和右为空的处理方法相似,都分为两种情况:树中只有一个结点和多个结点。

一个结点:将删除结点的左孩子或右孩子传给根结点。

多个结点:判断删除结点是父亲结点的左孩子还是右孩子,随后将删除结点的左孩子或右孩子传给父亲结点

左右不为空结点较难处理,首先要查找右树的最左结点,这里的replace和rchild用来循环查找右数最左结点,但是这里的rplace不能置空

像这里如果rplace置空的情况,10结点又不存在左结点,意味着不会通过循环,replace依旧是空,此时if语句中就会出现问题,rplace 在之后的语句中会处于空的状态。

如果没有进入循环的情况下,我们并不能无脑的进行判断rchild一定是rplace的左孩子,在删除8结点的时候,10结点并不是8结点的左孩子,所以我们要在之后进行判断,判断rchild到底是左孩子还是右孩子

⼆叉搜索树key和key/value使用场景

key搜索场景:

只有key作为关键码,结构中只需要存储key即可,关键码即为需要搜索到的值,搜索场景只需要判断key在不在。key的搜索场景实现的⼆叉树搜索树支持增删查,但是不支持修改,修改key破坏搜索树结构了。

场景1:小区无人值守车库,小区车库买了车位的业主车才能进小区,那么物业会把买了车位的业主的车牌号录入后台系统,车辆进入时扫描车牌在不在系统中,在则抬杆,不在则提示非本小区车辆,无法进入。

场景2:检查⼀篇英文文章单词拼写是否正确,将词库中所有单词放⼊⼆叉搜索树,读取文章中的单词,查找是否在⼆叉搜索树中,不在则波浪线标红提示。

key/value搜索场景:

每⼀个关键码key,都有与之对应的值value,value可以任意类型对象。树的结构中(结点)除了需要存 储key还要存储对应的value,增/删/查还是以key为关键字⾛⼆叉搜索树的规则进行比较,可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树支持修改,但是不支持修改key,修改key破坏搜索树结构了,可以修改value。

场景1:简单中英互译字典,树的结构中(结点)存储key(英⽂)和vlaue(中⽂),搜索时输⼊英文,则同时查找到了英文对应的中文。

场景2:商场无人值守⻋库,入口进场时扫描车牌,记录车牌和⼊场时间,出口离场时,扫描车牌,查找入场时间,用当前时间-入场时间计算出停车时长,计算出停车费用,缴费后抬杆,车辆离场。

场景3:统计⼀篇文章中单词出现的次数,读取⼀个单词,查找单词是否存在,不存在这个说明第⼀次 出现,(单词,1),单词存在,则++单词对应的次数。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Contact Form 7最新5.9.8版错误修复方案

最近有多位用户反应Contact Form 7最新5.9.8版的管理页面有错误如下图所示 具体错误文件的路径为wp-content\plugins\contact-form-7\admin\includes\welcome-panel.php on line 153 找到welcome-panel.php这个文件编辑它&#xff0c;将如下图选中的部分删除 删除以后&#xf…

洛谷P5740——结构体运用

简单的结构体&#xff0c;但是要注意这个排序还有求和重复 时的特判 AC代码附在后面 #include<bits/stdc.h> using namespace std; struct Node{string name;int a,b,c,sum;//语文&#xff0c;数学&#xff0c;英语 }node[1000]; bool cmp(Node a,Node b){return a.sum…

软件测试之测试用例

1. 测试用例的基本要素 测试用例&#xff08;Test Case&#xff09;是为了实施测试而向被测试的系统提供的一组集合&#xff0c;这组集合包含&#xff1a;测试环 境、操作步骤、测试数据、预期结果等要素。 好的测试用例是一个不熟悉业务的人也能依据用例来很快的进行测试 评价…

Fyne ( go跨平台GUI )中文文档- 架构 (八)完结

本文档注意参考官网(developer.fyne.io/) 编写, 只保留基本用法 go代码展示为Go 1.16 及更高版本, ide为goland2021.2 这是一个系列文章&#xff1a; Fyne ( go跨平台GUI )中文文档-入门(一)-CSDN博客 Fyne ( go跨平台GUI )中文文档-Fyne总览(二)-CSDN博客 Fyne ( go跨平台GUI…

恶意Bot流量识别分析实践

1、摘要 随着互联网的发展&#xff0c;自动化工具和脚本&#xff08;Bots&#xff09;的使用越来越普遍。虽然一些善意 Bots 对于网站的正常运行和数据采集至关重要&#xff0c;但恶意 Bots 可能会对网站带来负面影响&#xff0c;如爬取敏感信息、恶意注册、刷流量等。因此&am…

某建筑市场爬虫数据采集逆向分析

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 目标网站 aHR0cHM6Ly9qenNjLm1vaHVyZC5nb3YuY24vZGF0YS9jb21wYW55P2NvbXBsZXhuYW1lPSVFNiVCMCVCNA 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面…

十八,Spring Boot 整合 MyBatis-Plus 的详细配置

十八&#xff0c;Spring Boot 整合 MyBatis-Plus 的详细配置 文章目录 十八&#xff0c;Spring Boot 整合 MyBatis-Plus 的详细配置1. MyBatis-Plus 的基本介绍2. Spring Boot 整合 MyBatis Plus 的详细配置3. Spring Boot 整合 MyBatis plus 注意事项和细节4. MyBatisx 插件的…

空栈压数 - 华为OD统一考试(E卷)

2024华为OD机试&#xff08;E卷D卷C卷&#xff09;最新题库【超值优惠】Java/Python/C合集 题目描述 向一个空栈压入正整数&#xff0c;每当压入一个整数时&#xff0c;执行以下规则&#xff08;设&#xff1a;栈顶至栈底整数依次编号为 $n_1, n_2, \dots, n_x $&#xff0c;其…

SPI驱动学习六(SPI_Master驱动程序)

目录 前言一、SPI_Master驱动程序框架1. SPI传输概述1.1 数据组织方式1.2 SPI控制器数据结构 2. SPI传输函数的两种方法2.1 老方法2.2 新方法 二、如何编写SPI_Master驱动程序1. 编写设备树2. 编写驱动程序 三、SPI_Master驱动程序简单示例demo1. 使用老方法编写的SPI Master驱…

NLP 主流应用方向

主流应用 文本分类文本匹配序列标注生成式任务 应用细分 常见落地应用举例&#xff1a; 文本纠错句法分析文本翻译话者分离 本质为文本分类任务数字归一化 实现数字映射&#xff0c;提高内容可读性 如将一九九九转1999

【高分系列卫星简介——高分三号卫星(GF-3)】

高分三号卫星&#xff08;GF-3&#xff09; 高分三号&#xff08;GF-3&#xff09;是我国首颗高分辨率、C频段、多极化合成孔径雷达&#xff08;SAR&#xff09;卫星&#xff0c;由中国空间技术研究院北京空间飞行器总部设计部研制&#xff0c;并于2016年8月10日成功发射。该卫…

flash_attention简要笔记

优化效果 原来&#xff0c;attention部分的计算量和中间激活占用显存的复杂度都是 O ( N 2 ) O(N^2) O(N2) 计算量部分原来QK矩阵乘和attn_scoreV矩阵乘的计算量&#xff0c;复杂度都是 O ( N 2 ) O(N^2) O(N2)&#xff1b;中间激活因为中间有一个attn_score&#xff0c;所以复…

10.解析解方法推导线性回归——不容小觑的线性回归算法

引言 线性回归是许多复杂机器学习模型的基础。作为一种基本的机器学习方法&#xff0c;线性回归提供了清晰的思路和工具&#xff0c;通过理解其推导过程&#xff0c;可以更好地掌握机器学习的基本原理和模型设计。 通过阅读本篇博客&#xff0c;你可以&#xff1a; 1.学会如…

win11永久关闭Windows Defend

# Win11 Microsoft Defender 防病毒 彻底关闭 Win11 Microsoft Defender 防病毒关闭 **WinR****——输入 gpedit.msc &#xff0c;打开本地组策略编辑器——计算机配置——管理模板——Windows组件——Microsoft Defender 防病毒——关闭 Microsoft Defender 防病毒策略——设置…

免费在线压缩pdf 压缩pdf在线免费 推荐简单好用

压缩pdf在线免费&#xff1f;在日常生活和工作学习中&#xff0c;处理PDF文件是常见任务。但有时PDF文件体积较大&#xff0c;给传输、存储和分享带来不便。因此&#xff0c;学习PDF文件压缩技巧十分必要。压缩PDF文件是指通过技术手段减小文件占用的存储空间&#xff0c;同时尽…

kafka 一步步探究消费者组与分区分配策略

本期主要聊聊kafka消费者组与分区 消费者组 & 消费者 每个消费者都需要归属每个消费者组&#xff0c;每个分区只能被消费者组中一个消费者消费 上面这段话还不够直观&#xff0c;我们举个例子来说明。 订单系统 订单消息通过 order_topic 发送,该topic 有 5个分区 结算系…

基于YOLO算法的网球运动实时分析-击球速度测量-击球次数(附源码)

这个项目通过分析视频中的网球运动员来测量他们的速度、击球速度以及击球次数。该项目使用YOLO&#xff08;You Only Look Once&#xff09;算法来检测球员和网球&#xff0c;并利用卷积神经网络&#xff08;CNNs&#xff09;来提取球场的关键点。此实战项目非常适合提升您的机…

基于 Web 的工业设备监测系统:非功能性需求与标准化数据访问机制的架构设计

目录 案例 【说明】 【问题 1】(6 分) 【问题 2】(14 分) 【问题 3】(5 分) 【答案】 【问题 1】解析 【问题 2】解析 【问题 3】解析 相关推荐 案例 阅读以下关于 Web 系统架构设计的叙述&#xff0c;回答问题 1 至问题 3 。 【说明】 某公司拟开发一款基于 Web 的…

【JavaEE】多线程编程引入——认识Thread类

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯&#xff0c;你们的点赞收藏是我前进最大的动力&#xff01;&#xff01;希望本文内容能帮到你&#xff01; 目录 引入&#xff1a; 一&#xff1a;Thread类 1&#xff1a;Thread类可以直接调用 2&#xff1a;run方法 &a…

springboot每次都需要重设密码?明明在springboot的配置中设置了密码

第一步&#xff1a;查看当前的密码是什么&#xff1f; 打开redis-cli.exe&#xff0c;输入config get requirepass&#xff0c;查看当前的密码是什么&#xff1f; 接着&#xff0c;修改redis的配置文件&#xff0c;找到redis的安装目录&#xff0c;找到相关的conf文件&#x…