二叉搜索树(二叉排序树,二叉查找树)(附图详解+代码实现+应用分析)

最近学习了有关搜索二叉树的相关知识,在此特意将该知识进行总结分享,希望对大家有所帮助。

文章目录

  • 一.二叉搜索树
    • 1.1二叉搜索树的概念
    • 1.2二叉搜索树的操作(含思路分析+代码实现)
        • 1.2.1二叉搜索树的查找(递归实现看最后总代码)
        • 1.2.2二叉搜索树的插入(递归实现看最后总代码)
        • 1.2.3二叉搜索树的删除(递归实现看最后总代码)
        • 总代码(含递归实现):
  • 二. 二叉搜索树的应用
  • 三.二叉搜索树的性能分析

一.二叉搜索树

1.1二叉搜索树的概念

二叉搜索树又叫二叉排序树,二叉查找树,可以为空,也可以不为空,具体有以下的特性:

  1. 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  2. 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  3. 它的左右子树也分别为二叉搜索树

在这里插入图片描述

1.2二叉搜索树的操作(含思路分析+代码实现)

一个基本的二叉搜索树需要有哪些函数(接口)呢?

1.2.1二叉搜索树的查找(递归实现看最后总代码)

基于二叉搜索树的结构的特点:左节点小于根,右节点大于根
查找的思路分析:

a、从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。
b、最多查找高度次,走到到空,还没找到,这个值不存在。

图解:
在这里插入图片描述

代码实现:

	bool Find(const K& key)       //key为寻找关键字
	{
		if (_root == nullptr)    //如果为空,直接返回
		{
			return false;
		}
		else                      
		{
			Node* cur = _root;         //用cur迭代寻找
			while (cur)
			{
				if (key > cur->_key)      //如果key比根节点的值大,则去右子树寻找
				{
					cur = cur->_right;
				}
				else if(key < cur->_key)   //如果key比根节点的值小,则去左子树寻找
				{
					cur = cur->_left;
				}
				else
				{
					return true;       //相等,返回true
				}
			} 
			return false;          //出循环,还没找到,返回false
		}
	}
1.2.2二叉搜索树的插入(递归实现看最后总代码)

插入思路分析:

a. 树为空,则直接新增节点,赋值给root指针
b. 树不空,按二叉搜索树性质查找插入位置,插入新节点

图解:
在这里插入图片描述

代码实现:

	bool insert(const K& key)
	{
		if (_root == nullptr)    //如果为空树,直接插入
		{
			Node* newNode = new Node(key);    //new一个节点
			_root = newNode;                   //链接

			return true;      //插入成功,返回true
		}
		else
		{
			Node* parent = nullptr;     //因为要链接,所以需要记录父亲
			Node* cur = _root;   
			while (cur)                   //while循环和find函数类似,目的找到合适位置插入
			{
				if (key > cur->_key)
				{
					parent = cur;    //记录父节点
					cur = cur->_right;
				}
				else if(key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;    //搜索二叉树里面的值不能重复,如果已经存在,则返回false
				}
			}
			//cur空,结束循环,代表找到位置了
			Node* newNode = new Node(key);      //new节点
			if (key < parent->_key)            
				parent->_left = newNode;
			if (key > parent->_key)          //判断是链接到父亲的左还是右
				parent->_right = newNode;

			return true;
		}
	}
1.2.3二叉搜索树的删除(递归实现看最后总代码)

首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情况:

a. 要删除的结点无孩子结点 //直接删除
b. 要删除的结点只有左孩子结点 //托孤
c. 要删除的结点只有右孩子结点 //托孤
d. 要删除的结点有左、右孩子结点 //替换法删除

看起来有待删除节点有4中情况,实际情况a可以与情况b或者c合并起来,因此真正的删除过程如下:

情况b:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d:在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题–替换法删除

托孤发删除的原理:
假设我们要删除【图一】的22,它只有一个孩子,就可以使用托孤的方法,直接让父节点(15)指向它的孩子(17);
该方法也可以在删除没有孩子的节点上使用(将它看作有一个为NULL的孩子即可),例如下【图二】,假设删除17;
在这里插入图片描述

在这里插入图片描述

替换法删除的原理:
方法作用于有两个孩子的节点:

a,找到该节点左子树的最右节点(即左子树最大的节点)或则右子树的最左节点(即右子树最小值);
b,然后将待删除节点的值与找到的最大(或最小)节点的值进行交换,转化为删除找到的这个节点;
c,最后用上面的托孤的方法删除该节点

在这里插入图片描述

代码实现:

	bool Erase(const K& key)
	{
		if (_root == nullptr)     //如果树为空,直接返回
			return false;
		else                     //树不为空
		{
			Node* parent = _root;
			Node* cur = _root;       
			while (cur)                 //while循环,先找到待删除节点以及记录它父节点
			{                           //该循环体与find和insert类似
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) 
				{
					parent = cur;
					cur = cur->_left;
				}
				else                             //找到该节点了,开始删除
				{
				    //1.只有一个孩子或则没有孩子
					Node* del = cur;                    //保存要删除的这个节点,防止等下托孤后该节点找不到
					if (!(cur->_left && cur->_right))    //两个孩子都存在的逻反就是有一个孩子或则没有孩子
					{
						if (cur == _root)       //这里,判断如果该节点是头节点,直接将头节点置空,返回
						{
							_root = nullptr;         
						}
						if (parent->_left == cur)     //该删除节点为父节点的左子树,则将它的孩子连接到它父节点的左子树上
						{
							if (cur->_left)           //判断孩子是待删除节点的哪个孩子
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_left = cur->_right;
							}
							return true;
						}
						else                        //和上面一样
						{
							if (cur->_left)
							{
								parent->_right = cur->_left;
							}
							else
							{
								parent->_right = cur->_right;
							}
							return true;
						}
					}
					//2.待删除节点有两个孩子
					else                            //这里实现的是替换法中找右子树中最小的节点
					{
						Node* rightMinparent = cur;        //记录最小节点的父亲,因为等下需要托孤
						Node* rightMin = cur->_right;      //记录最小节点
						while (rightMin->_left)
						{
							rightMinparent = rightMin;
							rightMin = rightMin->_left;
						}
						//到这里说明中找到了右树的最小节点
						swap(rightMin->_key, cur->_key);    //交换最小节点与待删除节点的值,转换为删除这个最小节点
						if (rightMinparent->_left==rightMin)     //下面的逻辑与上面的托孤一样
						{
							rightMinparent->_left = rightMin->_right;
						}
						else
						{
							rightMinparent->_right = rightMin->_right;
						}
						delete rightMin;                      //最后删除
					}
					return true;
				}
			}
			return false;
		}
	}
总代码(含递归实现):
#pragma once
#include<iostream>

using namespace std;

template<class K>
struct Binary_Serach_TreeNode
{
	typedef Binary_Serach_TreeNode<K> Node;
	Node* _left;
	Node* _right;
	K _key;

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

};

template<class K>
class B_S_Tree
{
public:
	typedef Binary_Serach_TreeNode<K> Node;
	//B_S_Tree() = default;    //强制生成默认构造
	B_S_Tree()
		:_root(nullptr)
	{}

	B_S_Tree(B_S_Tree<K>& bst)
	{
		_root = copy(bst._root);
	}
	Node* copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newroot = new Node(root->_key);
		newroot->_left = copy(root->_left);
		newroot->_right = copy(root->_right);

		return newroot;
	}
	B_S_Tree<K>& operator=(B_S_Tree<K> bst)
	{
		std::swap(bst._root, _root);
		return *this;
	}
	bool insert(const K& key)
	{
		if (_root == nullptr)    //如果为空树,直接插入
		{
			Node* newNode = new Node(key);    //new一个节点
			_root = newNode;                   //链接

			return true;      //插入成功,返回true
		}
		else
		{
			Node* parent = nullptr;     //因为要链接,所以需要记录父亲
			Node* cur = _root;   
			while (cur)                   //while循环和find函数类似,目的找到合适位置插入
			{
				if (key > cur->_key)
				{
					parent = cur;    //记录父节点
					cur = cur->_right;
				}
				else if(key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;    //搜索二叉树里面的值不能重复,如果已经存在,则返回false
				}
			}
			//cur空,结束循环,代表找到位置了
			Node* newNode = new Node(key);      //new节点
			if (key < parent->_key)            
				parent->_left = newNode;
			if (key > parent->_key)          //判断是链接到父亲的左还是右
				parent->_right = newNode;

			return true;
		}
	}

	bool Erase(const K& key)
	{
		if (_root == nullptr)     //如果树为空,直接返回
			return false;
		else                     //树不为空
		{
			Node* parent = _root;
			Node* cur = _root;       
			while (cur)                 //while循环,先找到待删除节点以及记录它父节点
			{                           //该循环体与find和insert类似
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) 
				{
					parent = cur;
					cur = cur->_left;
				}
				else                             //找到该节点了,开始删除
				{
				    //1.只有一个孩子或则没有孩子
					Node* del = cur;                    //保存要删除的这个节点,防止等下托孤后该节点找不到
					if (!(cur->_left && cur->_right))    //两个孩子都存在的逻反就是有一个孩子或则没有孩子
					{
						if (cur == _root)       //这里,判断如果该节点是头节点,直接将头节点置空,返回
						{
							_root = nullptr;         
						}
						if (parent->_left == cur)     //该删除节点为父节点的左子树,则将它的孩子连接到它父节点的左子树上
						{
							if (cur->_left)           //判断孩子是待删除节点的哪个孩子
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_left = cur->_right;
							}
							return true;
						}
						else                        //和上面一样
						{
							if (cur->_left)
							{
								parent->_right = cur->_left;
							}
							else
							{
								parent->_right = cur->_right;
							}
							return true;
						}
					}
					//2.待删除节点有两个孩子
					else                            //这里实现的是替换法中找右子树中最小的节点
					{
						Node* rightMinparent = cur;        //记录最小节点的父亲,因为等下需要托孤
						Node* rightMin = cur->_right;      //记录最小节点
						while (rightMin->_left)
						{
							rightMinparent = rightMin;
							rightMin = rightMin->_left;
						}
						//到这里说明中找到了右树的最小节点
						swap(rightMin->_key, cur->_key);    //交换最小节点与待删除节点的值,转换为删除这个最小节点
						if (rightMinparent->_left==rightMin)     //下面的逻辑与上面的托孤一样
						{
							rightMinparent->_left = rightMin->_right;
						}
						else
						{
							rightMinparent->_right = rightMin->_right;
						}
						delete rightMin;                      //最后删除
					}
					return true;
				}
			}
			return false;
		}
	}

	bool Find(const K& key)       //key为寻找关键字
	{
		if (_root == nullptr)    //如果为空,直接返回
		{
			return false;
		}
		else                      
		{
			Node* cur = _root;         //用cur迭代寻找
			while (cur)
			{
				if (key > cur->_key)      //如果key比根节点的值大,则去右子树寻找
				{
					cur = cur->_right;
				}
				else if(key < cur->_key)   //如果key比根节点的值小,则去左子树寻找
				{
					cur = cur->_left;
				}
				else
				{
					return true;       //相等,返回true
				}
			} 
			return false;          //出循环,还没找到,返回false
		}
	}
	bool insertR(const K& key)
	{
		return _inserR(_root, key);
	}
	bool  FindR(const K& key)
	{
		return _FindR(_root,key);
	}
	bool  EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}

	void OrdPrint()
	{
		_OrdPrint(_root);
		cout << endl;
	}

	~B_S_Tree()
	{
		//_Destory(_root);
	}
private:
	void _OrdPrint(Node* root)
	{
		if (root == nullptr)
			return;

		_OrdPrint(root->_left);
		cout << root->_key <<' ';
		_OrdPrint(root->_right);
	}
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (key < root->_key)
			return _FindR(root->_left, key);
		else if (key < root->_key)
			return _FindR(root->_right, key);
		else
			return true;
	}
	bool _inserR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (key < root->_key)
			return _inserR(root->_left, key);
		else if (key > root->_key)
			return _inserR(root->_right, key);
		else
			return false;
	}
	bool _EraseR(Node*& root,const K&  key)
	{
		if (root == nullptr)
			return false;
		if (key < root->_key)
			_FindR(root->_left, key);
		else if (key < root->_key)
			_FindR(root->_right, key);
		else
		{
			Node* del = root;
			if (root->_left==nullptr)
				root = root->_right;
			else if(root->_right==nullptr)
				root = root->_left;
			else
			{
				Node* rightMinparent = root;
				Node* rightMin = root->_right;
				while (rightMin->_left)
				{
					rightMinparent = rightMin;
					rightMin = rightMin->_left;
				}
				swap(root->_key, rightMin->_key);
				return _EraseR(root->_right, key);
			}
			delete del;
			return true;

		}
	}
	void _destory(Node* root)
	{
		if (root == nullptr)
			return;
		else
		{
			_destory(root->_left);
			_destory(root->_right);
			delete root;
		}
	}

private:
	Node* _root;
};

二. 二叉搜索树的应用

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

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

三.二叉搜索树的性能分析

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。

最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树)【如图左】,其平均比较次数为:log_2 N
最差情况下,二叉搜索树退化为单支树(或者类似单支)【如图右】,其平均比较次数为:N

在这里插入图片描述
本章完~看完觉得对你有用就点个赞吧!

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

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

相关文章

如何在Ubuntu系统使用Docker搭建MongoDB结合内网穿透实现公网连接

文章目录 前言1. 安装Docker2. 使用Docker拉取MongoDB镜像3. 创建并启动MongoDB容器4. 本地连接测试5. 公网远程访问本地MongoDB容器5.1 内网穿透工具安装5.2 创建远程连接公网地址5.3 使用固定TCP地址远程访问 前言 本文主要介绍如何在Linux Ubuntu系统使用Docker快速部署Mon…

城市排涝与海绵城市规划设计中的水文水动力模拟技术应用

随着计算机的广泛应用和各类模型软件的发展&#xff0c;将排水系统模型作为城市洪灾评价与防治的技术手段已经成为防洪防灾的重要技术途径。本次培训将聚焦于综合利用GIS及CAD等工具高效地进行大规模城市排水系统水力模型的建立&#xff0c;利用SWMM实现排水系统水力模拟。讲解…

如何本地部署Imagewheel并实现无公网IP远程连接打造个人云图床

文章目录 1.前言2. Imagewheel网站搭建2.1. Imagewheel下载和安装2.2. Imagewheel网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar临时数据隧道3.2.Cpolar稳定隧道&#xff08;云端设置&#xff09;3.3.Cpolar稳定隧道&#xff08;本地设置&#xff09; 4.公网访问测…

Linux文件系列:磁盘,文件系统,软硬链接

Linux文件系列:磁盘,文件系统,软硬链接 一.磁盘相关知识1.磁盘机械构成2.磁盘物理存储3.磁盘逻辑存储1.LBA地址2.磁盘的分区和分组 二.文件系统和inode1.inode结构体2.文件系统1.Super Block(超级块)2.Group Descriptor Table(块组描述表GDT)3.inode Table4.Data Blocks5.Block…

vue3+threejs新手从零开发卡牌游戏(八):关联卡组和手牌区、添加初始化卡组和初始化手牌逻辑

首先我们优化下之前的代码&#xff0c;先加载游戏资源&#xff0c;然后再初始化场景&#xff0c;由于目前只有一个font字体需要加载&#xff0c;所以我们将之前game/deck/p1.vue中的font相关代码迁移到game/index.vue下&#xff0c;同时使用async和await处理异步加载&#xff0…

基于Scapy国内城市空气质量数据采集系统设计与实现

代码和完整的报告在文章最后 城市空气质量数据采集系统设计与实现 &#x1f3d9;️ 研究背景 &#x1f32c;️ 城市化与环境挑战&#xff1a;随着城市化进程的加快&#xff0c;环境污染问题&#xff0c;尤其是空气质量问题&#xff0c;已成为公众关注的焦点。数据监测的重要性…

Windows安装配置国产达梦数据库、配置Python接口

文章目录 前言1.下载安装达梦数据库2.配置达梦环境变量3.安装Microsoft Visual C 14.04.安装达梦Python接口dmpython5.测试验证 总结 前言 达梦数据库&#xff08;Dameng Database&#xff09;是由武汉达梦数据库股份有限公司开发的一款高性能的关系型数据库管理系统。该数据库…

关于短群签名论文阅读

参考文献为2004年发表的Short Group Signatures 什么群签名&#xff1f; 群签名大致就是由一组用户组成一个群&#xff0c;其中用户对某条消息的签名&#xff0c;改签名不会揭示是哪一个用户签署的&#xff0c;签名只能表明该消息确实是来自该群的签名。对于群还有一个群管理者…

蓝桥杯算法 - DP

上一篇&#xff1a;[[蓝桥杯算法-排序、递归、全排列]] 动态规划&#xff08;dp&#xff09; dp即动态规划&#xff0c;常用于&#xff1a;数学&#xff0c;计算机科学&#xff0c;管理学&#xff0c;经济和生物信息学。 dp在生活中也很常见&#xff0c;如&#xff1a;你今天…

【随笔】oh-my-posh(Windows power shell为例)

Oh My Posh 是一个适用于任何 shell 的自定义提示引擎&#xff0c;能够使用函数或变量调整提示字符串。 文章目录 一、安装oh-my-posh二、安装Nerd 字体三、oh-my-posh 初始化四、更换主题 一、安装oh-my-posh GitHub repo&#xff1a;https://github.com/JanDeDobbeleer/oh-m…

情感视频素材怎么来的?(情感语录的视频素材在哪里找)

很多小伙伴觉得情感类型的短视频账号用户多&#xff0c;都想要进入分一杯羹&#xff0c;那么这些创作素材去哪里找呢&#xff0c;下面分享几个非常使用的找情感短视频素材的办法。 1&#xff0c;蛙学网 说到情感视频素材的短视频&#xff0c;作为一个专业的短视频素材网站&am…

2024年云服务器ECS价格表出炉——腾讯云

腾讯云服务器多少钱一年&#xff1f;61元一年起。2024年最新腾讯云服务器优惠价格表&#xff0c;腾讯云轻量2核2G3M服务器61元一年、2核2G4M服务器99元一年可买三年、2核4G5M服务器165元一年、3年756元、轻量4核8M12M服务器646元15个月、4核16G10M配置32元1个月、312元一年、8核…

nodeJs中实现连表查询

nodeJs中实现连表查询 router.post(/getOrder, async function(req, res, next) {let userId req.body.phone;let sql select * from orders where userId?;let orders await new Promise((resolve, reject) > {connection.query(sql, [userId], function(error, resul…

一分钟在Solana链创建代币教程

只需要 1 分钟就可以创建自己的SOLANA代币 1、连接Solana钱包2、填写代币信息创建3、创建成功 Solana 是一个基于区块链技术的高性能、去中心化的智能合约平台&#xff0c;旨在为开发者提供高度可扩展和低成本的区块链基础设施。通过其创新的共识机制和高吞吐量的网络架构&…

注册中国商标的大致流程

在当今竞争激烈的商业环境中&#xff0c;商标作为企业形象和品牌标识的重要载体&#xff0c;其保护和推广至关重要。注册中国商标是拓展中国市场的关键步骤 注册中国商标需要以下基本资料&#xff1a; 商标图样&#xff1a;须清晰、完整地展示商标图案和文字内容&#xff1b;商…

MQ消息队列从入门到精通速成

文章目录 1.初识MQ1.1.同步和异步通讯1.1.1.同步通讯1.1.2.异步通讯 1.2.技术对比&#xff1a; 2.快速入门2.1.安装RabbitMQ2.2.RabbitMQ消息模型2.3.导入Demo工程2.4.入门案例2.4.1.publisher实现2.4.2.consumer实现 2.5.总结 3.SpringAMQP3.1.Basic Queue 简单队列模型3.1.1.…

大模型日报|今日必读的6篇大模型论文

大家好&#xff0c;今日必读的大模型论文来啦&#xff01; 1.英伟达提出LATTE3D&#xff1a;更快、更好的“文生3D”方法 近来&#xff0c;由文本到 3D 生成的方法可以生成令人印象深刻的 3D 效果&#xff0c;但这个过程需要耗时的优化过程&#xff0c;每个提示&#xff08;p…

AI之Suno:Suno V3的简介、安装和使用方法、案例应用之详细攻略

AI之Suno&#xff1a;Suno V3的简介、安装和使用方法、案例应用之详细攻略 目录 Suno AI的简介 1、特点与改进&#xff1a; Suno AI的安装和使用方法 1、第一步&#xff0c;让国产大模型—ChatGLM4帮我写一个提示词 2、第二步&#xff0c;将提示词交给Suno v3&#xff0c;…

TikTok vs Instagram!哪个广告形式更适合你

近几年&#xff0c;TikTok以短视频和创新性吸引不少年轻受众&#xff0c;在广告方面也提供挑战赛、创意滤镜和名人合作等多种方式&#xff0c;自2019年起迅速增长&#xff0c;成为Instagram的强劲对手&#xff0c;连续三年下载量居首。而Instagram则拥有十多年历史和庞大用户基…

人工智能(Educoder)-- 搜索技术 -- 盲目式搜索

第1关&#xff1a;盲目搜索之宽度优先搜索算法 任务描述 本关任务&#xff1a;给定迷宫地图以及在迷宫中的起始位置&#xff0c;利用宽度优先搜索算法求解走出迷宫的最短路径长度&#xff0c;走出迷宫意味着达到迷宫地图的边界&#xff08;所有位置下标0开始&#xff09;。 …