二叉搜索树（BST,Binary Search Tree）

目录

前言

一、二叉搜索树概念

二、二叉搜索树的实现与操作

1.查找

2.插入

3.删除

4.中序遍历 

5.完整代码 

三、二叉搜索树的应用（K模型、KV模型）

1.K模型

2.KV模型

3.完整代码

四、二叉搜索树的性能分析

前言

为何学？

1.二叉搜索树是一种树形结构，是一种查找效率非常高的结构，值得我们去学习

2.map和set的底层也是二叉搜素树，学习二叉搜索树可以让我们更好的了解set和map的特性

一、二叉搜索树概念

二叉搜索树（BST,Binary Search Tree）又称二叉排序树、二叉查找树

它可以是一颗空树

如果不是，它（或者说它的任何一颗子树）必须满足下列条件：

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

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

3.左、右子树都是二叉搜索树 

二、二叉搜索树的实现与操作

节点结构

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

	Node* _left;
	Node* _right;
	K _key;

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

树类

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	bool Insert(const K& key){}
    bool Find(const K& key){}
    bool Erase(const K& key){}
    void _InOrder(Node* root){}

    void InOrder()
    {
	    _InOrder(root);
    }
private:
	Node* root = nullptr;
};

 

1.查找

从根开始查找比较，比当前根值大往右边查找，比当前根值大往右边查找，且最多查找高度次，走到空还未找到，则所查找值不存在

代码实现：

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;
}

2.插入

1.如果为空树，则将创建新节点，并将新节点赋值给根节点（root指针）

2.如果树不为空，则按二叉搜索树的性质先查找插入位置，再插入

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

	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
		{
			return false;
		}
	}

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

	return true;
}

3.删除

在二叉搜索树中删除是一个稍显麻烦的事，其中包含了许多细节

我们可以知道，待删除的节点有四种情景：

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

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

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

4.要删除的结点有左、右孩子结点

 在后面的处理中1情景和23情景可以融合，因此去掉1情景，我们有3种情景

  • 情景2：使待删除节点的父节点指向待删除节点的左孩子，删除待删除节点
  • 情景3：使待删除节点的父节点指向待删除节点的右孩子，删除待删除节点 
  • 情景4：

这里我们事用替换法删除--即在待删除节点的子树中找一个合适的替换节点，用它的值替换填补调待删除节点，可以找左子树的最大值或者右子树的最小值 ，在处理替换节点的子树问题

下面的演示代码找的树右子树的最小值替换：

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->_right)
					{
						parent->_right = cur->_right;
					}
					else
					{
						parent->_left = cur->_right;
					}
				}

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

				delete cur;
				return true;
			}
			else
			{
				// 替换法
				Node* rightMinParent = cur;
				Node* rightMin = cur->_right;
				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}

				cur->_key = rightMin->_key;

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

				delete rightMin;
				return true;
			}
		}
	}

	return false;
}

4.中序遍历 

既然二叉搜索树能叫做二叉排序树，自然是有原因的，在二叉搜索树中，对二叉搜索树来一次中序遍历，即可得到一组有序元素

 在C++的类中，不能直接调用递归函数，需要嵌套一层递归

void InOrder()
{
	_InOrder(_root);
	cout << endl;
}
void _InOrder(Node* root)
{
	if (root == nullptr)
		return;

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

5.完整代码 

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

	Node* _left;
	Node* _right;
	K _key;

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

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	
	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}

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

		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
			{
				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* 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->_right)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}

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

					delete cur;
					return true;
				}
				else
				{
					// 替换法
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

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

					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}

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

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

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

private:
	Node* _root = nullptr;
};

三、二叉搜索树的应用（K模型、KV模型）

1.K模型

K模型中只有一个key值作为关键码，只存储key值 

如我们要在一个词库中搜索一个单词 “key”，我们只需要以这个词库的每一个单词作为key值构建二叉搜索树，再在这个树中查找key值为“key”的节点

2.KV模型

KV模型中的每一个key值都有一个对应的value值（也叫映射），即<Key,Value>键值对

如我们平时学习上经常用到的英汉词典，每个英文都对应着中文，英文单词与其对应的<Word,Chinese>就构成了一种键值对

下面就是上述K模型代码改造的KV模型代码

3.完整代码

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

	Node* _left;
	Node* _right;
	K _key;
	V _value;

	BSTreeNode(const K& key, const V& value)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
		, _value(value)
	{}
};

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	bool Insert(const K& key, const V& value)
	{
		if (_root == nullptr)
		{
			_root = new Node(key, value);
			return true;
		}

		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
			{
				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* 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->_right)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}

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

					delete cur;
					return true;
				}
				else
				{
					// 替换法
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

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

					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}

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

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

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

private:
	Node* _root = nullptr;
};

四、二叉搜索树的性能分析

根据上面的介绍我们可以知道，无论是删除还是插入，都需要先查找到需要处理的位置，因此，查找效率代表了二叉搜索树的各个操作额性能

对于一个有n个节点的二叉搜索树，查找的平均长度差不多就是二叉搜索树的深度，节点越深，次数越多。

插入次序不同，得到的二叉搜索树的结构可能不同，比如下图：

对于较好的情况参考上面的左图，二叉树为完全二叉树或者说接近完全二叉树，查找的平均次数为log n 

对于较差的情况参考上面的右图，二叉搜索树退化成单只树或者说接近单只树，查找的平均次数为n

若是退化为单只树，二叉搜索树就失去了它的性能优势

要想二叉搜索树的性能不管怎样插入都能达到最优，请继续学习后面大佬们发明的AVL树和红黑树，在那里你可以找到所要的答案

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

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

相关文章

OceanBase 内存研究(OceanBase 3.2.4.5)

OceanBase 内存研究(OceanBase 3.2.4.5)

内存结构 从官网的结构图可以看出&#xff0c;一台observer可使用的总内存(memory_limit)包括 系统内存(system_memory) 和 租户内存(sys租户与普通租户) 系统内存 系统内存system_memory 属于 observer 的内部内存&#xff0c;允许其它租户共享使用该内存资源 (root10.0.0.…
阅读更多...
vue2转vue3初步下载pnpm遇到的问题 pnpm : 无法加载文件 D:\nodejs\pnpm.ps1

vue2转vue3初步下载pnpm遇到的问题 pnpm : 无法加载文件 D:\nodejs\pnpm.ps1

安装pnpm npm install -g pnpm pnpm -v 提示&#xff1a; 解决&#xff1a;nvm install 18.18.0 下载最稳定版本的nodejs nvm use 18.18.0 然后注意重新下载删除pnpm npm uninstall -g pnpm npm install -g pnpmlatest 在vscode使用pnpm报错 解决&#xff1a;管理员运行Windo…
阅读更多...
爬虫（没）入门：用 node-crawler 爬取 blog

爬虫（没）入门：用 node-crawler 爬取 blog

起因 前几天想给一个项目加 eslint&#xff0c;记得自己曾经在博客里写过相关内容&#xff0c;所以来搜索。但是发现 csdn 的只能按标题&#xff0c;没办法搜正文&#xff0c;所以我没搜到自己想要的内容。 没办法只能自己又重新折腾了一通 eslint&#xff0c;很烦躁。迁怒于…
阅读更多...
tomcat配置请求的最大参数个数和请求数据大小

tomcat配置请求的最大参数个数和请求数据大小

maxParameterCount"10000" maxPostSize"10485760" maxParameterCount&#xff1a;单个请求最大请求参数个数&#xff1b; maxPostSize&#xff1a;单个请求最大数据大小&#xff0c;1048576010M&#xff1b;
阅读更多...
flutter3-os：基于flutter3.x+dart3+getx手机版os管理系统

flutter3-os：基于flutter3.x+dart3+getx手机版os管理系统

flutter3-os-admin跨平台手机后台OS系统。 原创Flutter3.22Dart3.4Getxfl_chart等技术开发仿ios手机桌面OA管理系统。自研栅格化布局引擎、自定义桌面壁纸、小部件、底部Dock菜单、可拖拽悬浮球等功能。 全新自研栅格化OS菜单布局引擎。 使用技术 编辑器&#xff1a;VScode技术…
阅读更多...
【架构模型】

【架构模型】

一、客户端/服务端模式 二、单击应用模式 单机应用系统是最简单的软件结构&#xff0c;是指运行在一台物理机器上的独立应用程序。
阅读更多...
【大模型】基于Hugging Face调用及微调大模型（1）

【大模型】基于Hugging Face调用及微调大模型（1）

文章目录 一、前言二、Transformer三、Hugging Face3.1 Hugging Face Dataset3. 2 Hugging Face Tokenizer3.3 Hugging Face Transformer3.4 Hugging Face Accelerate 四、基于Hugging Face调用模型4.1 调用示例4.2 调用流程概述4.2.1 Tokenizer4.2.2 模型的加载4.2.3 模型基本…
阅读更多...
spring源码初始学习基础-环境

spring源码初始学习基础-环境

环境&#xff1a;在这里插入代码片 allprojects {repositories {maven { url file:///D:/software/repository} // 本地仓库地址&#xff0c;如果没有依次向下寻找maven { url "https://maven.aliyun.com/repository/public" }mavenLocal()mavenCentral()}buildscri…
阅读更多...
CopilotKit：开源 Copilot 框架，部署应用内 AI 代理，使用 Langchain 自动执行任何任务！

CopilotKit：开源 Copilot 框架，部署应用内 AI 代理，使用 Langchain 自动执行任何任务！

原文链接&#xff1a;&#xff08;更好排版、视频播放、社群交流、最新AI开源项目、AI工具分享都在这个公众号&#xff01;&#xff09; CopilotKit&#xff1a;开源 Copilot 框架&#xff0c;部署应用内 AI 代理&#xff0c;使用 Langchain 自动执行任何任务&#xff01; &am…
阅读更多...
前端工程化工具系列（九）—— mddir(v1.1.1)：自动生成文件目录结构工具

前端工程化工具系列（九）—— mddir(v1.1.1)：自动生成文件目录结构工具

mddir 是一个基于项目目录结构动态生成 Markdown 格式目录结构的工具&#xff0c;方便开发者在文档中展示文件和文件夹的组织结构。 1. 安装 全局安装改工具&#xff0c;方便用于各个项目。 pnpm i -g mddir2. 使用 在想要生成目录接口的项目内打开命令行工具&#xff0c;输…
阅读更多...
RocketMQ教程(一)：RocketMQ的基本概念

RocketMQ教程(一)：RocketMQ的基本概念

RocketMQ是什么？ RocketMQ 是一个分布式消息中间件和流计算平台，由阿里巴巴团队开源并贡献给 Apache 软件基金会，现为 Apache 顶级项目。它主要用于处理大规模数据的传输问题，支持高吞吐量、高可用性和可扩展性的消息发布和订阅服务。RocketMQ 能够确保消息的可靠传输，支持…
阅读更多...
从报名到领证：软考高级【系统分析师】报名考试全攻略

从报名到领证：软考高级【系统分析师】报名考试全攻略

本文共计13156字&#xff0c;预计阅读39分钟。包括七个篇章&#xff1a;报名、准考证打印、备考、考试、成绩查询、证书领取及常见问题。 不想看全文的可以点击目录&#xff0c;找到自己想看的篇章进行阅读。 一、报名篇 报名条件要求&#xff1a; 1.凡遵守中华人民共和国宪…
阅读更多...
R语言探索与分析17-股票题目

R语言探索与分析17-股票题目

Value at Risk&#xff08;VaR&#xff09;是一种统计技术&#xff0c;用于量化投资组合在正常市场条件下可能遭受的最大潜在损失。它是风险管理和金融领域中一个非常重要的概念。VaR通常以货币单位表示&#xff0c;用于估计在给定的置信水平和特定时间范围内&#xff0c;投资组…
阅读更多...
码农危是否到来? AI大模型时代到来程序员能做啥？

码农危是否到来? AI大模型时代到来程序员能做啥？

前言 “马斯克提到人工智能会让工作变得毫无意义&#xff0c;并建议人们可能需要去编写人工智能程序&#xff0c;以避免被AI剥夺就业”&#xff0c;AI大模型的爆发&#xff0c;各种自动化编码应用工具&#xff0c;AI机器人出现&#xff0c;“前有2023年2月份&#xff0c;ChatG…
阅读更多...
基于FPGA的任意点滑动平均（滑动窗长度和数据位宽参数化，例化时参数可设置）

基于FPGA的任意点滑动平均（滑动窗长度和数据位宽参数化，例化时参数可设置）

目录 1.前言2.原理3.举例说明4.Matlab实现5.FPGA实现滑动平均 微信公众号获取更多FPGA相关源码&#xff1a; 1.前言 对于一维信号&#xff0c;我们可以使用类似移动平均滤波&#xff08;Moving Average Filtering&#xff09;实现denoising。Moving Average Filtering 是一种…
阅读更多...
算法金 | 再见！！！KNN

算法金 | 再见！！！KNN

大侠幸会&#xff0c;在下全网同名「算法金」 0 基础转 AI 上岸&#xff0c;多个算法赛 Top 「日更万日&#xff0c;让更多人享受智能乐趣」 KNN算法的工作原理简单直观&#xff0c;易于理解和实现&#xff0c;这使得它在各种应用场景中备受青睐。 我们将深入探讨KNN算法&…
阅读更多...
微服务+分库分表的自增主键ID该如何设计？

微服务+分库分表的自增主键ID该如何设计？

一. 前言 分布式ID 是分布式系统里面非常重要的一个组成部分&#xff0c;那么我们在设计分布式ID的时候&#xff0c;需要考虑什么问题呢&#xff1f; ❓简单结构下是怎么实现 ID 的控制的&#xff1f; 单实例系统 &#xff1a;通过时间戳&#xff0c;系统内自增&#xff0c;上…
阅读更多...
【高校科研前沿】新疆生地所陈亚宁研究员团队在GeoSus发文:在1.5°C和2°C全球升温情景下，中亚地区暴露于极端降水的人口增加

【高校科研前沿】新疆生地所陈亚宁研究员团队在GeoSus发文:在1.5°C和2°C全球升温情景下，中亚地区暴露于极端降水的人口增加

目录 文章简介 1.研究内容 2.相关图件 3.文章引用 文章简介 论文名称&#xff1a;Increased population exposures to extreme precipitation in Central Asia under 1.5 ◦C and 2 ◦C global warming scenarios&#xff08;在1.5C和2C全球变暖情景下&#xff0c;中亚地区…
阅读更多...
flutter LINK : ...fatal error LNK1168: �޷���...

flutter LINK : ...fatal error LNK1168: �޷���...

执行 flutter run -d windows 后报错 LINK : fatal error LNK1168: &#xfffd;޷&#xfffd;&#xfffd;&#xfffd; E:\xiaoli\flutter_project\huapu_update_hardware\build\windows\x64\runner\Debug\huapu_update_hardware.exe &#xfffd;&#xfffd;&#xfffd;…
阅读更多...
gstreamer+mpp调用硬解码播放视频

gstreamer+mpp调用硬解码播放视频

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、cpu解码二、gstreamermpp1.默认已安装2.没安装必要软件 总结 前言 以前一直在MPP上开发硬解码推理&#xff0c;最近想弄一个盒子支持调用mpp硬解码播放视频…
阅读更多...
最新文章

Copyright @ 2022~2023