二叉搜索树模拟实现

目录

认识二叉搜索树：

模拟实现：

节点结构体构建：

insert（插入）:

 find（查找）：

erase（删除）（重点）：

 全部代码

认识二叉搜索树：

        二叉搜索树（BST，Binary Search Tree）又称二叉排序树，二叉查找树，主要功能是排序，去重，查找一个值是否存在。

        二叉搜索树在普通二叉树的特性上加上了一点，也就是每个根节点，左子树的值始终比根节点的值小，右子树的值始终比根节点的值要大。

        这样做的好处是什么呢？当我们在这颗树中查找某个值时，若这个值比根小就往左走，若这个值比根大就往右走，也就是说，我们最少走高度次，就能找到它，根据二叉树特性：n = 2^h - 1,n表示节点数，h表示高度，换算一下，h = log(n+1)，所以我们查找一个数的时间复杂度就为O(logn),这个时间复杂度是个什么概念呢？若有10亿个数据在树里，当我们查找时，最坏查找30次就能找到，因为2的30次方约等于10亿，相比我们遍历一遍，最坏情况需要查找10亿次，所以它的含金量就不必我多说了。

模拟实现：

节点结构体构建：

        树中的每个节点，我使用结构体来存储：

接下来就可以开始构建类模板了：

insert（插入）:

注意：二叉搜索树一般不允许数据冗余，所以如果插入树中已有的值，则插入失败

思路：用cur找到插入的位置， 将要插入的值和根节点作比较，会出现3种情况，1，比根节点小，cur往左走，2，比根节点大，cur往右走，3，与根节点相等，插入失败。我们每次移动cur都要用parent记录它父节点的位置，这样当找到应该插入的位置时，用parent的左子树或者右子树指向它。

bool insert(const K& val)
	{
		if (_root == nullptr)//若原来树为空
		{
			_root = new node(val);
			return true;
		}
		node* cur = _root;
		node* parent = nullptr;
		while (cur)//开始找插入位置
		{
			if (val < cur->_val)
			{
				parent = cur;
				cur = parent->left;
			}
			else if (val > cur->_val)
			{
				parent = cur;
				cur = parent->right;
			}
			else
			{
				return false;
			}
		}
		cur = new node(val);
		if (val > parent->_val)
		{
			parent->right = cur;
		}
		else
		{
			parent->left = cur;
		}
	}

 find（查找）：

思路：这个简单，被查找的值比根节点小就往左走，比根节点大就往右走，相等返回true，走到空节点还没找到就返回false：

	bool find(const K& val)
	{
		node* cur = _root;
		while (cur)
		{
			if (val > cur->_val)
			{
				cur = cur->right;
			}
			else if (val < cur->_val)
			{
				cur = cur->left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

erase（删除）（重点）：

思路：

在二叉搜索树中删除一个值，先找到这个值所在的节点，删除这个节点后，返回true，找不到返回false，这个被删除的节点肯定不能空出来，还是要它组成一颗二叉搜索树，我们在删除的时候就会遇到这几种情况：

1，要删除的节点的左子树为空，我们只需将要删除的节点的父节点指向该左子树就行，右子树同理：

如图所示：

我们要删除1，因为1只有一个孩子，所以我们只需要将3的左子树指向1的孩子就行。不过要注意，当要删除的就是最上面的根节点时，也就是父节点为空，如下图删除13时，这时需要特判的，我们只需将根节点改成那个唯一的孩子就行。

 2.要删除的节点，左右孩子都存在

        这时要删除这个节点就有点复杂了，就需要使用替代法删除，看下图这个场景，当我们要删除3：

替代法删除， 就是在被删除节点的左右子树中找到能在这个位置占得住脚的值来替换掉这个位置，所以现在主要就是到底哪些值是能在被删除节点的位置站的住脚。如上图，也就是要比1大比6小。

 这些值就是，左子树的最大节点和右子树的最小节点，原理不再多说，想必看上图应该都能体会出来，上图左子树的最大节点是2，右子树的最小节点是4，都能在3的位置占住脚，所以我们只需要随便找到一个，这里我找右子树的最小值，找到后交换右子树最小值和需要删除节点的值，再让右子树最小值的父节点的左子树指向右子树最小值的右一个孩子就行（因为左孩子肯定为空，不然它就不是右子树的最小值），然后删除右节点最小值位置的节点，。

为了帮助理解来模拟一下：

1.找到右子树的最小值4及它的父亲节点：

2.交换需要删除的节点和左子树最小值的值：

 ​​​​​​​3.再让右子树最小值的父节点的左子树指向右子树最小值的右一个孩子：

4.最后删除RIghtMin所在的节点：

 最后达成预期！

注意有特殊情况，需要特判！当右子树的最小值就是右子树的第一个根时，如下图删除3时

这时右子树的最小节点就是第一个根6，此时当我们走到上面模拟的第三步后就会出现这样的情况：

画圈部分直接被抛弃掉了，而且还会造成内存泄漏。

解决方法很简单，只需简单用if判断一下这种情况即可，如果RightMinparent->right==RightMin，就让RightMinparent->right=RightMin->right, 如果RightMinparent->left==RightMin,就让RightMinparent->left=RightMin->right.

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			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 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
				{
					// 左右都不为空，替换法删除
					// 
					// 查找右子树的最小节点替代删除
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)//找右子树的最小节点放在rightMin中
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					swap(cur->_key, rightMin->_key);//找到后交换

					if (rightMinParent->_left == rightMin)//特判
						rightMinParent->_left = rightMin->_right;
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
				}
				return true;
			}
		}
		return false;
	}

 全部代码：

#pragma once
#include<string>

template<class T>
struct BSTNode
{
	BSTNode<T>* left;//左子树
	BSTNode<T>* right;//右子树
	T _val;//值
	BSTNode(T& val)//构造函数
		:left(nullptr)
		, right(nullptr)
		, _val(val);
	{}
};
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* cur = _root;
		node* parent = nullptr;
		while (cur)//开始找插入位置
		{
			if (val < cur->_val)
			{
				parent = cur;
				cur = parent->left;
			}
			else if (val > cur->_val)
			{
				parent = cur;
				cur = parent->right;
			}
			else
			{
				return false;
			}
		}
		cur = new node(val);
		if (val > parent->_val)
		{
			parent->right = cur;
		}
		else
		{
			parent->left = cur;
		}
	}

	bool find(const K& val)
	{
		node* cur = _root;
		while (cur)
		{
			if (val > cur->_val)
			{
				cur = cur->right;
			}
			else if (val < cur->_val)
			{
				cur = cur->left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			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 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
				{
					// 左右都不为空，替换法删除
					// 
					// 查找右子树的最小节点替代删除
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)//找右子树的最小节点放在rightMin中
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					swap(cur->_key, rightMin->_key);//找到后交换

					if (rightMinParent->_left == rightMin)//特判
						rightMinParent->_left = rightMin->_right;
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
				}
				return true;
			}
		}
		return false;
	}
private:
	node* _root = nullptr;
};

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

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

相关文章

[算法][单调栈] [leetcode]316. 去除重复字母

[算法][单调栈] [leetcode]316. 去除重复字母

去除重复字母 给你一个字符串 s &#xff0c;请你去除字符串中重复的字母&#xff0c;使得每个字母只出现一次。需保证 返回结果的 字典序最小&#xff08;要求不能打乱其他字符的相对位置&#xff09;。 字典序最小&#xff1a; 考虑字符串 a 与 字符串 b&#xff0c;如果字…
阅读更多...
Pytest测试实战 —— 分布式执行！

Pytest测试实战 —— 分布式执行！

在这篇文章中&#xff0c;我们将从头开始介绍如何使用Pytest进行测试实战&#xff0c;并探讨如何在分布式环境中执行测试。Pytest是一个功能强大且易于使用的Python测试框架&#xff0c;它提供了丰富的功能和灵活的配置选项&#xff0c;使得编写和执行测试变得简单而又高效。 …
阅读更多...
决策管理中的数学方法

决策管理中的数学方法

需要注意的是，用excel求解的时候需要导入线性规划加载项如下： pert分析需要DecisionTools中的RiskSolver插件 1.链接：https://pan.baidu.com/s/1wKhUFWgNmQ7U33kl5AypZw 提取码：zqkn 2.“Palisade_Book_expires_Aril_10_2025.lic”文件复制到以下路径： C:\Program Files …
阅读更多...
在视频号搞变现，又不想直播，可以试试它！

在视频号搞变现，又不想直播，可以试试它！

大家好&#xff0c;我是电商糖果 视频号这两年流量比较大&#xff0c;甚至有了即将赶超抖音&#xff0c;快手的趋势。 再加上它的用户都是来自微信&#xff0c;属于是私域流量。 所以视频号的用户粘性比较大&#xff0c;而且非常容易变现。 就有不少人想在视频号搞变现&…
阅读更多...
保健品小程序商城线上经营的作用是什么

保健品小程序商城线上经营的作用是什么

保健品涵盖酒水、醋、食品等多个类型&#xff0c;无论厂商还是经销商&#xff0c;手里的品牌和数量都比较多&#xff0c;由于特殊性&#xff0c;商家经营时需要找到目标客户&#xff0c;而市场中虽然有大量客户&#xff0c;但商家实际想要触达却并不容易。 渠道多样化&#xf…
阅读更多...
C#知识|无边框的WinForm窗体，如何拖动位置？

C#知识|无边框的WinForm窗体，如何拖动位置？

哈喽&#xff0c;你好啊&#xff0c;我是雷工&#xff01; 上一节时练习做了一个简单的登录窗体界面&#xff0c;为了美观设置成了无边框&#xff0c; 当运行起来&#xff0c;发现无边框的窗体无法用鼠标拖动位置&#xff0c; 本节记录通过添加代码实现无边框窗体实现移动&…
阅读更多...
VR智慧文旅：开启“韵味”旅游季的新篇章

VR智慧文旅：开启“韵味”旅游季的新篇章

为了充分满足游客的假日文化旅游需求&#xff0c;各地纷纷“解锁”新花样&#xff0c;沉浸式实景观展震撼“出圈”。在数字化浪潮的推动下&#xff0c;文化旅游行业正经历着变革&#xff0c;在万物皆可沉浸的时代&#xff0c;VR智慧文旅燃起了不一样的热度。 许多业内人士认为&…
阅读更多...
【数据结构】顺序表（一）

【数据结构】顺序表（一）

✨✨✨专栏&#xff1a;数据结构 &#x1f9d1;‍&#x1f393;个人主页&#xff1a;SWsunlight 不怕别人看不起&#xff0c;就怕自己不争气。路是人走出来的&#xff0c;关键要靠自己闯。振作起来&#xff0c;生活的含义就是前进。 目录 一、顺序表的概念&#xff1a; 二…
阅读更多...
安卓实现视频录制与显示和翻转摄像头

安卓实现视频录制与显示和翻转摄像头

权限&#xff1a; <!-- 相机权限 --> <uses-featureandroid:name"android.hardware.camera"android:required"false" /> <uses-permission android:name"android.permission.CAMERA" /><!-- 录音权限&#xff08;包括麦克…
阅读更多...
企业网站从传统服务器迁移到弹性云有什么优势呢？

企业网站从传统服务器迁移到弹性云有什么优势呢？

现代企业对于网站和应用程序的可用性和性能要求越来越高&#xff0c;传统基础设施可能无法满足这些需求。弹性云作为一种新兴的云计算服务模式&#xff0c;对于企业网站的运行和管理带来了许多优势。下面是企业网站从传统服务器迁移到弹性云的五大优势&#xff1a; 灵活弹性&a…
阅读更多...
数据结构（一）绪论

数据结构（一）绪论

2024年5月11日 一稿 数据元素+数据项 逻辑结构 集合 线性结构 树形结构 </
阅读更多...
水表智能抄表系统是什么？

水表智能抄表系统是什么？

水表智能抄表系统是一种现代化水资源保护专用工具&#xff0c;它利用先进的物联网、云计算和大数据剖析&#xff0c;完成了智能抄表、实时监控系统、数据分析等作用&#xff0c;大大提高了水务管理的效率和精确性。 1.功能特点 1.1远程控制自动抄表 传统水表抄水表方法采用人…
阅读更多...
SAP-CentralFinance - 会计核算中的组织要素 - 学习心得1

SAP-CentralFinance - 会计核算中的组织要素 - 学习心得1

1. 定义SAP组织架构和理解各组织架构含义 组织结构遍布SAP 系统的所有重要功能范围。FI 中最重要的组织要素是公司代码。它是“财务会计”中的最小组织单位，可以为其编制自主式完整科目集供外部报告使用。其他重要的组织要素是利润中心业务范围和段。您可以为各个利润中…
阅读更多...
Linux系统编程——进程控制

Linux系统编程——进程控制

目录 一&#xff0c;进程创建 1.1 fork回顾 1.2 写时拷贝 1.3 fork用处 1.4 fork调用失败原因 二&#xff0c;进程退出 2.1 进程退出场景 2.2 mainCRTStartup调用 2.3 进程退出码 2.3.1 main函数返回值 2.3.2 strerror ​编辑 2.3.3 命令的退出码 2.4 进程正常退…
阅读更多...
LeetCode-258. 各位相加【数学 数论 模拟】

LeetCode-258. 各位相加【数学 数论 模拟】

LeetCode-258. 各位相加【数学 数论 模拟】 题目描述&#xff1a;解题思路一&#xff1a;循环解题思路二&#xff1a;进阶 O(1)解题思路三&#xff1a; 题目描述&#xff1a; 给定一个非负整数 num&#xff0c;反复将各个位上的数字相加&#xff0c;直到结果为一位数。返回这个…
阅读更多...
记录一次pods 导入 SocketRocket库的经历

记录一次pods 导入 SocketRocket库的经历

折腾一上午&#xff0c;brew 安装成功了 cococapod 然后项目启动下载一个SocketRocket库 下载成功后总是报错&#xff1a; 睡了2个多小时&#xff0c;我在qq就交流群里求助&#xff1a; 终于把项目管理&#xff0c;在命令行里执行这句&#xff1a; open chat_app.xcworkspace…
阅读更多...
企业破产重整：从“至暗时刻”到“涅槃重生”

企业破产重整：从“至暗时刻”到“涅槃重生”

今天我们不谈星辰大海&#xff0c;而是要潜入商业世界的深海区&#xff0c;探索那些濒临绝境的企业是如何借助“破产重整”的神秘力量&#xff0c;实现惊天大逆转的&#xff01; 一、破产重整&#xff0c;到底是个啥&#xff1f; 想象一下&#xff0c;企业像是一位远航的船长…
阅读更多...
【Redis】Redis 事务

【Redis】Redis 事务

Redis 的事务的本质是一组命令的批处理。这组命令在执行过程中会被顺序地、一次性 全部执行完毕&#xff0c;只要没有出现语法错误&#xff0c;这组命令在执行期间不会被中断 1.事务特性 仅保证了数据的一致性 这组命令中的某些命令的执行失败不会影响其它命令的执行&#xff…
阅读更多...
geoserver SQL注入、Think PHP5 SQL注入、spring命令注入

geoserver SQL注入、Think PHP5 SQL注入、spring命令注入

文章目录 一、geoserver SQL注入CVE-2023-25157二、Think PHP5 SQL注入三、Spring Cloud Function SpEL表达式命令注入&#xff08;CVE-2022-22963&#xff09; 一、geoserver SQL注入CVE-2023-25157 介绍&#xff1a;GeoServer是一个开源的地理信息系统&#xff08;GIS&#…
阅读更多...
Java 开发 框架安全：Spring 漏洞序列.（CVE-2022-22965）

Java 开发 框架安全：Spring 漏洞序列.（CVE-2022-22965）

什么叫 Spring 框架. Spring 框架是一个用于构建企业级应用程序的开源框架。它提供了一种全面的编程和配置模型&#xff0c;可以简化应用程序的开发过程。Spring 框架的核心特性包括依赖注入&#xff08;Dependency Injection&#xff09;、面向切面编程&#xff08;Aspect-Or…
阅读更多...
最新文章

Copyright @ 2022~2023