数据结构---二叉搜索树

2023-09-17 17:36:43

二叉搜索树

二叉搜索树

什么是二叉搜索树？

二叉搜索树(Binary Search Tree 简称BST)又称二叉排序树，是一种二叉树的特殊形式，它在每个节点上存储的键值满足以下性质：

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

根据这个性质，我们可以利用二叉搜索树进行高效的插入，删除和搜索操作。

在这里插入图片描述

二叉搜索树的操作

查找

  • 从根节点开始比较，如果比根节点大则往右查找，反之往左查找。
  • 最多查找高度次，走到空，还没找到，这个值不存在。

上面的图，比如果要查找4.

4 < 8，往左走，找到3，4大于3，往右走，找到6，6大于4，往左走，找到4，4 == 4，查找成功。

重复上面的操作，直到走到4，4小于5，往右走，为nullptr，不存在这个值，返回false。

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

插入

  • 树为空，则直接新增节点，赋值给root指针
  • 树非空，按二叉搜索树性质查找插入位置，插入新节点。
bool Insert(const K& key)
{
	if (_root == nullptr)// 树为空
	{
		_root = new Node(key);
		return true;
	}

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

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

	return true;
}

如果要插入的值(val)比当前节点的key大，则往右子树移动；反之往左子树移动，直到找到合适的插入位置。

在找到插入位置的时候，不要直接 cur = new Node(val),这样创建的是临时变量，出了作用域会销毁，可以用一个临时变量(parent)记录查找过程中cur的上一个位置，在找到合适的位置的时候，与parent节点的key进行比较之后，在进行链接。

删除

删除有点麻烦，

在这里插入图片描述

看这棵树，把7删了，很简单，delete了就行了，把14给删了呢？右子树的所有节点一定大于根节点，把13链接在10的右子树即可，就算13下面还有子树，也不会导致这个树混乱。那么删3呢？3有两个孩子，这个时候可以找人把3给替代了，从左子树找最大的节点，或者找右子树的最小节点完成替代。

删除分三种情况

  1. 没有孩子
  2. 一个孩子
  3. 两个孩子 (找左子树的最大节点 or 右子树的最小节点)

首先要找到要删除节点的位置(cur)，但光找到一个节点的位置不够，还要找到当前节点的父节点(parent)。如果说cur的左子树为空，并且要删除的节点为根节点。

在这里插入图片描述

也就是当前cur位于8的位置，此时要删除，把根节点移动到cur的右子树位置即可。

若要删的不是根节点。

在这里插入图片描述

此时cur=6，parent=3，要先判断cur与parent的关系，然后直接将parent与cur的子树链接在一起即可。这是要删除节点的左子树为空的情况，右子树为空与这个一样。

若要删除的节点有两个孩子。

在这里插入图片描述

要先找到左子树中最大的节点(leftMax)，将根节点的key与leftMax的key交换。在找leftMax的过程中记录下来其父节点(parent)，判断parent和leftMax的关系。最后将parent与leftMax的左右节点(都为空)链接一下即可。

当然还有一种特殊情况。

在这里插入图片描述

这里要删除8，而3就是左子树中最大的节点。所以这种情况下的parent初始值不能设为nullptr，而是初始化为cur。leftMax还是初始化为cur->left

		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 (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}
				}
				else
				{}
				delete cur;
				return true;
			}
		}

源代码

非递归版

#pragma once


template <class K>
class BSTreeNode
{
public:

	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

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

	
};


template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{}

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

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

		return true;
	}

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

	bool erase(const K& key)
	{
		Node* parent = _root;
		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 (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}
				}
				else
				{
					Node* parent = cur;					
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}
					swap(leftMax->_key, _root->_key);
					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_right;
					}

					cur = leftMax;
				}
				delete cur;
				return true;
			}
		}
		return false;
	}

	void InOrder()
	{
		_InOrder(_root);
	}

private:

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

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

	Node* _root;
};

递归版

#pragma once


template <class K>
class BSTreeNode
{
public:

	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

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



};


template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{}

	bool Insert(const K& key)
	{
		return _Insert(_root, key);
	}

	bool Find(const K& key)
	{
		return _Find(_root, key);
	}

	bool erase(const K& key)
	{
		return _erase(_root, key);
	}

	void InOrder()
	{
		_InOrder(_root);
	}

private:

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

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

	bool _erase(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_key > key)
		{
			return _erase(root->_left,key);
		}
		else if (root->_key < key)
		{
			return _erase(root->_right,key);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* leftMax = root->_left;

				while (leftMax->_right)
				{
					leftMax = leftMax->_right;
				}

				swap(root->_key, leftMax->_key);

				return _erase(root->_left, key);
			}

			delete del;

			return true;
		}

		return false;
	}

	bool _Insert(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (root->_key > key)
		{
			return _Insert(root->_left,key);
		}
		else if (root->_key < key)
		{
			return _Insert(root->_right,key);
		}
		else
		{
			return false;
		}
	}

	bool _Find(Node* root, const K& key)
	{
		if (root == nullptr) {
			return false;
		}

		if (root->_key > key)
		{
			return _Find(root->_left);
		}
		else if (root->_key < key)
		{
			return _Find(root->_right);
		}
		else
		{
			return true;
		}
	}

	Node* _root;
};
更多推荐

陕西省高级工程师职称评审条件

一.评审范围全省范围具有合法生产，经营手续的中小企业局和非公有制经济从事工程师工作专业技术人员和高技能人员，均可申报当年达到法定退休或已办退休的人员，不大参加职称评审。评审专业领域；机械，材料，冶金，电气，电子，信息通信，仪器仪表，能源动力，控制工程，计算机，自动化，人工智能，广播电视，建设，土木，水利，测绘，化工，地

GAN入门｜第四篇：生成手势图像｜可控制生成

🍨本文为🔗365天深度学习训练营中的学习记录博客🏡我的环境：语言环境：Python3.10.11编译器：JupyterNotebook深度学习框架：Pytorch2.0.1+cu118显卡（GPU）：NVIDIAGeForceRTX4070👉考虑到大家算力有限，这里为大家提供我已经训练好生成器模型，大家可自行下

前端之webpck的优化

一、webpack的打包流程/webpack的机制/原理/webpack是怎么打包的1webpack是根据运行的指令来决定一个基本的业务流程2如果是build就是执行打包，如果是配合了devServer就是就行本地化的调试。两者其实在本质上没有太大区别，只是devServer会运行一个node服务器来进行本地化调试，打

构建工具Webpack简介

一、构建工具当我们习惯了Node中使用ES模块化编写代码以后，用原生的HTML、CSS、JS这些东西会感觉到各种不便。比如：不能放心的使用模块化规范（浏览器兼容性问题）、即使可以使用模块化规范也会面临模块过多时的加载问题。这时候我们就希望有一个工具能对代码进行打包，将多个模块打包成一个文件。这样一来即解决了兼容性问题，

pdf文件太大如何处理？教你pdf压缩简单方法

PDF文件过大，是很多人在使用PDF文件时都遇到过的一个常见问题，过大的PDF文件不仅会占用大量的存储空间，还会影响文件传输和处理效率，下面给大家总结了几个方法，帮助大家解决PDF文件过大的问题。方法一：嗨格式压缩大师这是一款专业的文件压缩工具，支持多种文件格式的压缩，包括PDF文件，它具有简单易用的界面，可以帮助用户

爬虫介绍及举例

爬虫（Webcrawler）指的是一种自动化程序，可以通过互联网上的URL，按照一定的规则，自动地抓取目标网站的数据，包括文字、图片、视频等，然后将这些数据进行处理、分析、存储或展示。举例来说，爬虫可以用于搜索引擎的抓取和索引，比如Google、百度等。当用户输入关键字进行搜索时，搜索引擎便会调用爬虫程序到网络上抓取相

Ebay易贝商品详情数据接口

易贝商品详情数据接口可以用于获取易贝商品详情信息，包括商品链接、状态、标题、简介、分类、商品图片、销量、价格等。获取易贝商品详情数据的接口是item_get，其请求参数为num_iid（EBAY商品ID），通过传入该参数可以获取商品详情数。易贝商品详情数据接口的具体使用方法如下：注册并获取API密钥。通过调用相应的AP

Docker Compose

文章目录简介compose文件一、文件简介二、version三、services1.build:2.image3.container_name4.ports5.command6.depends_on7.deploy8.networks9.volumes四、networks1.name2.driver3.attachab

加速老化测试目的是什么？

加速老化测试使用加速应力的组合来暴露产品设计和制造中的产品缺陷。这有助于提高产品可靠性并减少现场故障和保修费用。加速老化测试在环境室中进行，高温加速有效时间，通常与所有振动台结合使用，产生全轴振动。加速老化测试可分为高加速寿命测试（HALT）和高加速应力筛选（HASS）。这两种技术都使用远远超出产品正常工作条件的应力，

IT隔离电源系统在医院低压配电箱中的应用

【摘要】参考国外及国际对医疗领域的相应标准，结合我国有关的规范%标准，对手术室等处的供配电系统作出了探讨；论述了ＩＴ配电系统在医院的应用范围；分析了ＩＴ系统接地故障的特点；提出了医院手术室ＩＴ电源系统的基本配置。【关键词】手术室配电系统；故障；绝缘监视；漏电198.2138.07290引言*近，本院就北部分院的两百多个

mybatis动态sql&choose&foreach&sql 及include & sql中的特殊字符&后台分页实现& 数据版本号处理并发问题

1.动态sql简述mybatis的动态sql语句是基于OGNL表达式的。可以方便的在sql语句中实现某些逻辑.总体说来mybatis动态SQL语句主要有以下几类:if语句(简单的条件判断)choose(when,otherwize),相当于java语言中的switch,与jstl中的choose很类似trim(对包含的

热文推荐
  1. 数据结构--7.1散列表（哈希表）查找

    散列表查找我们要在a[]中查找key关键字的记录：——顺序表查找：挨个儿查找——有序表查找：二分法查找——散列表查找记录的存储位置=f（关键字）散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。这里我们把这种对应关系f称为散列函数，又成为哈希（Hash

  2. EM算法和VAE的学习笔记

    文章目录摘要EM算法流程EM算法对GMM的参数估计EM算法的证明EM算法的另一种理解VAE参考文献摘要这是我学习EM算法（Expectation-MaximizationAlgorithm）和VAE（VariationalAuto-Encoder）的学习笔记，首先总结了EM算法流程，然后举了一个例子，用EM算法对GMM

  3. 【karle 笔记】QQ机器人jdk17版本下载和安装

    这里写自定义目录标题下载地址安装JDK：安装JRE验证安装成功下载地址https://download.oracle.com/java/17/latest/jdk-17_windows-x64_bin.exe下载后，是一个exe文件，傻瓜式安装即可安装JDK：直接用安装包安装，默认安装路径在：C:\ProgramFil

  4. ChatGPT技术原理

    目录一、Tokenization二、Transformer模型三、预训练四、微调五、Beamsearch总结自从OpenAI的ChatGPT在2022年底横空出世以来，这款大型语言模型在各种任务中都展现了惊人的性能，包括问答、对话、文本生成等。ChatGPT以其卓越的性能和高效的处理能力，引领了自然语言处理（NLP）领

  5. vue/react/node项目通过eslint检查语法规范

    首先我们打开终端全局安装依赖npminstall-geslint然后以管理员身份运行项目终端输入eslint--init然后这里在初始化时会问我们想如何使用它?分别对应仅检查语法检查语法并发现问题检查语法、发现问题并强制执行代码样式这里建议第二种第三种肯定是不行的然后问我们您的项目使用哪种类型的模块?JavaScrip

  6. 日主题RiPro主题高端美化/设计素材软件下载站专用子主题/美化包源码（升级版/免拓展）

    主题简介日主题RiPro主题高端美化/设计素材软件下载站专用子主题/美化包源码，这个子主题美化包无授权无暗链，不用再修改原主题代码，在用这个本美化包前要先下载最新ripro主题，本子主题有版本要求，仅支持RiPro8.0以上版本，建议使用官方正版主题。更新记录：美化网站整站主色调颜色，优化代码结构，更适合SEO新增菜单

  7. 文件包含漏洞

    1.文件包含原理程序在开发的时候，未对包含的文件进行严格的过滤，攻击者可以构造自己的图片木马当作php执行2.文件包含分类本地包含不需要条件，只要有程序代码漏洞，默认条件就可以包含漏洞远程包含需要allow_url_include=on（开启远程包含功能）、magic_quotes_gpc=off（魔术符号关闭）htt

  8. Flutter与Native通信原理剖析与实践

    通信原理我们分几种场景来介绍Flutter和Native之间的通信。Native发送数据给FlutterFlutter发送数据给NativeFlutter发送数据给Native，然后Native回传数据给FlutterFlutter与Native通信机制在讲解Flutter与Native之间是如何传递数据之前，我们先了

  9. UE4 C++ 使用第三方库（动态库） 详解

    目录1代码共享的方式2使用三方库2.1准备一个动态库（包含.h;.lib;.dll）2.2创建一个UEC++工程2.3配置三方库1代码共享的方式在使用三方库之前，先介绍一下三方库的由来，以及为什么需要三方库。就从程序员共享代码成果开始讲述。1）三种共享方式：代码分发也就是代码共享的方式有三种：源码、动态库、静态库。源码