c++二叉树的进阶--二叉搜索树

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

注意:二叉树的中序遍历是一个有序(升序)序列。 

2. 二叉搜索树的操作 

2.1  二叉搜索树的查找 

假设要查找的数为x 。

1. 从根节点开始比较,x大于根去右树找,小于根去左数找。

2. 最多查找高度次,如果走到空就代表没有找到,返回false。

2.2 二叉搜索树的插入

假设插入的数为x

1. 如果树为空,直接新增节点,将x赋值给root。

2.  如果树不为空,则查找x应该插入的位置,然后插入新节点。

2.3 二叉搜索树的删除 

 要删除某一结点,我们需要考虑该节点是否有孩子,并在其子树中择一节点放入该节点的位置。

因此删除我们不仅要知道该节点,还要知道该节点的孩子,同时还要知道该节点的父亲,才能向该节点插入其孩子。但是,如果我们使用递归,传入该节点的引用,我们就可以直接对该节点进行操作而不需要知道其父节点。

删除分为以下几种情况:设要删除的节点为cur,其父亲为parent <因为树是单向的,要链接节点必须知道上一层的位置>

1. cur没有孩子,那么直接删除即可

2. cur左右子树有一个为空,这时候需要将他不为空的一侧孩子挪到cur处,由于我们并不知道cur在parent的哪一侧,因此需要判断cur在parent的哪一侧,然后进行删除与覆盖。

3. cur左右子树都不为空,这时候我们会选择将左树的最右节点or右树的最左节点替换到cur处,以右树的最左节点为例,此时只需要考虑替换后的cur是否有右树< 注意,这里右树的最左节点有可能是cur的右孩子,如果该节点有右树,将其右孩子给他即可>。回到第二步。

3.二叉搜索树的实现

3.1 Find

Node* Find(const K& key)//查找结点,返回其位置
{
	Node* cur = _root;
	while (cur)
	{
		if (key > cur->_key)
		{
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}

3.2 Insert 

bool Insert(const K& key, const V& value)//插入
{
	if (_root == nullptr)//如果空树,直接构建根节点
	{
		_root = new Node(key, value);
		return true;
	}
	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
		{
			return false;
		}
	}
	cur = new Node(key, value);
	if (key < parent->_key)//确定要插入节点在父亲的左还是右
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	return true;
}

3.3 Erase 

bool Erase(const K& key)//删除
{
	Node* cur = _root, * 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)//cur只有一个节点或没有节点
			{
				if (cur == _root)//cur可能在根节点处
				{
					_root = cur->_right;
				}
				if (cur == parent->_right)
				{
					parent->_right = cur->_right;
				}
				else if (cur == parent->_left)
				{
					parent->_left = cur->_right;
				}
				delete cur;
				return true;
			}
			else if (cur->_right == nullptr)//cur只有一个节点或没有节点
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				if (cur == parent->_right)
				{
					parent->_right = cur->_left;
				}
				else if (cur == parent->_left)
				{
					parent->_left = cur->_left;
				}
				delete cur;
				return true;
			}
			else//cur有两个节点,需要替换法,找右树的最左节点
			{
				Node* rightminParent = cur;
				Node* rightmin = cur->_right;
				while (rightmin->_left)
				{
					rightminParent = rightmin;
					rightmin = rightmin->_left;
				}
				
				cur->_key = rightmin->_key;
				cur->_value = rightmin->_value;
				if (rightminParent->_right = rightmin)//右树如果没有左树,那么最左节点就是cur->right
					rightminParent->_right = rightmin->_right;
				else
					rightminParent->_left = rightmin->_right;
				delete rightmin;
				return true;
			}
		}
	}
		return false;
}

3.4 Inorder 

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " : " << root->_value << endl;
		_InOrder(root->_right);
	}

3.5 测试代码 

	void TestBSTree()
	{
		BSTree<string, string> dict;
		dict.Insert("insert", "插入");
		dict.Insert("erase", "删除");
		dict.Insert("left", "左边");
		dict.Insert("string", "字符串");

		dict.InOrder();
		string str = "insert";
		dict.Erase(str);
		dict.InOrder();
		string str1 = "insert";
		BSTreeNode<string,string>* ret = dict.Find(str1);
		if (ret == nullptr)
		{
			cout << str1<<"没有找到!" << endl;
		}
		else
			cout << str1 << " : " << ret->_value << endl;
		cout << endl;

		string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
		// 统计水果出现的次
		BSTree<string, int> countTree;
		for (auto str : strs)
		{
			auto ret = countTree.Find(str);
			if (ret == NULL)
			{
				countTree.Insert(str, 1);
			}
			else
			{
				ret->_value++;
			}
		}
		countTree.InOrder();
	}

3.5 运行结果

当然,这些接口都可以用递归实现,不过只有Erase有用递归实现的价值,在Erase中传入节点的别名,可以避免记录节点的父亲。 

4. 二叉搜索树的应用

1. K模型:K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。
比如:给一个单词word,判断该单词是否拼写正确,具体方式如下:
以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。
2. KV模型:每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。该种方
式在现实生活中非常常见:
比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英
文单词与其对应的中文<word, chinese>就构成一种键值对;
再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出
现次数就是<word, count>就构成一种键值对。我们上面模拟实现的二叉搜索树就是KV模型。

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

从上面的实现中我们可以看出,无论是删除还是插入,我们都需要先进行查找,因此查找在一定程度上就表明了二叉搜索树的性能。

那么二叉搜索树的性能怎么样呢?

对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。

对于上面的二叉搜索树,其查找效率是截然不同的。

因此我们可以得出结论:

最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为:logN* N
最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为:N^2

 

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

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

相关文章

R-Tree与其他空间索引结构的对比

文章目录 R-Tree vs Quadtree/OctreeR-Tree vs kd-TreeR-Tree vs BSP TreeR-Tree vs Hilbert R-Tree总结Python: 使用rtree库实现R-TreeJavaScript: 使用rbush库实现kd-Tree R-Tree是一种广泛使用的空间索引结构&#xff0c;尤其适用于处理多维空间数据。然而&#xff0c;还有其…

电脑上怎么调照片尺寸?怎么压缩图片为144×144

在一些社交媒体平台通常要求用户上传头像&#xff0c;并对其进行裁剪和调整大小&#xff0c;144x144像素是常见的头像尺寸之一&#xff0c;适合在社交媒体上展示个人头像或者小图标&#xff0c;为了可以保证图片的画质&#xff0c;我们尽量会选择专业的图片处理工具来完成操作。…

OpenAI推出强化企业级安全与成本管理新功能

欢迎大家在 GitHub 上 Star 我们&#xff1a; 分布式全链路因果学习系统 OpenASCE: https://github.com/Open-All-Scale-Causal-Engine/OpenASCE 大模型驱动的知识图谱 OpenSPG: https://github.com/OpenSPG/openspg 大规模图学习系统 OpenAGL: https://github.com/TuGraph-…

探索在Apache SeaTunnel上使用Hudi连接器,高效管理大数据的技术

Apache Hudi是一个数据湖处理框架&#xff0c;通过提供简单的方式来进行数据的插入、更新和删除操作&#xff0c;Hudi能够帮助数据工程师和科学家更高效地处理大数据&#xff0c;并支持实时查询。 支持的处理引擎 Spark Flink SeaTunnel Zeta 主要特性 批处理 流处理 精确一次性…

Linux——(grep指令及zip/tar压缩指令)

1.grep指令 语法&#xff1a; grep【选项】查找字符串 文件 功能&#xff1a; 在文件中搜索字符串&#xff0c;将找到的行打印出来 常用选项&#xff1a; -i &#xff1a;忽略大小写&#xff0c;所以大小写视为相同 -n &#xff1a; 顺便输出行号 -v &#xff1a;反向选择&…

DDD领域驱动设计总结和C#代码示例

DDD&#xff08;领域驱动设计&#xff09;是一种软件设计方法&#xff0c;它强调以业务领域为核心来驱动软件的设计和开发。 DDD 的设计初衷是为了解决复杂业务领域的设计和开发问题&#xff0c;它提供了一套丰富的概念和模式&#xff0c;帮助开发者更好地理解和建模业务领域&…

【管理咨询宝藏88】556页!公司经营分析内部培训

本报告首发于公号“管理咨询宝藏”&#xff0c;如需阅读完整版报告内容&#xff0c;请查阅公号“管理咨询宝藏”。 【管理咨询宝藏88】556页&#xff01;公司经营分析内部培训 【格式】PDF版本 【关键词】经营分析、内部培训、多业务分析 【核心观点】 - 非常全面和详细的公…

Composer初次接触

php一直都是简单处理一下单片机的后台服务&#xff0c;没什么深入研究 今天安装一个 php composer.phar require qiniu/php-sdkComposer完全不懂&#xff0c;照着一试&#xff0c;就报错了 - topthink/think-installer v1.0.12 requires composer-plugin-api ^1.0 -> found…

Python爬虫入门指南--爬虫技术的由来、发展与未来--实战课程大赠送

爬虫&#xff0c;也称为网络爬虫或网络蜘蛛&#xff0c;是一种自动化程序&#xff0c;专门用于遍历互联网并收集数据。这种技术的起源、发展和未来都与互联网紧密相连&#xff0c;并在信息检索、数据挖掘等多个领域发挥着不可或缺的作用。 "免费IP池大放送&#xff01;助…

【汇编语言】流程转移和子程序

【汇编语言】流程转移和子程序 文章目录 【汇编语言】流程转移和子程序前言一、“转移”综述二、操作符offset三、jmp指令jmp指令——无条件转移jmp指令&#xff1a;依据位移进行转移两种段内转移远转移&#xff1a;jmp far ptr 标号转移地址在寄存器中的jmp指令转移地址在内存…

Linux信号(处理)

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 前言&#xff1a; Linux信号(产生)-CSDN博客 Linux信号(保存)-CSDN博客 前面我们解释了信号的产生和保存&#xff0c;接下来我们就要解释信号的处理&#xff0c;关于操作系统在合适的时候对信号进行处理&#xff0c;合适…

C++奇迹之旅:从0开始实现日期时间计算器

文章目录 &#x1f4dd;前言&#x1f320; 头文件Date.h&#x1f309;日期计算函数&#x1f320;前后置&#x1f309;前后置-- &#x1f320;两对象日期相减&#x1f309;自定义流输入和输出 &#x1f309; 代码&#x1f309; 头文件Date.h&#x1f320;Date.cpp&#x1f309; …

(windows ssh) windows开启ssh服务,并通过ssh登录该win主机

☆ 问题描述 想要通过ssh访问win主句 ★ 解决方案 安装ssh服务 打开服务 如果这里开不来就“打开服务”&#xff0c;找到下面两个开启服务 然后可以尝试ssh链接&#xff0c;注意&#xff0c;账号密码&#xff0c;账号是这个&#xff1a; 密码是这个 同理&#xff0c;如果…

matlab新手快速上手5(蚁群算法)

本文根据一个较为简单的蚁群算法框架详细分析蚁群算法的实现过程&#xff0c;对matlab新手友好&#xff0c;源码在文末给出。 蚁群算法简介&#xff1a; 蚁群算法是一种启发式优化算法&#xff0c;灵感来源于观察蚂蚁寻找食物的行为。在这个算法中&#xff0c;解决方案被看作是…

vue3中的ref、isRef、shallowRef、triggerRef和customRef

1.ref 接受一个参数值并返回一个响应式且可改变的 ref 对象。 ref 对象拥有一个指向内部值的单一属性 .value property &#xff0c;指向内部值。 例&#xff1a;此时&#xff0c;页面上的 str1 也跟着变化 <template><div><button click"handleClick&quo…

BUUCTF-MISC-10.LSB1

10.LSB1 题目&#xff1a;lsb隐写&#xff0c;stegsolve可以看到包含了一个PNG图片 使用stegsolve打开这个图片 由PNG文件头可以看出隐写内容为PNG文件&#xff0c;按save Bin键保存为PNG文件。 得到一张二维码图片&#xff0c;使用CQR扫一下

盲返模式:电商领域的新玩法与商业创新

大家好&#xff0c;我是微三云周丽&#xff0c;今天给大家分析当下市场比较火爆的商业模式&#xff01; 小编今天跟大伙们分享什么是什么是盲返模式&#xff1f; 随着互联网的深入发展&#xff0c;电商行业正面临着前所未有的机遇与挑战。在这个竞争激烈的市场环境中&#xff…

GAN 生成对抗神经网络

GAN 文章目录 GANGAN的结构GAN的目标函数GAN的训练GAN的优势和不足优势不足 GAN的结构 GAN的设计灵感来源于博弈论中的零和博弈&#xff08;Zero-sum Game&#xff09;&#xff0c;在零和博弈中&#xff0c;参与双方的收益是完全相反的&#xff0c;一方的收益必然导致另一 方的…

Python400集 视频教程,手把手带你零基础手写神经网络!!

嗨喽&#xff0c;大家好&#xff0c;今天又要给大家整一波福利了&#xff01; 学习编程&#xff0c;最忌讳就是今天一个教程&#xff0c;明天一个教程&#xff0c;频繁更换教程&#xff0c;增加自己的学习成本&#xff0c;对于新手小白会是一件严重打击自信心的事情。所以今天…

jetson开发板+外接散热风扇

本文参考链接 https://news.mydrivers.com/1/580/580811.htm?refhttps%3A//www.baidu.com/link%3Furl%3DM_D45a-od3NK-ER_Flgqqw4LjHLinB1xrmYNj7VVqHlM2zVXwR9Z7FGilCYDRRJYNpIsdejeAfpVtmVTowuFfK%26wd%3D%26eqid%3D81e7865e000256a5000000046628ff4a 一、三种风扇的种类 二…