【数据结构】二叉搜索树底层刨析

文章目录

  • 1. 二叉搜索树的实现
  • 2. 二叉搜索树的应用
  • 3. 改造二叉搜索树为 KV 结构
  • 4. 二叉搜索树的性能分析

在这里插入图片描述

1. 二叉搜索树的实现

namespace key
{
	template<class K>
	struct BSTreeNode
	{
		typedef BSTreeNode<K> Node;

		Node* _left;
		Node* _right;
		K _key;

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

	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		// 强制生成默认构造
		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);
		}

		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
				{
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_right)
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_right)
							{
								parent->_right = cur->_left;
							}
							else
							{
								parent->_left = cur->_left;
							}
						}
						delete cur;
						return true;
					}
					else
					{
						// 替换法
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

						cur->_key = rightMin->_key;

						if (rightMin == rightMinParent->_left)
						{
							rightMinParent->_left = rightMin->_right;
						}
						else
						{
							rightMinParent->_right = rightMin->_right;
						}

						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}

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

		bool FindR(const K& key)
		{
			return _FindR(_root, key);
		}

		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}

		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}

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

			Destroy(root->_left);
			Destroy(root->_right);
			delete 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;
		}

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

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

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

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

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

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

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

			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _EraseR(root->_left, key);
			}
			else
			{
				Node* del = root;
				if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else
				{
					Node* rightMin = root->_right;
					while (rightMin->_left)
					{
						rightMin = rightMin->_left;
					}
					swap(root->_key, rightMin->_key);

					return _EraseR(root->_right, key);
				}
				delete del;
				return true;
			}
		}

	private:
		Node* _root = nullptr;
	};
}

2. 二叉搜索树的应用

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

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

    • 以词库中所有单词集合中的每个单词作为 key，构建一颗二叉搜索树；
    • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

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

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

3. 改造二叉搜索树为 KV 结构

namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		typedef BSTreeNode<K, V> Node;

		Node* _left;
		Node* _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
				{
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_right)
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_right)
							{
								parent->_right = cur->_left;
							}
							else
							{
								parent->_left = cur->_left;
							}
						}
						delete cur;
						return true;
					}
					else
					{
						// 替换法
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

						cur->_key = rightMin->_key;

						if (rightMin == rightMinParent->_left)
						{
							rightMinParent->_left = rightMin->_right;
						}
						else
						{
							rightMinParent->_right = rightMin->_right;
						}

						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}

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

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

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

	private:
		Node* _root = nullptr;
	};
}

测试代码：

namespace key_value
{
	void TestBSTree1()
	{
		// 输入单词，查找单词对应的中文翻译
		BSTree<string, string> dict;
		dict.Insert("string", "字符串");
		dict.Insert("tree", "树");
		dict.Insert("left", "左边、剩余");
		dict.Insert("right", "右边");
		dict.Insert("sort", "排序");
		// 插入词库中所有单词
		string str;
		while (cin >> str)
		{
			BSTreeNode<string, string>* ret = dict.Find(str);
			if (ret == nullptr)
			{
				cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
			}
			else
			{
				cout << str << "中文翻译:" << ret->_value << endl;
			}
		}
	}

	void TestBSTree2()
	{
		// 统计水果出现的次数
		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
		"苹果", "香蕉", "苹果", "香蕉" };
		BSTree<string, int> countTree;
		for (const auto& str : arr)
		{
			// 先查找水果在不在搜索树中
			// 1、不在，说明水果第一次出现，则插入<水果, 1>
			// 2、在，则查找到的节点中水果对应的次数++
			//BSTreeNode<string, int>* ret = countTree.Find(str);
			auto ret = countTree.Find(str);
			if (ret == NULL)
			{
				countTree.Insert(str, 1);
			}
			else
			{
				ret->_value++;
			}
		}
		countTree.InOrder();
	}
}

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

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

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

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

在这里插入图片描述

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其平均比较次数为： l o g 2 N log_2 N log2​N；

最差情况下，二叉搜索树退化为单支树（或者类似单支），其平均比较次数为： N 2 \frac{N}{2} 2N​。

问题：如果退化成单支树，二叉搜索树的性能就失去了。能否进行改进，不论按照什么次序插入关键码，都能使二叉搜索树的性能达到最优？

答：可以使用 AVL树 和 红黑树 的特性，使单支树在达到一定深度时进行“旋转”，变回接近完全二叉树的形状，这个我们后面再谈。

END

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

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

相关文章

【1】Python零基础起步

【1】Python零基础起步

什么是编程(Programming) 编程是编定程序的中文简称&#xff0c;就是让计算机代码解决某个问题&#xff08;目的&#xff09;&#xff0c;对某个计算体系规定一定的运算方式&#xff0c;使计算体系按照该计算方式运行&#xff0c;并最终得到相应结果的过程&#xff08;手段&am…
阅读更多...
Java Day 10 io流

Java Day 10 io流

IO流 1、前置知识 字符集1.1 标准ASCII1.2 GBK编码1.3 UTF-321.4 UTF-81.5 编码和解码方法 2、IO流2.1 流的分类2.2 FileInputStream2.2.1 常用方法 2.3 FileOutputStram2.3.1 常用方法2.3.2 文件复制案例 2.4 释放资源的方式2.4.1 try-catch-finally2.4.2 try-with-resource 1…
阅读更多...
ftp和fxp哪个传传输快，传输大文件该怎么选择？

ftp和fxp哪个传传输快，传输大文件该怎么选择？

在当今数字化时代&#xff0c;大文件传输已成为日常工作和商业活动中不可或缺的一部分。无论是跨国公司的数据交换&#xff0c;还是个人用户的大型媒体文件分享&#xff0c;选择一个高效的传输协议至关重要。FTP和FXP是两种常用的文件传输方式&#xff0c;但在传输大文件时&…
阅读更多...
nginx gzip性能优化 —— 筑梦之路

nginx gzip性能优化 —— 筑梦之路

对比使用和不使用gzip static处理 1. 不使用 gzip static 时的 gzip 处理 如果你不使用 gzip_static 而只是 "gzip on"&#xff0c;它每次都会被压缩并发送。 虽然它实际上可能缓存在内存中&#xff0c;但传统观点是 "每次都会执行压缩处理&#xff0c;因此 CP…
阅读更多...
【SRE系列之docker容器】--dockerfile镜像优化

【SRE系列之docker容器】--dockerfile镜像优化

dockerfile镜像优化 1.1 镜像优化方法 系统镜像采用ubuntu或者alpine&#xff0c;会比centos少1G左右编写业务镜像时从官网拉取镜像&#xff0c;其余配置根据业务需求再配置编写dockerfile时把不用的安装包卸载或者删除尽量减少run命令的使用&#xff08;一个run命令&#xf…
阅读更多...
【兆易创新GD32H759I-EVAL开发板】图像处理加速器（IPA）的应用

【兆易创新GD32H759I-EVAL开发板】图像处理加速器（IPA）的应用

GD32H7系列的IPA&#xff08;Image Pixel Accelerator&#xff09;是一个高效的图像处理硬件加速器&#xff0c;专门设计用于加速图像处理操作&#xff0c;如像素格式转换、图像旋转、缩放等。它的优势在于能够利用硬件加速来实现这些操作&#xff0c;相比于软件实现&#xff0…
阅读更多...
YOLOv9实例分割教程|（二）验证教程

YOLOv9实例分割教程|（二）验证教程

专栏地址&#xff1a;目前售价售价59.9&#xff0c;改进点30个 专栏介绍&#xff1a;YOLOv9改进系列 | 包含深度学习最新创新&#xff0c;助力高效涨点&#xff01;&#xff01;&#xff01; 一、验证 打开分割验证文件&#xff0c;填入数据集配置文件、训练好的权重文件&…
阅读更多...
go语言基础笔记

go语言基础笔记

1.基本类型 1.1. 基本类型 bool int: int8, int16, int32(rune), int64 uint: uint8(byte), uint16, uint32, uint64 float32, float64 string 复数&#xff1a;complex64, complex128 复数有实部和虚部&#xff0c;complex64的实部和虚部为32位&#xff0c;complex128的实部…
阅读更多...
yocto是个什么东东

yocto是个什么东东

yocto不是个什么东东 在我们了解Yocto项目是什么之前&#xff0c;让我们先了解一下它不是什么。 Yocto项目不是用于现有硬件的软件开发工具包&#xff08;SDK&#xff09;&#xff0c;而是用于构建这样一个工具包。 Yocto项目不是可以部署到硬件上的系统二进制镜像&#xff…
阅读更多...
客服销冠偷偷用的提效神器！无广很实用

客服销冠偷偷用的提效神器！无广很实用

近期发现我的同事每天上班必登录的一款软件——客服宝聊天助手&#xff0c;用过才发现&#xff1a;真客服办公的提效神器&#xff01;感兴趣的小伙伴请往下看~一、客服宝的简介&#xff1a;客服宝聊天助手&#xff0c;是一款跨平台快捷回复工具。自带多种功能&#xff0c;有效帮…
阅读更多...
leetcode判断子序列

leetcode判断子序列

本题中&#xff0c;我们可以删除原始字符串的一些字符但是不能改变其他字符的位置&#xff0c;这种求子序列的题都可以用动态规划来解决。 首先我们要确定dp数组的定义&#xff0c;这里我们将dp数组定义为dp[i][j] 表示以下标i-1为结尾的字符串s&#xff0c;和以下标j-1为结尾的…
阅读更多...
蓝桥杯[OJ 1621]挑选子串-CPP-双指针

蓝桥杯[OJ 1621]挑选子串-CPP-双指针

目录 一、题目描述&#xff1a; 二、整体思路&#xff1a; 三、代码&#xff1a; 一、题目描述&#xff1a; 二、整体思路&#xff1a; 要找子串&#xff0c;则必须找头找尾&#xff0c;找头可以遍历连续字串&#xff0c;找尾则是要从头的基础上往后遍历&#xff0c;可以设头…
阅读更多...
OSCP靶场--BlackGate

OSCP靶场--BlackGate

OSCP靶场–BlackGate 考点(1.redis rce 2. CVE-2021-4034提权) 1.nmap扫描 ┌──(root㉿kali)-[~/Desktop] └─# nmap -sV -sC -p- 192.168.163.176 --min-rate 2500 Starting Nmap 7.92 ( https://nmap.org ) at 2024-03-14 03:32 EDT Nmap scan report for 192.168.163.…
阅读更多...
MongoDB实战面试指南：常见问题一网打尽

MongoDB实战面试指南：常见问题一网打尽

码到三十五 &#xff1a; 个人主页 心中有诗画&#xff0c;指尖舞代码&#xff0c;目光览世界&#xff0c;步履越千山&#xff0c;人间尽值得 ! MongoDB是一款流行的非关系型数据库&#xff0c;以其高效、可扩展的特性受到开发者的青睐。了解MongoDB的架构、存储引擎和数据结…
阅读更多...
python 基础知识点（蓝桥杯python科目个人复习计划63）

python 基础知识点（蓝桥杯python科目个人复习计划63）

今日复习内容&#xff1a;做题 例题1&#xff1a;蓝桥骑士 问题描述&#xff1a; 小蓝是蓝桥王国的骑士&#xff0c;他喜欢不断突破自我。 这天蓝桥国王给他安排了N个对手&#xff0c;他们的战力值分别为a1,a2,...,an&#xff0c;且按顺序阻挡在小蓝的前方。对于这些对手小…
阅读更多...
剪辑设计软件如何跨系统使用？PC也能用Mac Final Cut

剪辑设计软件如何跨系统使用？PC也能用Mac Final Cut

我猜你工作中&#xff0c;常常遇到这样那样的麻烦&#xff1a; 临时接手一个项目&#xff0c;之前的同事用Final Cut&#xff0c;而你是Windows系统&#xff1b; 临时有紧急需求要调整&#xff0c;而本地电脑却没有工作软件/性能不给力&#xff1b; 那这样的情况&#xff0c…
阅读更多...
SSL证书如何实现数据加密传输？

SSL证书如何实现数据加密传输？

在当前互联网的洪流中&#xff0c;用户对网站隐私与安全性的重视程度日益提升。为了确保用户信息和交易数据的安全传输&#xff0c;SSL证书在网络世界中扮演了关键角色。本文将深入解析SSL证书的核心功能及其重要作用。 1、SSL证书采用加密技术保障数据传输安全 通过应用公钥加…
阅读更多...
Mysql 无法启动，mysql-bin.日志丢失删除处理

Mysql 无法启动，mysql-bin.日志丢失删除处理

在linux操作系统中&#xff0c;当mysql无法启动时候&#xff0c;先看日志 2024-03-15T05:20:16.352075Z 0 [Warning] [MY-000081] [Server] option max_allowed_packet: unsigned value 107374182400 adjusted to 1073741824. 2024-03-15T05:20:16.352156Z 0 [Warning] [MY-010…
阅读更多...
（008）Unity StateMachineBehaviour的坑

（008）Unity StateMachineBehaviour的坑

文章目录 StateMachineBehaviour同名函数的调用问题StateMachineBehaviour 的 OnState*、OnStateMachine* 的区别 StateMachineBehaviour同名函数的调用问题 1.如果脚本中&#xff0c;两个同名的函数都存在&#xff0c;那么两个函数都会被调用&#xff1b;如果只有其中一个同名…
阅读更多...
IO流——字节流

IO流——字节流

常见字符集 标准ASCII码字符集 ASCII(American Standard Code for Information Interchange)&#xff1a;美国信息交换标准代码&#xff0c;包括英文、符号等标准ASCII码使用1个字节存储一个字符&#xff0c;首位是0&#xff0c;总共可表示128个字符 而对于国内而言&a…
阅读更多...
最新文章

Copyright @ 2022~2023