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

2023-09-20 21:22:49

文章目录

1. 二叉搜索树

1.1 二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

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

在这里插入图片描述

1.2 二叉搜索树的查找

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

1.3 二叉搜索树的插入

插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
在这里插入图片描述

1.4 二叉搜索树的删除

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

a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程
如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点
中，再来处理该结点的删除问题–替换法删除。
在这里插入图片描述

2 二叉搜索树的实现

template<class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;
	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};
template<class K>
struct BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{}
	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->_left;
			else if (cur->_key < key)
				cur = cur->_right;
			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->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else//找到了
			{
				if (cur->_left == nullptr)//左为空
				{
					if (cur == _root)
					{
						_root = _root->_right;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}
				else if (cur->_right == nullptr)//右为空
				{
					if (cur == _root)
					{
						_root = _root->_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(cur->_key, LeftMax->_key);
					if (parent->_left == LeftMax)
					{
						parent->_left = LeftMax->_left;
					}
					else
					{
						parent->_right = LeftMax->_left;
					}
					cur = LeftMax;
				}
				delete cur;
				return true;
			}
		}
		return false;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	void _InOrder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
private:
	Node* _root;
};

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

	t.InOrder();

	t.Erase(4);
	t.InOrder();

	t.Erase(6);
	t.InOrder();

	t.Erase(7);
	t.InOrder();

	t.Erase(3);
	t.InOrder();

	for (auto e : a)
	{
		t.Erase(e);
	}
	t.InOrder();
}

3 二叉搜索树的应用

  1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到
    的值。
    比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
    以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
    在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
  2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方
    式在现实生活中非常常见：
    比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
    文单词与其对应的中文<word, chinese>就构成一种键值对；
    再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出
    现次数就是<word, count>就构成一种键值对。
以下是完整的代码，包括改造二叉搜索树为KV结构、测试二叉搜索树的函数和主函数：

cpp
#include <iostream>  
#include <string>  
  
using namespace std;  
  
template<class K, class V>  
struct BSTNode  
{  
    BSTNode(const K& key = K(), const V& value = V())  
        : _pLeft(nullptr) , _pRight(nullptr), _key(key), _value(value)  
    {}  
    BSTNode<K, V>* _pLeft;  
    BSTNode<K, V>* _pRight;  
    K _key;  
    V _value;  
};  
  
template<class K, class V>  
class BSTree  
{  
public:  
    typedef BSTNode<K, V> Node;  
    typedef Node* PNode;  
public:  
    BSTree(): _pRoot(nullptr){}  
    PNode 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 Insert(const K& key, const V& value)
    {
    	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 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 (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(cur->_key, leftMax->_key);

						if (parent->_left == leftMax)
						{
							parent->_left = leftMax->_left;
						}
						else
						{
							parent->_right = leftMax->_left;
						}

						cur = leftMax;
					}

					delete cur;
					return true;
				}
			}

			return false;
    }  
private:  
    PNode _pRoot;  
};

3.1二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二
叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
在这里插入图片描述
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为： l o g 2 N log_2 N log2​N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为： N 2 \frac{N}{2} 2N​
问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插
入关键码，二叉搜索树的性能都能达到最优？AVL树和红黑树就可以上场了。

更多推荐

OSI七层网络参考模型与数据流通过程

OSI七层网络参考模型文章目录OSI七层网络参考模型1.OSI参考模型初步了解2.OSI参考模型理解3.数据流通的过程1.OSI参考模型初步了解OSI，英文为OpenSystemInterconnect，意为开放式系统互连，国际化标准组织(ISO)指定了OSI模型，这个模型把网络通信的工作定义成7个框架，分别是物理层，

《java并发编程的艺术》读书笔记 1~2章

1.java并发基本概念1.1上下文切换实现原理：通过CPU时间片来实现这个机制。时间片是CPU分配给各个线程的时间，时间片非常短，CPU通过不停的切换线程执行，让我们感觉多个线程是同时执行的。CPU通过时间片分配算法来循环执行任务，当前任务执行一个时间片会切换到下一个任务，并保存上一个任务的状态，下次切换到这个任务时

day44 数据库查询命令

--isnull和isnotnull#1.查询没有上级领导的员工编号，姓名，工资selectempno,ename,salfromempwheremgrisnull;#2.查询emp表中没有奖金（comm）的员工姓名，工资，奖金selectename,sal,commfromempwherecommisnull;#3.

《Clean Code》

整洁代码文章目录一、命名1.1变量1.2函数Rule11.【推荐】先整体后细节1.3类二、格式三、条件语句四、对象和数据结构一、命名以业务为导向命名[operateMaxSaleQtyLogs]>以技术命名[operateMaxSaleQtyLogList]>随意命名[logList]1.1变量Rule1.【推荐】变量

面向组织分析的内容

声明本文是学习GB-T42859-2023航天产品质量问题三个面向分析方法实施要求.而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们1范围本文件规定了航天产品质量问题三个面向分析方法实施的一般要求、程序和分析内容。本文件适用于承担航天产品研制任务的单位对质量问题从产品、流程、组织等角度开展分析和改进

安全模型中的4个P

引言：在安全模型中，经常会碰到PDR,PPDR，IPDRR，CARTA-PPDR等模型，其中的P，是predict？是prevent？还是protect？还是policy呢？一、4P字典意思解释1、predict：动词，预测的意思，tosaythatsomethingwillhappeninthefuture；2、pr

pnpm入门教程

一、概述1、更小使用npm时，依赖每次被不同的项目使用，都会重复安装一次。而在使用pnpm时，依赖会被存储在内容可寻址的存储中。2、更快依赖解析。仓库中没有的依赖都被识别并获取到仓库。目录结构计算。node_modules目录结构是根据依赖计算出来的。链接依赖项。所有以前安装过的依赖项都会直接从仓库中获取并链接到nod

【腾讯云 Cloud Studio 实战训练营】在Cloud Studio上使用React实现学生管理系统

一、前言为了提升办公效率，越来越多的人开始使用云工作站的方法进行“云办公”了，所谓云办公即把传统意义办公场所转移到网络浏览器中，这样做的好处有：实现真正的移动化办公，不再受设备、时间、地点等的束缚，随时随地都能访问云工作站进行办公。支持多人协同，大家都能在同一环境下进行工作，可对同文件进行修改。更能保证数据的安全性，以

Spring高手之路5，Dubbo服务注册与发现（文末送书）

目录一、介绍1、介绍Dubbo服务注册与发现的基本概念和重要性2、阐述Dubbo服务注册与发现的实现方式和应用场景二、Dubbo服务注册与发现的架构设计1、Dubbo服务注册与发现的总体架构设计。2、Dubbo服务提供方的注册与发现设计3、Dubbo服务消费者端的注册与发现设计三、Dubbo服务注册与发现的实现方式1、

使用cpolar配合Plex打造个人媒体站，畅享私人影音娱乐空间

文章目录1.前言2.Plex网站搭建2.1Plex下载和安装2.2Plex网页测试2.3cpolar的安装和注册3.本地网页发布3.1Cpolar云端设置3.2Cpolar本地设置4.公网访问测试5.结语1.前言用手机或者平板电脑看视频，已经算是生活中稀松平常的场景了，特别是各种碎片时间（追剧下饭、地铁上刷剧等等），看

【整理】text2kgbench: 语言模型根据本体生成知识图谱的能力

概述该论文的研究背景是大型语言模型（LLM）和基于本体的知识图谱（KG）在自然语言处理（NLP）任务中的性能提升。过去的方法存在一些问题，该论文提出的方法通过从文本中生成KG并遵循给定的本体，解决了这些问题，并鼓励了新的方法。本文提出了Text2KGBench，一个基准测试，用于评估语言模型根据本体从自然语言文本中生成

热文推荐
  1. 面试官：用Vue3.0 写过组件吗？如果想实现一个 Modal你会怎么设计？

    🎬岸边的风：个人主页🔥个人专栏:《VUE》《javaScript》⛺️生活的理想，就是为了理想的生活!目录一、组件设计二、需求分析三、实现流程目录结构组件内容实现API形式事件处理其他完善一、组件设计组件就是把图形、非图形的各种逻辑均抽象为一个统一的概念（组件）来实现开发的模式现在有一个场景，点击新增与编辑都弹框出

  2. linux文件权限

    借东风七星坛上卧龙登，一夜东风江水腾。不是孔明施巧计，周郎安得逞才能？基本权限文件权限设置：可以使某个用户或者某个组能够对文件进行某些操作权限对象：u===>属主g===>属组o===>其他人----------------基本权限类型r--->read读--->4w--->write写--->2x--->exec执行

  3. Vue2+Vue3

    文章目录Vue快速上手Vue是什么第一个Vue程序插值表达式Vue核心特性：响应式Vue指令v-htmlv-show与v-ifv-else与v-else-ifv-onv-bindv-forv-model指令修饰符计算属性watch侦听器（监视器）watch——简写watch——完整写法Vue生命周期和生命周期的四个阶段

  4. 【Linux学习笔记】权限

    1.普通用户和root用户权限之间的切换2.权限的三个w2.1.什么是权限（what）2.1.1.用户角色2.1.2.文件属性2.2.怎么操作权限呢？（how）2.2.1.ugo+-rwx方案2.2.2.八进制方案2.2.3.文件权限的初始模样2.2.4.进入一个目录，需要什么权限呢？2.3.为什么要有权限呢？（why

  5. 计算机毕业设计 基于SSM+Vue的校园短期闲置资源置换平台的设计与实现 Java实战项目 附源码+文档+视频讲解

    博主介绍：✌从事软件开发10年之余，专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌🍅文末获取源码联系🍅👇🏻精彩专栏推荐订阅👇🏻不然下次找不到哟————————————————计算机毕业设计题目《10

  6. 强化学习从基础到进阶--案例与实践[7.1]：深度确定性策略梯度DDPG算法、双延迟深度确定性策略梯度TD3算法详解项目实战

    【强化学习原理+项目专栏】必看系列：单智能体、多智能体算法原理+项目实战、相关技巧（调参、画图等、趣味项目实现、学术应用项目实现专栏详细介绍：【强化学习原理+项目专栏】必看系列：单智能体、多智能体算法原理+项目实战、相关技巧（调参、画图等、趣味项目实现、学术应用项目实现对于深度强化学习这块规划为：基础单智能算法教学（g

  7. 01-初识HTML

    01-初识HTML学习目标：理解HTML的基本语法掌握排版标签实现标题等效果相对路径和绝对路径媒体标签（图片、音频、视频）超链接一、基础认知了解网页组成和五大浏览器明确Web标准的构成1.1认识网页以下网页有哪些部分组成文字、图片、音频、视频、超链接…那么这个网页背后本质是什么？前端的代码是通过什么软件转换成用户眼中的

  8. 高精度地图定位在高速公路自动驾驶系统中的应用

    【摘要】自动驾驶已经成为全球汽车产业的战略发展方向，其中L3级高速公路自动驾驶是最有可能率先落地的自动驾驶系统，高精度地图和定位系统是自动驾驶系统的关键一部分，近年来发展迅速，已经达到可量产状态。文章首先分析了自动驾驶和高精度地图定位的发展现状，然后，对高精度地图和定位系统在自动驾驶系统的地理围栏判定和感知冗余方面的应

  9. Linux MQTT智能家居（MQTT框架）

    文章目录前言一、MQTT通信框架二、心跳包三、项目中使用到的软件四、MQTT中服务器和客户端建立连接的步骤总结前言本篇文章将会讲解MQTT的框架，我们这个项目使用到的MQTT源码库来自于一位大佬编写。大佬博客主页：主页一、MQTT通信框架MQTT（MessageQueuingTelemetryTransport）是一种