【C++进阶之路】第三篇：二叉搜索树 kv模型

文章目录

  • 一、二叉搜索树
    • 1.二叉搜索树概念
    • 2.二叉搜索树操作
    • 3.二叉搜索树的实现
  • 二、二叉搜索树的应用
    • 1.kv模型
    • 2.kv模型的实现
  • 三、 二叉搜索树的性能分析

一、二叉搜索树

1.二叉搜索树概念

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

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

在这里插入图片描述

2.二叉搜索树操作

在这里插入图片描述

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

（1）二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

（2）二叉搜索树的插入

插入的具体过程如下：

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

在这里插入图片描述

（3）二叉搜索树的删除

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

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

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

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

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

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

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

注意：

  • 使用替换法删除，我们通常替换所需删除节点右树中的最小节点，即所需删除节点右树区域的最左节点。需要与被删除节点替换的节点可能左为空，所以我们不能直接删除它，我们还要多做一些工作–要考虑情况c发生的可能性，做情况c一样的工作。

  • 使用替换法删除，还要考虑根节点的删除问题（根节点就是所需删除节点右树区域的最左节点）
    在这里插入图片描述

3.二叉搜索树的实现

  • BSTree.h
namespace key
{
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;

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

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

		BSTree() = default; // 制定强制生成默认构造

		BSTree(const BSTree<K>& t)
		{
			_root = Copy(t._root);
		}

		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}

		~BSTree()
		{
			Destroy(_root);
			//_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->_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
				{
					// 删除
					// 1、左为空
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;

					} // 2、右为空
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						// 找右树最小节点替代，也可以是左树最大节点替代
						Node* pminRight = cur;
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							pminRight = minRight;
							minRight = minRight->_left;
						}

						cur->_key = minRight->_key;

						if (pminRight->_left == minRight) //考虑根节点，做判断
						{
							pminRight->_left = minRight->_right; //正常节点
						}
						else
						{
							pminRight->_right = minRight->_right; //根节点
						}

						delete minRight;
					}

					return true;
				}
			}

			return false;
		}



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

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

			Destroy(root->_left);
			Destroy(root->_right);

			delete root;
			root = nullptr;
		}



	private:
		Node* _root = nullptr;
	};
}
  • Test.cpp
void TestBSTree1()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	key::BSTree<int> t1;

	for (auto e : a)
	{
		t1.Insert(e);
	}

	//t1.InOrder(t1.GetRoot());
	t1.InOrder();

	/*t1.Erase(7);
	t1.InOrder();

	t1.Erase(14);
	t1.InOrder();

	t1.Erase(3);
	t1.InOrder();*/

	t1.Erase(8);
	t1.InOrder();


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

	t1.InOrder();
}


int main()
{
	TestBSTree1();

	return 0;
}

二、二叉搜索树的应用

1.kv模型

  1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

    比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

    • 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树

    • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

  2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

    • 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
    • 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

2.kv模型的实现

  • 改造二叉搜索树为KV结构
// 改造二叉搜索树为KV结构
namespace key_value
{
	// BinarySearchTree -- BSTree
	// SearchBinaryTree

	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _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
				{
					// 删除
					// 1、左为空
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;

					} // 2、右为空
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						// 找右树最小节点替代，也可以是左树最大节点替代
						Node* pminRight = cur;
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							pminRight = minRight;
							minRight = minRight->_left;
						}

						cur->_key = minRight->_key;

						if (pminRight->_left == minRight)
						{
							pminRight->_left = minRight->_right;
						}
						else
						{
							pminRight->_right = minRight->_right;
						}

						delete minRight;
					}

					return true;
				}
			}

			return false;
		}


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

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

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};
}
  • 测试用例
// 测试用例
void TestBSTree2()
{
	key_value::BSTree<string, string> dict;
	dict.Insert("sort", "排序");
	dict.Insert("left", "左边");
	dict.Insert("right", "右边");
	dict.Insert("string", "字符串");
	dict.Insert("insert", "插入");
	dict.Insert("erase", "删除");

	string str;
	while (cin >> str)
	{
		auto ret = dict.Find(str);
		if (ret)
		{
			cout << ":" << ret->_value << endl;
		}
		else
		{
			cout << "无此单词" << endl;
		}
	}
}

void TestBSTree3()
{
	string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };

	key_value::BSTree<string, int> countTree;
	for (auto str : arr)
	{
		//key_value::BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == nullptr)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}

	countTree.InOrder();
}

int main()
{
	TestBSTree3();

	return 0;
}

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

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

在这里插入图片描述

  • 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log_2 N（以2为底N的对数）
  • 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N

结论：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？依据AVL树和红黑树的知识可以很好的解决，这两个知识小编会在后续章节讲解，此处先不做深入赘述。

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

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

相关文章

UG\NX二次开发 连接曲线、连结曲线 UF_CURVE_auto_join_curves

UG\NX二次开发 连接曲线、连结曲线 UF_CURVE_auto_join_curves

文章作者：里海 来源网站：王牌飞行员_里海_里海NX二次开发3000例,里海BlockUI专栏,C\C++-CSDN博客 简介 UG\NX二次开发 连接曲线、连结曲线 UF_CURVE_auto_join_curves 效果 代码 #include "me.hpp" extern DllExport void ufusr(char* param, int* returnC…
阅读更多...
使用Docker快速搭建服务器环境

使用Docker快速搭建服务器环境

简介 这篇文章也是方便自己记录搭建流程&#xff0c;服务器的购买啥的就不说了&#xff0c;最终目标就是在一个空白的Linux系统上&#xff0c;使用docker运行MySQL、TomcatJava、Nginx、Redis 的单机环境&#xff0c;以后方便自己快速的部署服务器。 安装Docker 首先需要安装…
阅读更多...
Spring关于注解的使用

Spring关于注解的使用

目录 一、使用注解开发的前提 1.1 配置注解扫描路径 二、使用注解创建对象 2.1 Controller&#xff08;控制器储存&#xff09; 2.2 Service&#xff08;服务储存&#xff09; 2.3 Repository&#xff08;仓库储存&#xff09; 2.4 Component&#xff08;组件储存&#xff09; …
阅读更多...
Qt之彻底解决QSpinBox限定范围无效的问题

Qt之彻底解决QSpinBox限定范围无效的问题

QSpinBox有个比较啃爹的问题，不管取值范围设置为多少，都能一直输入0，如下图所示： 当取值范围包含负数时，负号后也可以一直输入0，如下图所示： 还有就是当取值范围设置为10以上时，比如10~100，却可以输入1~9 虽然上述非法输入最终都未生效，当QSpinBox失去焦点时会显示为…
阅读更多...
030-第三代软件开发-密码输入框

030-第三代软件开发-密码输入框

第三代软件开发-密码输入框 文章目录 第三代软件开发-密码输入框项目介绍密码输入框总结一下 关键字&#xff1a; Qt、 Qml、 echoMode、 TextInput、 Image 项目介绍 欢迎来到我们的 QML & C 项目&#xff01;这个项目结合了 QML&#xff08;Qt Meta-Object Language…
阅读更多...
【Ubuntu18.04】激光雷达与相机联合标定（Livox+HIKROBOT）（一）

【Ubuntu18.04】激光雷达与相机联合标定（Livox+HIKROBOT）（一）

LivoxHIKROBOT联合标定 引言1 海康机器人HIKROBOT SDK二次开发并封装ROS1.1 介绍1.2 安装MVS SDK1.3 封装ROS packge 2 览沃Livox SDK二次开发并封装ROS3 相机雷达联合标定3.1 环境配置3.1.1 安装依赖——PCL 安装3.1.2 安装依赖——Eigen 安装3.1.3 安装依赖——Ceres-solver …
阅读更多...
数据结构与算法之矩阵: Leetcode 134. 螺旋矩阵 (Typescript版)

数据结构与算法之矩阵: Leetcode 134. 螺旋矩阵 (Typescript版)

螺旋矩阵 https://leetcode.cn/problems/spiral-matrix/ 描述 给你一个 m 行 n 列的矩阵 matrix &#xff0c;请按照 顺时针螺旋顺序 &#xff0c;返回矩阵中的所有元素。 示例 1 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&#xff1a;[1,2,3,6,9,8,7,4,5]示…
阅读更多...
RT-Thread 8. RT-Thread Studio arm-gcc使用10.2.1编译

RT-Thread 8. RT-Thread Studio arm-gcc使用10.2.1编译

1. gcc编译器下载 E:\RT-ThreadStudio\repo\Extract\ToolChain_Support_Packages\ARM\GNU_Tools_for_ARM_Embedded_Processors2. 把5.4.1 改为5.4.11 再“全部构建”&#xff0c;提示错误 3. 把工具链版本改为10.2.1&#xff0c;再“全部构建”
阅读更多...
华为eNSP配置专题-路由策略的配置

华为eNSP配置专题-路由策略的配置

文章目录 华为eNSP配置专题-路由策略的配置0、概要介绍1、前置环境1.1、宿主机1.2、eNSP模拟器 2、基本环境搭建2.1、终端构成和连接2.2、终端的基本配置 3、配置路由策略3.1、目标3.2、配置路由策略 华为eNSP配置专题-路由策略的配置 0、概要介绍 路由策略就是通过一系列工具…
阅读更多...
测试中Android与IOS分别关注的点

测试中Android与IOS分别关注的点

主要从本身系统的不同点、系统造成的不同点、和注意的测试点做总结 1、自身不同点 研发商&#xff1a;Adroid是google公司做的手机系统&#xff0c;IOS是苹果公司做的手机系统开源程度&#xff1a;Android是开源的&#xff0c;IOS是半开源的。所以IOS系统相对于Android来说是…
阅读更多...
C++ 模板和泛型编程详解

C++ 模板和泛型编程详解

C中的模板和泛型编程是非常重要的概念。模板是一种将数据类型作为参数的通用程序设计方法。它们允许开发人员编写可以处理各种数据类型的代码&#xff0c;而无需为每种数据类型编写不同的代码。下面介绍了一些关于C中模板和泛型编程的重要知识点 模板的定义 模板是一种通用程序…
阅读更多...
php使用lunar实现农历、阳历、节日等功能

php使用lunar实现农历、阳历、节日等功能

lunar是一个支持阳历、阴历、佛历和道历的日历工具库&#xff0c;它开源免费&#xff0c;有多种开发语言的版本&#xff0c;不依赖第三方&#xff0c;支持阳历、阴历、佛历、道历、儒略日的相互转换&#xff0c;还支持星座、干支、生肖等。仅供参考&#xff0c;切勿迷信。 官…
阅读更多...
Qt扫盲-QPen 理论使用总结

Qt扫盲-QPen 理论使用总结

QPen 理论使用总结 一、概述二、Pen Style 画笔风格三、Cap Style 帽风格四、Join Style 连接处样式 一、概述 QPen 是Qt绘图控件里面的一个重要的组件&#xff0c;和QColor 一样也是类似的一个属性类。这个类就是描述一个画笔具有的属性。 一个画笔 Pen 有style()&#xff0…
阅读更多...
encodeURIComponent对url参数进行编码

encodeURIComponent对url参数进行编码

在开发需求过程中&#xff0c;经常会遇到点击链接进入详情页的情况&#xff0c;一般的做法如下&#xff1a; window.open("/xxx/xxx/xxxDetail?a" item.a &b item.b); 我们也经常需要在详情页中获取url上面的参数进行一些逻辑的处理&#xff0c;一般的做法…
阅读更多...
FL Studio 21 for Mac中文破解版百度网盘免费下载安装激活

FL Studio 21 for Mac中文破解版百度网盘免费下载安装激活

FL Studio 21 for Mac中文破解版是Mac系统中的一款水果音乐编辑软件&#xff0c;提供多种插件&#xff0c;包括采样器、合成器和效果器&#xff0c;可编辑不同风格的音乐作品&#xff0c;Pattern/Song双模式&#xff0c;可兼容第三方插件和音效包&#xff0c;为您的创意插上翅膀…
阅读更多...
P-MOS管开关机控制电路（手动按键控制和自动采样信号触发控制）

P-MOS管开关机控制电路（手动按键控制和自动采样信号触发控制）

1. 手动(按键)控制 这种控制适合与消费电子&#xff0c;家庭消费电子领域&#xff0c;用户人为地手动按动机械按键控制P-MOS管导通与断开。例如&#xff1a;电动牙刷、儿童玩具等等&#xff0c;很多都会用到一个按钮控制产品的开关机&#xff0c;调档等等。 1.1 RH6030_JX触摸…
阅读更多...
Ubuntu deadsnakes 源安装新版 python

Ubuntu deadsnakes 源安装新版 python

前言 适用于 Ubuntu 安装 python3.11 等新版本。 因为比较常用并且不想重新编译就记录一下&#xff0c;方便以后面向CV安装。 安装 添加 deadsnakes ppa 源 sudo add-apt-repository ppa:deadsnakes/ppa更新 apt sudo apt update安装 python3.11 sudo apt install python…
阅读更多...
【java爬虫】使用selenium获取某交易所公司半年报数据

【java爬虫】使用selenium获取某交易所公司半年报数据

引言 上市公司的财报数据一般都会进行公开&#xff0c;我们可以在某交易所的官方网站上查看这些数据&#xff0c;由于数据很多&#xff0c;如果只是手动收集的话可能会比较耗时耗力&#xff0c;我们可以采用爬虫的方法进行数据的获取。 本文就介绍采用selenium框架进行公司财…
阅读更多...
【网络】对于我前面UDP博客的补充

【网络】对于我前面UDP博客的补充

UDP 前言正式开始UDP报文UDP报文如何将UDP报文和报头进行分离和封装UDP如何将有效载荷交付给上层如何提取出完整报文报头是啥报头中的检验和 UDP的特点IO接口乱序问题UDP是全双工的注意事项基于UDP的应用层协议 再次谈论端口五元组端口号范围划分netstatxargs 前言 本篇比较偏…
阅读更多...
【Qt之QtConcurrent】描述及使用

【Qt之QtConcurrent】描述及使用

描述 QtConcurrent是一个Qt库中的模块&#xff0c;用于实现多线程并发编程。它提供了一些高级API&#xff0c;使得在多核处理器上并行执行代码变得更加容易。 示例&#xff1a; 使用的话&#xff0c; 需要在pro文件中添加&#xff1a;QT concurrent模块。 #include <QC…
阅读更多...
最新文章

Copyright @ 2022~2023

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