从零开始的c++之旅——二叉搜索树

1、二叉搜索树概念

1. ⼆叉搜索树的概念

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

         • 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值

         • 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值

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

         • ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等 值，multimap/multiset⽀持插⼊相等值

以下就是两颗二叉搜索树

2. ⼆叉搜索树的性能分析

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

        最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为：O( N/2 ) 

        所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为：O(N)

这样的效率显然是⽆法满⾜我们需求的，后续会讲解⼆叉搜索树的变形，平衡⼆ 叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。

⼆分查找也可以实现O( logN ) 级别的查找效率，但是⼆分查找有两⼤缺陷：

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

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

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

3. 二叉搜索树的实现

        需要明确的一点是，我们此处实现的是不可插入相同值的二叉搜索树。

        而搜索二叉树的本质还是使用递归来完成，因此与我们之前博客实现的二叉树逻辑大体相似，因此一些类似的操作我们简略描述。

3.1 定义二叉搜索树

3.1.2 定义二叉搜索树节点

        这与之前实现的二叉树类似，只不过用上了模板跟构造函数，因为构造函数我们在后面需要用来生成节点。

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

	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

3.1.2 定义二叉搜索树结构 

template<class K>
class BSTree
{
	//这里也能体现封装思想，不管我们如何实现的类此处我们只需定义成Node即可
    typedef BSTNode<K> Node; 

private:
	Node* _root = nullptr;//头节点
}

3.2 中序遍历

        根据二叉搜索树的性质，中序遍历得到的应该是一个有序的升序列表。

        中序搜索的逻辑与之前大差不差，我们只需记住：先遍历左子树，在打印当前根节点的值，而后遍历右子树，这就是“ 左 根 右”。

        不要忘记了返回条件：遍历到空需要返回到上一级。

        最后需要注意的一点是，我们遍历时需要传入头节点root，但是root是我们类的私有成员变量，在类外无法访问，那我们怎么办呢？对于这种问题有个统一的办法，我们可以将这个函数定义成类的私有成员，在写一个类的公有成员函数，去调用类的私有成员函数即可。

pubilc：
 	void InOder()
	{
		_InOder(_root);
		cout << endl;
	}   

private：
    void _InOder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOder(root->_left);
		cout << root->_key << " ";
		_InOder(root->_right);
	}

3.3 插入

我们根据搜索二叉树的特点可以得出我们的插入逻辑：

        1.若当前的树是一颗空树，那么我们只需新增节点赋给root节点即可。

        2.若树不为空我们只需根据二叉搜索树的性质，定义一个指针cur遍历二叉搜索树，若cur指向的节点值大于我们要插入的值va，则cur往右子树走，反之则往左子树走，知道cur的下一节点为空时，用val初始化一个节点并根据cur和val的值比较，判断插入到左子树还是右子树

	bool Insert(const K& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(val);
			return true;
		}
		
		Node* parent = _root;
		Node* cur = _root;
		while (cur)
		{
			if ( val < cur->_key )
			{
				parent = cur;
				cur = cur->_left;
			}
			else if ( val > cur->_key )
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		
		cur = new Node(val);
		if (val > parent->_key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left= cur ;
		}

		return true;
	}

3.4 查找

        从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找。⾛到到空，还没找到，这个值不存在，返回false。找到则返回true。

	bool Find(const K& val)
	{
		Node* cur = _root;
		while (cur)
		{
			if (val > cur->_key)
			{
				cur = cur->_right;
			}
			else if (val < cur->_key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

 3.5 删除

        二叉搜索树的插入时整个步骤中最复杂的，因为在插入数据时我们需要对二叉搜索树的部分结构进行适当的调整，使其保持原有的性质。

我们以下图的删除二叉数为例

在删除之前，我们还需要明确一点，我们删除节点释放完资源之后，还需使其对应的父亲节点指向nullptr，避免产生野指针的问题，因此我们我们要一个指针cur来搜寻要删除的节点，还需要一个指针parent来记录cur的前一节点。

在删除的过程中，分为了好几种情况。，我们需要分别讨论

   1. 删除的位置为叶子节点
           这时候只需要cur搜索到对应的节点，再删除即可。

   2. 删除的位置只有一个孩子节点。
           若cur为parent的左节点，则使 parent->left 指向cur的非空节点
           反之则使 parent->right 指向cur的非空节点

   3.删除位置有两个孩子节点
           这是最后一种也是最复杂的一种情况。有两个孩子意味着删除了该节点后我们需要对搜索二叉树部分结构进行适当的调整。

           这里我没有两种方法：我们定义一个指针MaxLeft，使其找到要删除节点cur左子树的最大值，或者定义一个指针MinRight，使其找到cur右子树的最小节点，将其与cur的值进行交换，在删除LeftMax或者MinRight指向的节点即可
           为什么可以选择这两个节点的其中一个呢，因为只有选择这两个节点才会保证二叉搜索树的性质不变。
           我们以交换右子树最小节点为例，下列图我们可以看出，MidRight指针与cur交换完之后二叉搜索树的性质依然符合。

           但是我们还需要注意的是，和前面的两点一样，我们删除掉MidRight节点之后，不要文件将其父节点对应的指针指向nullptr，因此我们还需要定义一个指针PMidRight，防止释放完MidRight之后找不到其对应父节点。

以下是实现的代码

	bool Erase(const K& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(val);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (val < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (val > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				if (cur->_left == nullptr)
				{
					//让父亲指向我的右
					if (cur==parent->_right)
					{
						parent->_right=cur->_right;
					}
					else
					{
						parent->_left = cur->_right;
					}
					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					if (cur == parent->_right)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}

					delete cur;
					return true;
				}
				else
				{
					Node* rightMin = cur->_right;
					Node* rightMinP = cur;
					while (rightMin->_left)
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					if (rightMinP->_left == rightMin)
						rightMinP->_left = rightMin->_right;
					else
						rightMinP->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}


		return false;
	}

4.源代码

#pragma once
#include<iostream>
#include<vector>
using namespace std;

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

	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

template<class K>
class BSTree
{
	typedef BSTNode<K> Node;
	
public:
	bool Insert(const K& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(val);
			return true;
		}
		
		Node* parent = _root;
		Node* cur = _root;
		while (cur)
		{
			if ( val < cur->_key )
			{
				parent = cur;
				cur = cur->_left;
			}
			else if ( val > cur->_key )
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		
		cur = new Node(val);
		if (val > parent->_key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left= cur ;
		}

		return true;
	}

	bool Find(const K& val)
	{
		Node* cur = _root;
		while (cur)
		{
			if (val > cur->_key)
			{
				cur = cur->_right;
			}
			else if (val < cur->_key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	void InOder()
	{
		_InOder(_root);
		cout << endl;
	}

	bool Erase(const K& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(val);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (val < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (val > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				if (cur->_left == nullptr)
				{
					//让父亲指向我的右
					if (cur==parent->_right)
					{
						parent->_right=cur->_right;
					}
					else
					{
						parent->_left = cur->_right;
					}
					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					if (cur == parent->_right)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}

					delete cur;
					return true;
				}
				else
				{
					Node* rightMin = cur->_right;
					Node* rightMinP = cur;
					while (rightMin->_left)
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					if (rightMinP->_left == rightMin)
						rightMinP->_left = rightMin->_right;
					else
						rightMinP->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}


		return false;
	}
	
private:
	Node* _root = nullptr;

	void _InOder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOder(root->_left);
		cout << root->_key << " ";
		_InOder(root->_right);
	}
};

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

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

相关文章

类与对象；

类与对象；

目录 一、认识类&#xff1b; 1、类的引入&#xff1b; 2、类的定义&#xff1b; 类的两种定义方式&#xff1a; 3、类的访问限定符及封装&#xff1b; 4、类的作用域&#xff1b; 5、类的实例化&#xff1b; 6、类对象模型&#xff1b; 计算类对象的大小&#xff1b; …
阅读更多...
ceph的集群管理

ceph的集群管理

0 环境说明 ip地址主机名额外硬盘是否加入ceph集群10.0.0.141ceph141sdb 300G&#xff0c;sdc 500G是10.0.0.142ceph142sdb 300G&#xff0c;sdc 500G, sdd 1000G否10.0.0.143ceph143sdb 300G&#xff0c;sdc 500G否 在上一篇文章中&#xff0c;已经成功地初始化了一个ceph管…
阅读更多...
企业无线解决方案

企业无线解决方案

前言 无线广域网 无线广域网WWAN&#xff08;Wireless Wide Area Network&#xff09;目前已经成为了全球通信系统的核心组成部分&#xff0c;我们所熟悉的2G网络、3G网络和4G网络&#xff08;LTE&#xff09;等等都是WWAN的典型代表。通过WWAN&#xff0c;用户几乎可以在任何…
阅读更多...
Springboot集成ElasticSearch实现minio文件内容全文检索

Springboot集成ElasticSearch实现minio文件内容全文检索

一、docker安装Elasticsearch &#xff08;1&#xff09;springboot和Elasticsearch的版本对应关系如下&#xff0c;请看版本对应&#xff1a; 注意安装对应版本&#xff0c;否则可能会出现一些未知的错误。 &#xff08;2&#xff09;拉取镜像 docker pull elasticsearch:7…
阅读更多...
前后端请求响应

前后端请求响应

引入 在之前的例子中&#xff0c;我们编写了一个简单的web类&#xff0c;我们运行启动类&#xff0c;启动内嵌的tomcat后就可以在浏览器通过特定的路径访问tomcat中的应用程序。 但之前编写的程序仅仅是个简单的java类&#xff0c;其并未实现某个接口或继承某个类&…
阅读更多...
VS2022编译32位OpenCV

VS2022编译32位OpenCV

使用环境 Visual Studio 2022 OpenCV: 4.7.0 cmake: 3.30.2一、使用CMake工具生成vs2022的openCV工程解决方案 打开cmake&#xff0c;选择opencv的源代码目录&#xff0c;创建一个文件夹&#xff0c;作为VS工程文件的生成目录 点击configure构建项目&#xff0c;弹出构建设置…
阅读更多...
电子应用设计方案-12：智能窗帘系统方案设计

电子应用设计方案-12：智能窗帘系统方案设计

一、系统概述 本设计方案旨在打造便捷、高效的全自动智能窗帘系统。 二、硬件选择 1. 电机&#xff1a;选用低噪音、扭矩合适的智能电机&#xff0c;根据窗帘尺寸和重量确定电机功率&#xff0c;确保能平稳拉动窗帘。 2. 轨道&#xff1a;选择坚固、顺滑的铝合金轨道&…
阅读更多...
MySQL系统优化

MySQL系统优化

文章目录 MySQL系统优化第一章&#xff1a;引言第二章&#xff1a;MySQL服务架构优化1. 读写分离2. 水平分区与垂直分区3. 缓存策略 第三章&#xff1a;MySQL配置优化1. 内存分配优化Buffer Pool 的优化查询缓存与表缓存Key Buffer 2. 连接优化最大连接数会话超时连接池 3. 日志…
阅读更多...
LLM - 计算 多模态大语言模型 的参数量(Qwen2-VL、Llama-3.1) 教程

LLM - 计算 多模态大语言模型 的参数量(Qwen2-VL、Llama-3.1) 教程

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/143749468 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 影响 (…
阅读更多...
光耦选型指南

光耦选型指南

一、指南说明 针对光偶选型和实际使用过程中出现因光偶特性变化引起的产品失效问题&#xff0c;提供指导。光耦属于易失效器件&#xff0c;选型和使用过程中要特别的小心。目前发现&#xff0c;因光偶的选型&#xff0c;光偶工作电流&#xff0c;CTR参数选型不合适&#xff0c…
阅读更多...
git创建远程仓库，以gitee码云为例GitHub同理

git创建远程仓库，以gitee码云为例GitHub同理

git远程Remote服务端仓库构建的视频教程在这 Git建立服务端Remote远程仓库&#xff0c;gitee码云例&#xff0c;Github_哔哩哔哩_bilibili 1、登gitee码云/Github 登录 - Gitee.com https://github.com/ &#xff08;没账号的注册一下就行&#xff09; 点击如下图位置的创…
阅读更多...
19.UE5道具掉落

19.UE5道具掉落

2-21 道具掉落&#xff0c;回血、回蓝、升级提升伤害_哔哩哔哩_bilibili 目录 1.道具的创建&#xff0c;道具功能的实现 2.随机掉落 1.道具的创建&#xff0c;道具功能的实现 新建Actor蓝图&#xff0c;并命名为道具总类&#xff0c;添加一个Niagara粒子组件和一个碰撞箱bo…
阅读更多...
排序算法（基础）大全

排序算法（基础）大全

一、排序算法的作用&#xff1a; 排序算法的主要作用是将一组数据按照特定的顺序进行排列&#xff0c;使得数据更加有序和有组织。 1. 查找效率&#xff1a;通过将数据进行排序&#xff0c;可以提高查找算法的效率。在有序的数据中&#xff0c;可以使用更加高效的查找算法&…
阅读更多...
《Java核心技术 卷I》用户界面AWT事件继承层次

《Java核心技术 卷I》用户界面AWT事件继承层次

AWT事件继承层次 EventObject类有一个子类AWTEvent&#xff0c;它是所有AWT事件类的父类。 Swing组件会生成更多其他事件对象&#xff0c;都直接拓展自EventObject而不是AWTEvent。 AWT将事件分为底层(low-level)事件和语义事件。 语义事件&#xff1a;表示用户的动作事件&…
阅读更多...
24-Ingest Pipeline Painless Script

24-Ingest Pipeline Painless Script

将文档中的tags字段按照逗号&#xff08;,&#xff09;分隔符进行分割。 同时为文档&#xff0c;增加一个字段。blog查看量 DELETE tech_blogs#Blog数据&#xff0c;包含3个字段&#xff0c;tags用逗号间隔 PUT tech_blogs/_doc/1 {"title":"Introducing big …
阅读更多...
node.js下载安装步骤整理

node.js下载安装步骤整理

>> 进入node.js下载页面下载 | Node.js 中文网 >>点击 全部安装包 >>删除网址node后面部分&#xff0c;只保留如图所示部分&#xff0c;回车 >>点击进入v11.0.0/版本 >>点击下载node-v11.0.0-win-x64.zip(电脑是windows 64位操作系统适用) >…
阅读更多...
【HAProxy09】企业级反向代理HAProxy高级功能之压缩功能与后端服务器健康性监测

【HAProxy09】企业级反向代理HAProxy高级功能之压缩功能与后端服务器健康性监测

HAProxy 高级功能 介绍 HAProxy 高级配置及实用案例 压缩功能 对响应给客户端的报文进行压缩&#xff0c;以节省网络带宽&#xff0c;但是会占用部分CPU性能 建议在后端服务器开启压缩功能&#xff0c;而非在HAProxy上开启压缩 注意&#xff1a;默认Ubuntu的包安装nginx开…
阅读更多...
右键添加获取可供WSL使用的路径，对windows文件夹也适用，即获取符合Linux规范的路径内容给WSL

右键添加获取可供WSL使用的路径，对windows文件夹也适用，即获取符合Linux规范的路径内容给WSL

文章目录 1. 功能展示1.1. 对 WSL 文件/文件夹/目录空白位置 使用1.2. 对 Windows 文件/文件夹/目录空白位置 使用1.3. Fin 2. 方法3. 文件内容3.1. AddWSLPath.reg3.2. CopyPath.vbs 4. 念念碎 1. 功能展示 1.1. 对 WSL 文件/文件夹/目录空白位置 使用 输出 /etc 1.2. 对 Wi…
阅读更多...
数据分析——Python绘制实时的动态折线图

数据分析——Python绘制实时的动态折线图

最近在做视觉应用开发&#xff0c;有个需求需要实时获取当前识别到的位姿点位是否有突变&#xff0c;从而确认是否是视觉算法的问题&#xff0c;发现Python的Matplotlib进行绘制比较方便。 目录 1.数据绘制2.绘制实时的动态折线图3.保存实时数据到CSV文件中 import matplotlib.…
阅读更多...
Chrome 浏览器开启打印模式

Chrome 浏览器开启打印模式

打开开发者工具ctrl shift p输入print 找到 Emulate CSS print media type
阅读更多...
最新文章

Copyright @ 2022~2023