二叉搜索树介绍

⼆叉搜索树

  • 二叉搜索树的概念
  • 二叉搜索树的性能分析
    • 查找性能
    • 插入性能
    • 删除性能
  • 二叉搜索树的插入
  • 二叉搜索树的查找
  • 二叉搜索树的删除
  • ⼆叉搜索树的实现代码
    • 测试代码
  • 二叉搜索树key和key/value使⽤场景
    • key搜索场景
    • key/value搜索场景
    • key/value⼆叉搜索树代码实现
    • 测试代码

二叉搜索树的概念

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

  • 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值
  • 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值
  • 它的左右⼦树也分别为⼆叉搜索树
  • ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，后续我们学习map/set/multimap/ multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等值，multimap/multiset⽀持插⼊相等值
    注意： map和set是平衡二叉搜索树，底层结构是红黑树
    在这里插入图片描述

二叉搜索树的性能分析

查找性能

  • 在最佳情况下，二叉搜索树的高度为log(n+1),其查找效率为O(logn),近似于折半查找.
  • 如果二叉搜索树不平衡，其深度可能达到 n,查找效率退化为O(n),即顺序查找.

插入性能

  • 插入操作通常涉及找到正确的插入位置，然后根据需要进行树的调整以保持平衡。在平衡二叉搜索树中，插入操作的时间复杂度为O(logn).
  • 如果树不平衡，插入操作可能需要更多的时间，尤其是在树的同一侧连续插入时，可能导致树的退化。
    在这里插入图片描述

删除性能

  • 删除操作需要找到被删除节点，然后进行适当的替换和树的调整。在平衡二叉搜索树中，删除操作的时间复杂度也是O(logn).
  • 与插入类似，如果树不平衡，删除操作可能需要更多的时间，尤其是在树的同一侧连续删除时.

总结： 所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为： O(N)那么这样的效率显然是⽆法满⾜我们需求的，后续还会继续讲解⼆叉搜索树的变形，平衡⼆叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。

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

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

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

二叉搜索树的插入

插⼊的具体过程如下：

  • 树为空，则直接新增结点，赋值给root指针
  • 树不空，按⼆叉搜索树性质，插⼊值⽐当前结点⼤往右⾛，插⼊值⽐当前结点⼩往左⾛，找到 空位置，插⼊新结点。
  • 如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插⼊新结点。（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右走，⼀会往左走）
    在这里插入图片描述

二叉搜索树的查找

  • 从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找。
  • 最多查找⾼度次，⾛到到空，还没找到，这个值不存在。
  • 如果不⽀持插⼊相等的值，找到x即可返回
  • 如果⽀持插⼊相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。如下图，查找3，要找到1的右孩⼦的那个3返回
    在这里插入图片描述

二叉搜索树的删除

⾸先查找元素是否在⼆叉搜索树中，如果不存在，则返回false。
如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）

  • 要删除结点N左右孩⼦均为空
  • 要删除的结点N左孩⼦位空，右孩⼦结点不为空
  • 要删除的结点N右孩⼦位空，左孩⼦结点不为空
  • 要删除的结点N左右孩⼦结点均不为空

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

  • 把N结点的⽗亲对应孩⼦指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是⼀样的）
  • 把N结点的⽗亲对应孩⼦指针指向N的右孩⼦，直接删除N结点
  • 把N结点的⽗亲对应孩⼦指针指向N的左孩⼦，直接删除N结点
    在这里插入图片描述
  • ⽆法直接删除N结点，因为N的两个孩⼦⽆处安放，只能⽤ 替换法删除。找N左⼦树的值最⼤结点R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满⾜⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转⽽变成删除R结点，R结点符合情况2或情况3，可以直接删除。
    在这里插入图片描述

⼆叉搜索树的实现代码


namespace key
{
//节点
template<class K>
struct BSTNode
{
	K _key;
	BSTNode* _left;
	BSTNode* _right;

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

//二叉搜索树
template<class K>
class BSTree
{
	using Node = BSTNode<K>;
public:
	bool Insert(const K& key)
	{
	    //如果是根节点，直接插入
		if (_root == nullptr)
		{
			_root = new Node(key);
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key);
		//判断父节点的左边插入还是右边插入
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if(cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}
	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else //查找到与key相等的地方
			{
				//左为空
				if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				//右为空
				else if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else
				{
					//左右子树都不为空
					Node* r = cur->_right;
					Node* rp = cur;
					while (r->_left)
					{
						rp = r;
						r = r->_left;
					}
					cur->_key = r->_key;
					if (rp->_left == r)
					{
						rp->_left = r->_right;
					}
					else
					{
						rp->_right = r->_right;
					}
					delete r;
				}
				return true;
			}
		}
		return false;
	}
private:
	Node* _root = nullptr;
};
}

测试代码

测试插入

int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
key::BSTree<int> st;
for (auto e : a)
{
	st.Insert(e);
}

在这里插入图片描述
测试删除

int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
key::BSTree<int> st;
for (auto e : a)
{
	st.Insert(e);
}
for (auto e : a)
{
	st.Erase(e);
	//打印数据
}

在这里插入图片描述

二叉搜索树key和key/value使⽤场景

key搜索场景

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

  • 检查⼀篇英⽂⽂章单词拼写是否正确，将词库中所有单词放⼊⼆叉搜索树，读取⽂章中的单词，查找是否在⼆叉搜索树中，不在则波浪线标红提⽰。(VS的检查与这个也很类似)

key/value搜索场景

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

  • 统计⼀篇⽂章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。

key/value⼆叉搜索树代码实现

和key⼆叉搜索树代码实现类似，需要在节点中增加value这个变量。

namespace key_value
{
	template<class K,class V>
	struct BSTNode
	{
		K _key;
		V _value;
		BSTNode* _left;
		BSTNode* _right;

		BSTNode(const K& key,const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};
	template<class K,class V>
	class BSTree
	{
	public:
		using Node = BSTNode<K, V>;

		bool Insert(const K& key,const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key,value);
			}
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(key,value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
					}
					else if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;
					}
					else
					{
						//左右子树都不为空
						Node* r = cur->_right;
						Node* rp = cur;
						while (r->_left)
						{
							rp = r;
							r = r->_left;
						}
						cur->_key = r->_key;
						if (rp->_left == r)
						{
							rp->_left = r->_right;
						}
						else
						{
							rp->_right = r->_right;
						}
						delete r;
					}
					return true;
				}
			}
			return false;
		}
		~BSTree()
		{
			Destory(_root);
		}
		BSTree() = default;//C++11 强制生成默认构造
		BSTree(const BSTree<K, V>& st)
		{
			_root = Copy(st._root);
		}
		BSTree<K, V>& operator=(BSTree tmp)
		{
			swap(_root, tmp._root);
			return *this;
		}
	protected:
		//前序遍历复制二叉搜索树
		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			Node* newnode = new Node(root->_key, root->_value);
			newnode->_left = Copy(root->_left);
			newnode->_right = Copy(root->_right);
			return newnode;
		}
		//后序遍历销毁二叉搜索树
		void Destory(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			Destory(root->_left);
			Destory(root->_right);
			delete root;
		}
	private:
		Node* _root = nullptr;
	};
}

测试代码

	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
	key_value::BSTree<string, int> st;
	for (auto& e : arr)
	{
		auto ret = st.Find(e);
		if (ret != nullptr)
		{
			ret->_value++;
		}
		else
		{
			st.Insert(e, 1);
		}
	}

在这里插入图片描述

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

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

相关文章

7.揭秘C语言输入输出内幕：printf与scanf的深度剖析

7.揭秘C语言输入输出内幕：printf与scanf的深度剖析

揭秘C语言输入输出内幕&#xff1a;printf与scanf的深度剖析 C语言往期系列文章目录 往期回顾&#xff1a; VS 2022 社区版C语言的安装教程&#xff0c;不要再卡在下载0B/s啦C语言入门&#xff1a;解锁基础概念&#xff0c;动手实现首个C程序C语言概念之旅&#xff1a;解锁关…
阅读更多...
5.4.2-1 编写Java程序在HDFS上创建文件

5.4.2-1 编写Java程序在HDFS上创建文件

本次实战涉及使用Java操作Hadoop HDFS&#xff0c;包括创建文件、判断文件存在性及异常处理。通过手动添加依赖、启动HDFS服务&#xff0c;成功在HDFS上创建和检查文件。进一步探索了文件操作的最佳实践&#xff0c;如检查文件存在性以避免重复创建&#xff0c;以及处理HDFS安全…
阅读更多...
RabbitMQ教程：路由（Routing）（四）

RabbitMQ教程：路由（Routing）（四）

文章目录 RabbitMQ教程&#xff1a;路由&#xff08;Routing&#xff09;&#xff08;四&#xff09;一、引言二、基本概念2.1 路由与绑定2.2 Direct交换机2.3 多绑定2.4 发送日志2.5 订阅 三、整合代码3.1 EmitLogDirectApp.cs3.2 ReceiveLogsDirectApp.cs3.3 推送所有和接收e…
阅读更多...
智云-一个抓取web流量的轻量级蜜罐v1.5

智云-一个抓取web流量的轻量级蜜罐v1.5

智云-一个抓取web流量的轻量级蜜罐v1.5 github地址 https://github.com/xiaoxiaoranxxx/POT-ZHIYUN 新增功能-自定义漏洞信息 可通过正则来添加相关路由以及响应来伪造 nacos的版本响应如下 日流量态势 月流量态势 抓取流量效果
阅读更多...
21.UE5游戏存档，读档，函数库

21.UE5游戏存档，读档，函数库

2-23 游戏存档、读档、函数库_哔哩哔哩_bilibili 目录 1.存档蓝图 2.函数库 2.1保存存档 2.2读取存档&#xff1a; 3.加载游戏&#xff0c;保存游戏 3.1游戏实例对象 3.2 加载游戏 3.3保存游戏 这一节的内容较为错综复杂&#xff0c;中间没有运行程序进行阶段性成果的验…
阅读更多...
实验5：网络设备发现、管理和维护

实验5：网络设备发现、管理和维护

实验5&#xff1a;网络设备发现、管理和维护 实验目的及要求&#xff1a; 通过实验&#xff0c;掌握Cisco 路由器和交换机的IOS配置管理。自动从NTP服务器获取时间信息。能够利用TFTP服务器实现路由器和交换机配置文件的备份和恢复。同时验证CDP协议和LLDP协议的网络参数。完…
阅读更多...
vue 项目使用 nginx 部署

vue 项目使用 nginx 部署

前言 记录下使用element-admin-template 改造项目踩过的坑及打包部署过程 一、根据权限增加动态路由不生效 原因是Sidebar中路由取的 this.$router.options.routes,需要在计算路由 permission.js 增加如下代码 // generate accessible routes map based on roles const acce…
阅读更多...
DataWorks on EMR StarRocks，打造标准湖仓新范式

DataWorks on EMR StarRocks，打造标准湖仓新范式

在大数据领域&#xff0c;数据仓库和实时分析系统扮演着至关重要的角色。DataWorks 基于大数据引擎&#xff0c;为数据仓库/数据湖/湖仓一体等解决方案提供统一的全链路大数据开发治理平台&#xff0c;为用户带来智能化的数据开发和分析体验。而阿里云提供的 EMR Serverless St…
阅读更多...
七、利用CSS和多媒体美化页面的习题

七、利用CSS和多媒体美化页面的习题

题目一&#xff1a; 利用CSS技术&#xff0c;结合表格和列表&#xff0c;制作并美化 “ 翡翠阁 ”页面。运行效果如下 运行效果&#xff1a; 代码 <!DOCTYPE html> <html><head><meta charset"utf-8" /><title>翡翠阁</title>&…
阅读更多...
游戏引擎学习第15天

游戏引擎学习第15天

视频参考:https://www.bilibili.com/video/BV1mbUBY7E24 关于游戏中文件输入输出&#xff08;IO&#xff09;操作的讨论。主要分为两类&#xff1a; 只读资产的加载 这部分主要涉及游戏中用于展示和运行的只读资源&#xff0c;例如音乐、音效、美术资源&#xff08;如 3D 模型和…
阅读更多...
【动手学深度学习Pytorch】2. Softmax回归代码

【动手学深度学习Pytorch】2. Softmax回归代码

零实现 导入所需要的包&#xff1a; import torch from IPython import display from d2l import torch as d2l定义数据集参数、模型参数&#xff1a; batch_size 256 # 每次随机读取256张图片 train_iter, test_iter d2l.load_data_fashion_mnist(batch_size) # 将展平每个…
阅读更多...
51单片机基础05 实时时钟-思路及代码参考2、3

51单片机基础05 实时时钟-思路及代码参考2、3

目录 一、思路二 1、原理图 2、代码 二、思路三 1、原理图 2、代码 一、思路二 所有设定功能相关的操作均在矩阵键盘进行实现&#xff0c;并在定时器中扫描、计数等 1、原理图 2、代码 #include <AT89X52.h> //调用51单片机的头文件 //------------------…
阅读更多...
Notepad++的完美替代

Notepad++的完美替代

由于Notepad的作者曾发表过可能在开发者代码中植入恶意软件的言论&#xff0c;他备受指责。在此&#xff0c;我向大家推荐一个Notepad的完美替代品——NotepadNext和Notepad--。 1、NotepadNext NotepadNext的特点&#xff1a; 1、跨平台兼容性 NotepadNext基于Electron或Qt…
阅读更多...
Python | Leetcode Python题解之第564题数组嵌套

Python | Leetcode Python题解之第564题数组嵌套

题目&#xff1a; 题解&#xff1a; class Solution:def arrayNesting(self, nums: List[int]) -> int:ans, n 0, len(nums)for i in range(n):cnt 0while nums[i] < n:num nums[i]nums[i] ni numcnt 1ans max(ans, cnt)return ans
阅读更多...
面试经典 150 题：20、2、228、122

面试经典 150 题：20、2、228、122

20. 有效的括号 参考代码 #include <stack>class Solution { public:bool isValid(string s) {if(s.size() < 2){ //特判&#xff1a;空字符串和一个字符的情况return false;}bool flag true;stack<char> st; //栈for(int i0; i<s.size(); i){if(s[i] ( |…
阅读更多...
使用vscode+expo+Android夜神模拟器运行react-native项目

使用vscode+expo+Android夜神模拟器运行react-native项目

1.进入夜神模拟器安装路径下的bin目录 2.输入命令&#xff0c;连接Android Studio 启动夜神模拟器后&#xff0c; 打开安装目录的bin文件夹执行下面的命令&#xff0c;只需执行一次&#xff09; nox_adb.exe connect 127.0.0.1:62001adb connect 127.0.0.1:62001 3.运行项目…
阅读更多...
【STM32】USB 简要驱动软件架构图

【STM32】USB 简要驱动软件架构图

STM32 USB 软件架构比较复杂&#xff0c;建议去看 UM 1734 或者 st wiki STM32 USB call graph STM32 USB Device Library files organization Reference [1]: https://wiki.stmicroelectronics.cn/stm32mcu/wiki/Introduction_to_USB_with_STM32 [2]: UM1734
阅读更多...
鸿蒙中如何实现图片拉伸效果

鸿蒙中如何实现图片拉伸效果

2024年10月22日&#xff0c;华为发布会上&#xff0c;推出鸿蒙5.0。现在加入恰逢时机&#xff0c;你&#xff0c;我皆是鸿蒙时代合伙人。无论为了学习技术&#xff0c;还是为了谋福利&#xff0c;在鸿蒙的浩瀚海洋中分到一杯羹。现在学习鸿蒙正当时。 一文了解鸿蒙中图片拉伸的…
阅读更多...
VUE+SPRINGBOOT实现邮箱注册、重置密码、登录功能

VUE+SPRINGBOOT实现邮箱注册、重置密码、登录功能

随着互联网的发展&#xff0c;网站用户的管理、触达、消息通知成为一个网站设计是否合理的重要标志。目前主流互联网公司都支持手机验证码注册、登录。但是手机短信作为服务端网站是需要付出运营商通信成本的&#xff0c;而邮箱的注册、登录、重置密码&#xff0c;无疑成为了这…
阅读更多...
网络基础（4）传输层

网络基础（4）传输层

既然是传输层首先就要明确实在层状结构的哪里,除开物理层之外分成了四层协议: 到这里上层(应用层)的使用已经没有问题&#xff0c;之前使用的套接字都是在应用层的。 再说端口号 到一个主机收到一个报文的时候&#xff0c;这个报文中一定存在这个报文需要到的主机的ip号。如果…
阅读更多...
最新文章

Copyright @ 2022~2023