【C++杂货铺】二叉搜索树

目录

🌈前言🌈 

📁 二叉搜索树的概念

📁 二叉搜索树的操作

📂 二叉搜索树的查找

📂 二叉搜索树的插入

📂 二叉搜书树的删除

📁 二叉搜索树的应用

📁 二叉搜索树的实现

📁 二叉搜索树的性能分析

📁 总结

🌈前言🌈 

        欢迎观看本期博文，这期内容讲解二叉搜索树，包括了什么是二叉搜索树，如何实现二叉搜索树，以及二叉搜索树的应用，此外还会分析二叉搜索树的性能。

        在二叉搜索树应用中，会包含K模型，对应的是STL中set容器;KV模型，对应的是STL中的map容器。

📁 二叉搜索树的概念

        二叉搜索树又称为二叉排序树，它或是一颗空树，或者具有以下性质的二叉树：

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。

2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。

3. 它的左右子树也称为二叉搜索树。

📁 二叉搜索树的操作

📂 二叉搜索树的查找

1. 从根开始比较查找，比根大的往右查找，比根小的往左边查找。

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

📂 二叉搜索树的插入

1. 树为空，则直接新增节点，赋值给root指针。

2. 树不为空，按二叉搜索树性质查找插入位置，插入新节点。

📂 二叉搜书树的删除

        首先查找元素是否在二叉搜索树总，如果不存在，则返回，否则要删除的节点可能分为下面四种情况：

1. 要删除的节点无孩子节点

2. 要删除的节点只有左孩子节点

3. 要删除的节点只有右孩子节点

4. 要删除的节点有左右孩子节点。

        开起来有四种情况，实际情况1可以与情况2或者3结合起来，因此真正的删除过程如下：

情况A：删除该节点且使被删除节点的双亲节点指向被删除节点的左孩子节点 --> 直接删除。

情况B：删除该节点且使被删除节点的双亲节点指向被删除节点的右孩子节点--> 直接删除。

情况C：在它的右子树中寻找中序心爱的第一个节点（Key值最小），用它的值填补被删除节点中，再来处理该节点的删除问题 ---> 替换法删除。

📁 二叉搜索树的应用

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

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

📁 二叉搜索树的实现

1. K模型：

	template <class K>
	struct BSTreeNode
	{
		BSTreeNode(K key)
			: _key(key),_left(nullptr), _right(nullptr)
		{}

		K _key;
		BSTreeNode* _left;
		BSTreeNode* _right;
	};

	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K>  Node;

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

		//插入
		bool Insert(K key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}

			Node* cur = _root;
			Node* parent = cur;
			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}

			if (key > parent->_key)
			{
				cur = new Node(key);
				parent->_right = cur;
			}
			else
			{
				cur = new Node(key);
				parent->_left = cur;
			}
			return true;
		}

		//删除
		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
					}

					else if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;
					}

					else
					{
						//左子树最大的 || 右子树最小的
						Node* RightMin = cur->_right;
						Node* RightMinParent = cur;
						while (RightMin->_left)
						{
							RightMinParent = RightMin;
							RightMin = RightMin->_left;
						}
						swap(RightMin->_key, cur->_key);
						if(RightMin == RightMinParent->_left)
							RightMinParent->_left = RightMin->_right;
						else
							RightMinParent->_right = RightMin->_right;
						delete RightMin;
					}
					return true;
				}
			}
			return false;
		}

		//查找
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else
				{
					cout << cur->_key << endl;
					return cur;
				}
			}
			cout << "Not Find" << endl;
			return cur;
		}

		//遍历
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

	protected:
		Node* _root = nullptr;
	};

2. KV模型：

template <class K,class V>
	struct BSTreeNode
	{
		BSTreeNode(K key, V val)
			: _key(key), _value(val), _left(nullptr), _right(nullptr)
		{}

		K _key;
		V _value;
		BSTreeNode* _left;
		BSTreeNode* _right;
	};

	template<class K,class V>
	class BSTree
	{
		typedef BSTreeNode<K,V>  Node;

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

		//插入
		bool Insert(const K& key,const V& val)
		{
			if (_root == nullptr)
			{
				_root = new Node(key,val);
				return true;
			}

			Node* cur = _root;
			Node* parent = cur;
			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}

			if (key > parent->_key)
			{
				cur = new Node(key,val);
				parent->_right = cur;
			}
			else
			{
				cur = new Node(key,val);
				parent->_left = cur;
			}
			return true;
		}

		//删除
		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
					}

					else if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;
					}

					else
					{
						//左子树最大的 || 右子树最小的
						Node* RightMin = cur->_right;
						Node* RightMinParent = cur;
						while (RightMin->_left)
						{
							RightMinParent = RightMin;
							RightMin = RightMin->_left;
						}
						swap(RightMin->_key, cur->_key);
						if (RightMin == RightMinParent->_left)
							RightMinParent->_left = RightMin->_right;
						else
							RightMinParent->_right = RightMin->_right;
						delete RightMin;
					}
					return true;
				}
			}
			return false;
		}

		//查找
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else
				{
					return cur;
				}
			}
			return cur;
		}

		//遍历
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

	protected:
		Node* _root = nullptr;
	};

📁 二叉搜索树的性能分析

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

        对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。
        但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log_2 N 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插 入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上场了。

📁 总结

        以上就是二叉搜索树的所有内容了，讲解了什么是二叉搜索树，二叉搜索树的操作，如何实现二叉搜索树，以及二叉搜索树的应用，K模模型，对应的是STL中的set，KV模型，对应的是map容器。掌握了二叉搜索树，方便日后我们更好的学习ALV树，红黑树。

        如果感觉本期内容对你有帮助，欢迎点赞，关注，收藏Thanks♪(･ω･)ﾉ

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

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

相关文章

vue3 h5模板

vue3 h5模板

vue3的h5模板 基于vue3tsvantrem的h5模板 觉得帮到你了就给个start
阅读更多...
【win10移动热点，提示正在获取ip地址...】

【win10移动热点，提示正在获取ip地址...】

检查 Wired AutoConfig/ WLAN AutoConfig 服务运行 电脑→管理→服务和应用程序→服务&#xff1a;AutoConfig 有线网络无线网卡 1.开启wifi热点&#xff0c;自动生成“本地连接*10”&#xff1b; 2.配置Wired LAN网络共享 仅无线网卡 1. 开启wifi热点&#xff0c;自动生…
阅读更多...
自学Python爬虫js逆向（二）chrome浏览器开发者工具的使用

自学Python爬虫js逆向（二）chrome浏览器开发者工具的使用

js逆向中很多工作需要使用浏览器中的开发者工具&#xff0c;所以这里以chrome为例&#xff0c;先把开发者工具的使用总结一下&#xff0c;后面用到的时候可以回来查询。 Google Chrome浏览器的开发者工具是前端开发者的利器&#xff0c;它不仅提供了丰富的功能用于开发、调试和…
阅读更多...
电动公共交通车充电站设置储能电站方案

电动公共交通车充电站设置储能电站方案

相比于传统燃油公交车&#xff0c;电动公交车以电代油&#xff0c;具有零排放、低噪音、低能耗等优势。随着电池、车载电机等相关技术的不断发展&#xff0c;电动公交车在国内乃至全世界范围内逐步推广应用。动力电池是电动公交车的重要部件之一&#xff0c;其寿命及性能影响着…
阅读更多...
解密推理部署工程师的必备技能，面试题库分析

解密推理部署工程师的必备技能，面试题库分析

推理部署工程师面试题库 1. 描述一下SM的结构&#xff1f; 英伟达 GPU 架构&#xff1a;* 计算核心&#xff1a;INT32、FP32、FP64 CUDA 核心&#xff0c;Tensor 核心&#xff0c;超低延迟负载/存储。* 调度和存储器&#xff1a;Warp 调度器注册文件&#xff0c;共享存储器&am…
阅读更多...
逻辑回归模型与GBDT+LR——特征工程模型化的开端

逻辑回归模型与GBDT+LR——特征工程模型化的开端

随着信息技术和互联网的发展&#xff0c; 我们已经步入了一个信息过载的时代&#xff0c;这个时代&#xff0c;无论是信息消费者还是信息生产者都遇到了很大的挑战&#xff1a; 信息消费者&#xff1a;如何从大量的信息中找到自己感兴趣的信息&#xff1f;信息生产者&#xff…
阅读更多...
主题乐园私域精细化运营

主题乐园私域精细化运营

主题乐园私域精细化运营是指在细分用户群体的基础上&#xff0c;通过个性化、精准的运营方式&#xff0c;为用户提供定制化服务和体验。以下是一些常见的主题乐园私域精细化运营玩法&#xff1a; 会员制度和会员专属服务&#xff1a;建立完善的会员制度&#xff0c;为会员提供专…
阅读更多...
碳实践 | 一文读懂LCA产品生命周期环境影响评价

碳实践 | 一文读懂LCA产品生命周期环境影响评价

一、产品生命周期评价定义 生命周期评价&#xff1a;生命周期评价&#xff08;Life Cycle Assessment&#xff0c;简称LCA&#xff09;是一种量化评价方法。它涵盖了产品的整个生命周期——从自然资源开采到原材料加工、产品制造、分销、使用&#xff0c;直至最终废弃处置或回…
阅读更多...
mongodb使用debezium

mongodb使用debezium

前置 服务器上需要安装jdk11 jdk下载地址 kafka安装 官网下载地址 安装教程 debezium 安装 运行 Debezium 连接器需要 Java 11 或更高版本 Debezium 并不是一个独立的软件&#xff0c;而是很多个 Kafka 连接器的总称。这些 Kafka 连接器分别对应不同的数据库&#xff0c;…
阅读更多...
使用Cesium ion将 Sketchfab 3D 模型添加到您的GIS应用中

使用Cesium ion将 Sketchfab 3D 模型添加到您的GIS应用中

您现在可以将 Sketchfab 中的 3D 模型导入 Cesium ion 中以创建 3D 块&#xff0c;从而更轻松地为地理空间体验创建上下文和内容。 Sketchfab 是 Epic Games 的一部分&#xff0c;也是使用最广泛的 3D 资产市场之一。自 2012 年推出以来&#xff0c;已有超过 1000 万用户使用 …
阅读更多...
2024/4/28 C++day5

2024/4/28 C++day5

有以下类&#xff0c;完成特殊成员函数 class Person { string name; int *age; } class Stu:public Person { const double score; } #include <iostream> #include <string> using namespace std; class Person { string name; int *age ; publi…
阅读更多...
Kafka报错ERROR Exiting Kafka due to fatal exception during startup

Kafka报错ERROR Exiting Kafka due to fatal exception during startup

报错&#xff1a; ERROR Exiting Kafka due to fatal exception during startup. (kafka.Kafka$) kafka.common.InconsistentClusterIdException: The Cluster ID FSzSO50oTLCRhRnRylihcg doesnt match stored clusterId Some(0oSLohwtQZWbIi73YUMs8g) in meta.properties. Th…
阅读更多...
手撕红黑树（kv模型模拟）

手撕红黑树（kv模型模拟）

目录 前言 一、相关概念 二、性质介绍 红黑树平衡说明 三、红黑树模拟&#xff08;kv结构&#xff09; 1、红黑树节点 2、红黑树插入 2、特殊处理情况 声明&#xff1a; 情况一&#xff1a;cur为红&#xff0c;p为红&#xff0c;g为黑&#xff0c;u存在&#xff0c;且…
阅读更多...
MyBatis 核心配置讲解（下）

MyBatis 核心配置讲解（下）

大家好&#xff0c;我是王有志&#xff0c;一个分享硬核 Java 技术的互金摸鱼侠。 我们书接上回&#xff0c;继续聊 MyBatis 的核心配置&#xff0c;我们今天分享剩下的 5 项核心配置。 不过正式开始前&#xff0c;我会先纠正上一篇文章 MyBatis 核心配置讲解&#xff08;上&…
阅读更多...
QAnything知识库问答系统离线部署（LLM+RAG）

QAnything知识库问答系统离线部署（LLM+RAG）

一、QAnything介绍 &#xff08;一&#xff09;简介 QAnything 是网易有道开源的一个问答系统框架&#xff0c;支持私有化部署和SaaS服务两种调用形式。它能够支持多种格式的文件或数据库&#xff0c;提供准确、快速和可靠的问答体验。目前已支持的文件格式包括PDF、Word、PP…
阅读更多...
防火墙对要保护的服务器做端口映射的好处是几个

防火墙对要保护的服务器做端口映射的好处是几个

防火墙对要保护的服务器进行端口映射具有多重好处&#xff0c;这些好处主要围绕网络安全性、灵活性和可管理性展开。以下是对这些好处的专业分析&#xff1a; 1. 增强网络安全性&#xff1a;端口映射允许防火墙对进入服务器的流量进行精确控制。通过映射特定端口&#xff0c;防…
阅读更多...
FPGA秋招-笔记整理（3）无符号数、有符号数

FPGA秋招-笔记整理（3）无符号数、有符号数

参考&#xff1a;Verilog学习笔记——有符号数的乘法和加法 一、无符号数、有符号数 将输入输出全部定义为有符号数 &#xff08;1&#xff09;无符号数的读取按照原码进行&#xff0c;有符号数的读取应该按照补码读取&#xff0c;计算规则为去掉符号位后取反、加1在计算数值…
阅读更多...
Flink学习（九）-jar 包提交给 flink 集群执行

Flink学习（九）-jar 包提交给 flink 集群执行

一、界面执行 1&#xff0c;点击左侧的 submit new job&#xff0c;然后点击add New 2&#xff0c;粘贴程序入口&#xff0c;设置并行度 3&#xff0c;执行后&#xff0c;就可以在 taskManager 中找到相关任务了 二、控制台执行 在命令行中&#xff0c;在flink 的安装目录下&…
阅读更多...
【Java】关于异常你需要知道的事情

【Java】关于异常你需要知道的事情

文章目录 异常体系异常声明捕获多个异常Java中的哪些异常&#xff0c;程序不用捕获处理&#xff1f;【重要】try with resource 异常处理流程foreach中遇到异常面试题try和finally中都由return 异常体系 异常声明 如果声明的是Exception&#xff0c;那么必须要处理如果声明的是…
阅读更多...
基于SpringBoot的合家云社区物业管理平台 - 项目介绍

基于SpringBoot的合家云社区物业管理平台 - 项目介绍

合家云社区物业管理平台 2.合家云需求&设计 2.1 项目概述 2.1.1 项目介绍 合家云社区物业管理平台是一个全新的 ”智慧物业解决方案“&#xff0c;是一款互联网的专业社区物业管理系统。平台通过社区资产管理、小区管理、访客管理、在线报修、意见投诉等多种功能模块&a…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站