二叉搜索树(Binary_Search_Tree)

文章目录

  • 二叉搜索树概念
  • 二叉搜索树的操作
    • 查找
    • 插入
    • 删除
  • 二叉搜索树的应用
  • 二叉搜索树的实现
    • K模型
    • KV模型
  • 二叉搜索树的性能分析

二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
它的左右子树也分别为二叉搜索树。
如：
在这里插入图片描述

二叉搜索树的操作

查找

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

插入

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

删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回。
如果存在，可以分为下面三种情况：
1.删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
2.删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
3.在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点
中，再来处理该结点的删除问题–替换法删除（与堆中删除数据类似）

二叉搜索树的应用

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

二叉搜索树的实现

K模型

template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _l;
	BSTreeNode<K>* _r;
	K _k;

	BSTreeNode(const K& k)
		:_l(nullptr)
		, _r(nullptr)
		, _k(k)
	{}
};

首先定义一个二叉搜索树K模型的结构体。同二叉树一样包含左右孩子节点，还有_k值，一般情况下，二叉搜索树的_k值是唯一的，因为当前节点左孩子的_k小于当前节点的_k，而右孩子的则比当前节点的_k大，所以当插入一个在二叉搜索树中存在的值时，会返回false，不进行插入。

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


public:
	bool insert(const K& k)
	{
		if (_root == nullptr)
		{
			_root = new Node(k);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_k < k)
			{
				parent = cur;
				cur = cur->_r;
			}
			else if (cur->_k > k)
			{
				parent = cur;
				cur = cur->_l;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(k);
		if (parent->_k < k)
		{
			parent->_r = cur;
		}
		else
		{
			parent->_l = cur;
		}
		return true;
	}

在二叉搜索树中查找结点比较简单，根据二叉搜索树的性质，左子树小于根小于右子树能确定，当x大于当前节点的_k时，去右子树中找，小于则去左子树中找，遇到空节点则说明不存在。

bool find(const K& k)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_k < k)
		{
			cur = cur->_r;
		}
		else if (cur->_k > k)
		{
			cur = cur->_l;
		}
		else
		{
			return true;
		}
	}
	return false;
}

二叉搜索树的删除则比较麻烦，首先因为删除节点后要保证树的完整性，所以find节点时也要标记当前节点的父节点，当找到要删除的节点时，就要判断该节点的孩子节点的情况，可以分为左孩子为空、右孩子为空、左右孩子都存在。（左右孩子都不存在并入1、2情况中）
a.左孩子节点为空：
首先判断当前节点是否为根节点，如果是根节点，直接使右孩子为根节点
在这里插入图片描述
若不是根节点，则判断当前节点是父节点的左孩子还是右孩子，如果是左孩子，则父节点的右指针指向该节点的右孩子，否则让父节点的左指针指向当前节点的右孩子
在这里插入图片描述
在这里插入图片描述

b.右孩子节点为空：
同样先判断当前节点是否为根节点，为根节点则让根节点为左孩子节点
在这里插入图片描述
再判断当前节点是父节点左孩子还是右孩子，为左孩子则让父节点的左指针指向被删节点的左孩子，反之让父节点的右指针指向当前节点的左孩子

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

c.被删节点左右孩子都存在，此时用交换法使被删节点成为前面只有单个孩子或者没有孩子节点的情况。我们可以让被删节点与右子树的最左的节点或左子树的最右节点交换。
交换的合法性：
1.二叉搜索树的性质右>根>左，对于当前节点的右子树的最左节点，在右子树中，最左代表最小，所以它比右子树其他节点小，但它又在被删节点的右子树中，所以它比被删节点大，同时就比被删节点的左子树的所有结点大，所以交换后对右子树最左结点没有影响。
2.因为是右子树的最左结点，它没有左孩子，交换后可以将被删结点带入a情况解决。

左子树的最右节点同理。

	bool erase(const K& k)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_k < k)
			{
				parent = cur;
				cur = cur->_r;
			}
			else if (cur->_k > k)
			{
				parent = cur;
				cur = cur->_l;
			}
			else
			{
				if (cur->_l == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_r;
					}
					else
					{
						if (cur == parent->_l)
						{
							parent->_l = cur->_r;
						}
						else
						{
							parent->_r = cur->_r;
						}
					}
					delete cur;
				}
				else if (cur->_r == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_l;
					}
					else
					{
						if (cur == parent->_l)
						{
							parent->_l = cur->_l;
						}
						else
						{
							parent->_r = cur->_l;
						}
					}
					delete cur;
				}
				else
				{
					Node* rightMinParent = cur;
					Node* rightMin = cur->_r;
					while (rightMin->_l)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_l;
					}
					swap(cur->_k, rightMin->_k);
					if (rightMinParent->_l == rightMin)
					{
						rightMinParent->_l = rightMin->_r;
					}
					else
					{
						rightMinParent->_r = rightMin->_r;
					}
					delete rightMin;
				}
				return true;
			}
		}
	}

完整代码

namespace K_model
{
	//K模型
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _l;
		BSTreeNode<K>* _r;
		K _k;

		BSTreeNode(const K& k)
			:_l(nullptr)
			, _r(nullptr)
			, _k(k)
		{}
	};

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


	public:
		bool insert(const K& k)
		{
			if (_root == nullptr)
			{
				_root = new Node(k);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					parent = cur;
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					parent = cur;
					cur = cur->_l;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(k);
			if (parent->_k < k)
			{
				parent->_r = cur;
			}
			else
			{
				parent->_l = cur;
			}
			return true;
		}


		bool find(const K& k)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					cur = cur->_l;
				}
				else
				{
					return true;
				}
			}
			return false;
		}


		bool erase(const K& k)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					parent = cur;
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					parent = cur;
					cur = cur->_l;
				}
				else
				{
					if (cur->_l == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_r;
						}
						else
						{
							if (cur == parent->_l)
							{
								parent->_l = cur->_r;
							}
							else
							{
								parent->_r = cur->_r;
							}
						}
						delete cur;
					}
					else if (cur->_r == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_l;
						}
						else
						{
							if (cur == parent->_l)
							{
								parent->_l = cur->_l;
							}
							else
							{
								parent->_r = cur->_l;
							}
						}
						delete cur;
					}
					else
					{
						Node* rightMinParent = cur;
						Node* rightMin = cur->_r;
						while (rightMin->_l)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_l;
						}
						swap(cur->_k, rightMin->_k);
						if (rightMinParent->_l == rightMin)
						{
							rightMinParent->_l = rightMin->_r;
						}
						else
						{
							rightMinParent->_r = rightMin->_r;
						}
						delete rightMin;
					}
					return true;
				}
			}
		}

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

	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_l);
			cout << root->_k;
			_InOrder(root->_r);
		}
	private:
		Node* _root = nullptr;

	};
}

测试一下：

void testBSTree1()
{
	
	int a[] = { 3,7,5,9,11,3,2,6,4,1 ,8};
	K_model::BSTree<int> t1;
	for (auto& e : a)
	{
		t1.insert(e);
	}
	t1.InOrder();
	t1.erase(8);
	t1.InOrder();
	for (auto& e : a)
	{
		t1.erase(e);
		t1.InOrder();
	}

}

在这里插入图片描述

KV模型

KV模型的具体思路和代码实现与K模型几乎一样，只需加入一个V值与k对应即可

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

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					parent = cur;
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					parent = cur;
					cur = cur->_l;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(k,v);
			if (parent->_k < k)
			{
				parent->_r = cur;
			}
			else
			{
				parent->_l = cur;
			}
			return true;
		}

		
		Node* Find(const K& k)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					cur = cur->_l;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}

		bool Erase(const K& k)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					parent = cur;
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					parent = cur;
					cur = cur->_l;
				}
				else
				{
					if (cur->_l == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_r;
						}
						else
						{
							if (cur == parent->_l)
							{
								parent->_l = cur->_r;
							}
							else
							{
								parent->_r = cur->_r;
							}
						}
						delete cur;
					}
					else if (cur->_r == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_l;
						}
						else
						{
							if (cur == parent->_l)
							{
								parent->_l = cur->_l;
							}
							else
							{
								parent->_r = cur->_l;
							}
						}
						delete cur;
					}
					else
					{
						Node* rightMinParent = cur;
						Node* rightMin = cur->_r;
						while (rightMin->_l)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_l;
						}
						swap(cur->_k, rightMin->_k);
						if (rightMinParent->_l == rightMin)
						{
							rightMinParent->_l = rightMin->_r;
						}
						else
						{
							rightMinParent->_r = rightMin->_r;
						}
						delete rightMin;
					}
					return true;
				}
			}
		}
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_l);
			cout << root->_k << ":" << root->_v << endl;
			_InOrder(root->_r);
		}
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		Node* _root = nullptr;
	};

测试：

	void TestBSTree()
	{
		BSTree<string, string> dict;
		dict.Insert("insert", "插入");
		dict.Insert("erase", "删除");
		dict.Insert("left", "左边");
		dict.Insert("string", "字符串");
		dict.Insert("right", "右边");

		string str;
		while (cin >> str)
		{
			auto ret = dict.Find(str);
			if (ret)
			{
				cout << str << ":" << ret->_v << endl;
			}
			else
			{
				cout << "单词拼写错误" << endl;
			}
		}

		string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
		// 统计水果出现的次
		BSTree<string, int> countTree;
		for (auto str : strs)
		{
			auto ret = countTree.Find(str);
			if (ret == NULL)
			{
				countTree.Insert(str, 1);
			}
			else
			{
				ret->_v++;
			}
		}
		countTree.InOrder();
	}

在这里插入图片描述

二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
在这里插入图片描述
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：lgN
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N

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

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

相关文章

计算机网络面试高频：输入域名会发生那些操作，开放性回答

计算机网络面试高频：输入域名会发生那些操作，开放性回答

更多大厂面试内容可见 -> http://11come.cn 计算机网络面试高频&#xff1a;输入域名会发生那些操作&#xff0c;开放性回答 输入域名之后&#xff0c;会发生哪些操作&#xff1f; 当在浏览器中输入www.baidu.com并按下回车键时&#xff0c;会触发一系列复杂的网络过程&am…
阅读更多...
MMSeg搭建自己的网络

MMSeg搭建自己的网络

配置结构 首先&#xff0c;我们知道MMSeg矿机的配置文件很多&#xff0c;主要结构如下图所示。 在configs/_base_下是模型配置、数据集配置、以及一些其他的常规配置和运行配置&#xff0c;四类。 configs/all_config目录下存放&#xff0c;即是将四种配置聚合在一起的一个总…
阅读更多...
互联网的下个风口可能是供应链和B2B行业的创新

互联网的下个风口可能是供应链和B2B行业的创新

6年前我写过一篇文章叫做《所有B2B从业者都会遇到的9个问题》&#xff0c;这篇文章也同步发布在了我的知乎以及CSDN博客上面。几个平台陆续有读者通过私信和留言向我咨询一些问题&#xff0c;刚好这2年我对B2B又有了一些新的思考&#xff0c;于是就针对前些年的那篇文章做一些补…
阅读更多...
ubuntu22.04安装TensorRT（过程记录）

ubuntu22.04安装TensorRT（过程记录）

重要说明&#xff1a;此贴经过多次修改。第一次安装的的为trt8.6.1版本。第二次安装的10.0.0.6版本。有些地方可能没改过来&#xff0c;比如链接向导&#xff0c;我懒得改了&#xff0c;但是流程是对的。 cuda和cudnn版本对应关系 tensorRT历史发行版本 CUDA历史发行版本 cudn…
阅读更多...
【Linux】make 和 makefile

【Linux】make 和 makefile

进度条 #pragma once#include <stdio.h>#define NUM 102 #define BODY #define TOP 100 #define RIGHT >extern void processbar(int rate);#include "processBar.h" #include <string.h> #include <unistd.h>const char lable[] "|/-\…
阅读更多...
【限时免费】Adobe全家桶免费领取 一键安装，永久使用 全家桶大礼包破解直装版 2020-2024 设计师御用超全软件 值得收藏

【限时免费】Adobe全家桶免费领取 一键安装，永久使用 全家桶大礼包破解直装版 2020-2024 设计师御用超全软件 值得收藏

一次购买&#xff0c;终生使用&#xff01;正版永久激活&#xff0c;免费一键安装&#xff0c;赠送学习视频教程&#xff0c;支持远程安装&#xff0c;安装失败&#xff0c;立即退款。无需付费&#xff0c;直接免费送&#xff01; Adobe全家桶&#xff08;Adobe Creative Clou…
阅读更多...
【Canvas与艺术】绘制美国星条旗

【Canvas与艺术】绘制美国星条旗

【成图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>使用HTML5/Canvas绘制美国星条旗</title><style type"…
阅读更多...
舌头分割YOLOV8-SEG

舌头分割YOLOV8-SEG

舌头分割&#xff0c;基于YOLOV8-SEG&#xff0c;训练得到PT模型&#xff0c;然后转换成ONNX&#xff0c;OPENCV的DNN调用&#xff0c;从而摆脱YOLO依赖&#xff0c;支持C,PYTHON,ANDROID开发 舌头分割YOLOV8-SEG
阅读更多...
Gromacs——教程学习(1)

Gromacs——教程学习(1)

分子动力学模拟&#xff08;Molecular Dynamics&#xff09;全流程 所有的xvg格式文件&#xff0c;都可以使用大神编写的python DuIvyTools脚本可视化&#xff0c;很方便&#xff0c;只要你的电脑配置了python或者anaconda或者miniconda pip install DuIvyToolsdit xvg_show -…
阅读更多...
Blender面操作

Blender面操作

1.细分Subdivide -选择一个面 -右键&#xff0c;细分 -微调&#xff0c;设置切割次数 2.删除 -选择一个或多个面&#xff0c;按X键 -选择要删除的是面&#xff0c;线还是点 3.挤出面Extrude -选择一个面 -Extrude工具 -拖拽手柄&#xff0c;向外挤出 -微调&#xff…
阅读更多...
构建中小型企业网络-单臂路由

构建中小型企业网络-单臂路由

1.给IP地址配置好对应的IP和网关 2.配置交换机 3.路由配置 在交换机ge0/0/1中配置端口为trunk是可以允许多个vlan通过的&#xff0c;但路由器是不能够配置vlan&#xff0c;而交换机和路由器间连接的只有一根线&#xff0c;一个端口又只能配置一个ip地址&#xff0c;只有一个ip地…
阅读更多...
内网穿透及公网解析说明

内网穿透及公网解析说明

内网穿透释义&#xff1a; 自己在本地搭建服务器时&#xff0c;本地网络有多种环境&#xff0c;如没有公网IP、没有路由映射权限、网络被NAT转发等情况。在需要外网访问内网服务器资源时&#xff0c;就需要用到内网穿透。内网穿透&#xff0c;即内网映射&#xff0c;内网IP地址…
阅读更多...
vue3中使用animate.css

vue3中使用animate.css

在vue3中使用animate.css 20240428_093614 引入&#xff1a;npm install animate.css --save main.js注册&#xff1a;import ‘animate.css/animate.min.css’ 注意&#xff1a;import ‘animate.css’ 不适合在vue3项目 使用&#xff1a;class“animate__animated 动画名称”…
阅读更多...
艾宾浩斯记忆曲线记忆法，艾宾浩斯遗忘曲线计划表

艾宾浩斯记忆曲线记忆法，艾宾浩斯遗忘曲线计划表

一、资料前言 本套遗忘曲线复习计划表&#xff0c;大小59.22M&#xff0c;1个压缩文件。 二、资料目录 00 艾宾浩斯视频介绍 01 艾宾浩斯表格&#xff08;智能电子版&#xff09; 02 艾宾浩斯表格&#xff08;可编辑可打印&#xff09; 03 日周月计划表 04 一些好用的表…
阅读更多...
通过中缀表达式转后缀表达式计算复杂表达式

通过中缀表达式转后缀表达式计算复杂表达式

栈操作与表达式解析&#xff1a;从基础到实践 在计算机科学中&#xff0c;栈是一种常用的数据结构&#xff0c;它遵循后进先出&#xff08;LIFO&#xff09;的原则。本文将通过一系列函数的实现&#xff0c;探讨栈在括号匹配、中缀表达式转换为后缀表达式以及后缀表达式求值中…
阅读更多...
终端安全管理软件哪个好？

终端安全管理软件哪个好？

终端安全管理软件是保障企业信息安全的重要工具。 它们能够有效地防范恶意软件、黑客攻击和其他安全威胁&#xff0c;并提供多方面的终端设备安全保护措施。 终端安全软件的功能和保护机制各不相同&#xff0c;这就需要企业根据自身的需求和情况来进行评估和选择。 下面总结了…
阅读更多...
自动化测试

自动化测试

自动化测试 1、quit() 和 close()的区别2、窗口切换3、截图操作 1、quit() 和 close()的区别 1、quit() 是关闭整个浏览器&#xff1b;而close() 是关闭当前的页面&#xff1b; 2、quit() 操作会清空缓存&#xff1b;close() 不会清空缓存&#xff1b; 2、窗口切换 private …
阅读更多...
Python 语音识别系列-实战学习-语音识别特征提取

Python 语音识别系列-实战学习-语音识别特征提取

Python 语音识别系列-实战学习-语音识别特征提取 前言1.预加重、分帧和加窗2.提取特征3.可视化特征4.总结 前言 语音识别特征提取是语音处理中的一个重要环节&#xff0c;其主要任务是将连续的时域语音信号转换为连续的特征向量&#xff0c;以便于后续的语音识别和语音处理任务…
阅读更多...
【leetcode】快慢指针相关题目总结

【leetcode】快慢指针相关题目总结

141. 环形链表 判断链表是否有环&#xff1a;如果链表中存在环&#xff0c;则在链表上不断前进的指针会一直在环里绕圈子&#xff0c;且不能知道链表是否有环。使用快慢指针&#xff0c;当链表中存在环时&#xff0c;两个指针最终会在环中相遇。 /*** Definition for singly-…
阅读更多...
Java动态代理的实现方式

Java动态代理的实现方式

Java动态代理的实现方式 什么是动态代理&#xff1f; 动态代理是一种编程模式&#xff0c;它允许在运行时创建代理对象&#xff0c;以实现对目标对象的方法进行增强&#xff0c;代理对象同名方法内可以执行原有逻辑的同时嵌入执行其他增强逻辑或者其他对象方法。 动态代理的…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站