C++进阶（五）二叉搜索树

在这里插入图片描述


📘北尘_：个人主页

🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》
☀️走在路上，不忘来时的初心

文章目录

  • 一、二叉搜索树概念
  • 二、二叉搜索树操作
  • 三、二叉搜索树的实现
  • 四、二叉搜索树的应用
  • 五、二叉搜索树的性能分析

一、二叉搜索树概念

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

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

在这里插入图片描述

二、二叉搜索树操作

在这里插入图片描述

在这里插入图片描述

  1. 二叉搜索树的查找
    a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
    b、最多查找高度次，走到到空，还没找到，这个值不存在。
  2. 二叉搜索树的插入
    插入的具体过程如下：
    a. 树为空，则直接新增节点，赋值给root指针
    b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

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

在这里插入图片描述

三、二叉搜索树的实现

#include<iostream>
using namespace std;

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:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			parent = cur;
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				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->_left)
						{
							parent->_left = cur->_right;
						}
						else 
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur -> _left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				else
				{
					Node* parent = cur;
					Node* subleft = cur->_right;
					while (subleft->_left)
					{
						parent = subleft;
						subleft = subleft->_left;
				
					}
					swap(cur->_key, subleft->_key);

					if (subleft == parent->_left)
					{
						parent->_left = subleft->_right;
					}
					else
					{
						parent->_right = subleft->_right;
					}
					delete subleft;
				}
				return true;
			}
		}
		return false;
	}
	~BSTree()
	{
		Destory(_root);
	}

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
	bool InsertR(const K& key)
	{
		return _InsertR(_root,key);
	}
	bool findR(const K& key)
	{
		return _findR(_root, key);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}
	//C++11
	BSTree()
	{}
	
	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root,t._root);
		return *this;
	}


private:
	Node* _root = nullptr;
	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 Destory(Node*& root)
	{

		if (root == nullptr)
			return;
		Destory(root->_left);
		Destory(root->_right);
		delete root;
		root = nullptr;
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	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 _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 _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
		{
			if (root->_left == nullptr)
			{
				Node* del = root;
				root = root->_right;
				delete del;
			}
			else if (root->_right == nullptr)
			{
				Node* del = root;
				root = root->_left;
				delete del;
			}
			else
			{
				Node* subleft = root->_right;
				while (subleft->_left)
				{
					subleft = subleft->_left;
				}
				swap(subleft->_key, root->_key);

				return _EraseR(root->_right, key);
			}
		}
		return false;
	}
	
};
int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> bt;
	for (auto e : a)
	{
		bt.InsertR(e);
	}
	bt.InOrder();

	bt.EraseR(14);
	bt.InOrder();

	bt.EraseR(3);
	bt.InOrder();

	bt.EraseR(8);
	bt.InOrder();

	for (auto e : a)
	{
		bt.EraseR(e);
		bt.InOrder();
	}
	return 0;
}

四、二叉搜索树的应用

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

					}
					swap(cur->_key, subleft->_key);

					if (subleft == parent->_left)
					{
						parent->_left = subleft->_right;
					}
					else
					{
						parent->_right = subleft->_right;
					}
					delete subleft;
				}
				return true;
			}
		}
		return false;
	}
	~BSTree()
	{
		Destory(_root);
	}
	void InOrder()
	{
		_InOrder(_root);
		
	}

private:
	Node* _root = nullptr;
	
	void Destory(Node*& root)
	{

		if (root == nullptr)
			return;
		Destory(root->_left);
		Destory(root->_right);
		delete root;
		root = nullptr;
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << ":" << root->_value << endl;
		_InOrder(root->_right);
	}
	

};
void TestBSTree3()
{
	// 输入单词，查找单词对应的中文翻译
	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 TestBSTree4()
{
	// 统计水果出现的次数
	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();
}

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

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

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

在这里插入图片描述

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

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上场了。

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

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

相关文章

C++中特殊类的设计与单例模式的简易实现

C++中特殊类的设计与单例模式的简易实现

设计一个只能在堆上创建对象的类 对于这种特殊类的设计我们一般都是优先考虑私有构造函数。然后对于一些特殊要求就直接通过静态成员函数的实现来完成。 class A//构造函数私有&#xff08;也可以析构函数私有&#xff09; { public:static A* creat(){return new A;} privat…
阅读更多...
VsCode + CMake构建项目 C/C++连接Mysql数据库 | 数据库增删改查C++封装 | 信息管理系统通用代码 ---- 课程笔记

VsCode + CMake构建项目 C/C++连接Mysql数据库 | 数据库增删改查C++封装 | 信息管理系统通用代码 ---- 课程笔记

这个是B站Up主&#xff1a;程序员程子青的视频 C封装Mysql增删改查操作_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1m24y1a79o/?p6&spm_id_frompageDriver&vd_sourcea934d7fc6f47698a29dac90a922ba5a3安装mysql:mysql 下载和安装和修改MYSQL8.0 数据库存储…
阅读更多...
2023 年，我患上了 AI 焦虑症！

2023 年，我患上了 AI 焦虑症！

【作者有话说】2023 年对我来说是神奇的一年&#xff0c;我意外地从一个程序员变成了一个 AI 资讯届的“网红”&#xff0c;到年底时我在 X 平台的阅读量超过 1 亿&#xff0c;微博上的阅读量则超过 10 亿&#xff0c;很多人通过我的微博或者 X 了解最新的 AI 资讯、教程和 Pro…
阅读更多...
C#，字符串匹配（模式搜索）Sunday算法的源代码

C#，字符串匹配（模式搜索）Sunday算法的源代码

Sunday算法是Daniel M.Sunday于1990年提出的一种字符串模式匹配算法。 核心思想&#xff1a;在匹配过程中&#xff0c;模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较&#xff0c;它在发现不匹配时&#xff0c;算法能跳过尽可能多的字符以进行下一步的匹配&…
阅读更多...
多维时序 | Matlab实现CNN-BiLSTM-Mutilhead-Attention卷积双向长短期记忆神经网络融合多头注意力机制多变量时间序列预测

多维时序 | Matlab实现CNN-BiLSTM-Mutilhead-Attention卷积双向长短期记忆神经网络融合多头注意力机制多变量时间序列预测

多维时序 | Matlab实现CNN-BiLSTM-Mutilhead-Attention卷积双向长短期记忆神经网络融合多头注意力机制多变量时间序列预测 目录 多维时序 | Matlab实现CNN-BiLSTM-Mutilhead-Attention卷积双向长短期记忆神经网络融合多头注意力机制多变量时间序列预测效果一览基本介绍程序设计…
阅读更多...
scipy测试数据

scipy测试数据

文章目录 图像心电图 图像 scipy的datasets中提供了几组在图像和信号处理中可能会用到的数据&#xff0c;但是&#xff0c;如果想顺利使用&#xff0c;还需要安装一个scipy的依赖模块pooch pip install pooch然后就可以加载这几种数据了 from scipy.datasets import ascent,…
阅读更多...
云服务器搭建coturn出现Not reachable?

云服务器搭建coturn出现Not reachable?

文章目录 问题复现解决方案1. 云服务器端口开放问题2. 检查配置文件3. 浏览器 问题解决 问题复现 使用云服务器搭建coturn服务时&#xff0c;出现not reachable报错 ICE Server配置是正确的 但测试relay时却报错&#xff1a;not reachable? 并且服务器也没输出相应日志。 …
阅读更多...
Windows命令大全

Windows命令大全

文章目录 1. 文件和目录管理2. 系统信息查询3. 系统维护与修复4. 网络相关5. PowerShell 命令6. 用户管理7. 进程和服务管理8. 文件搜索与查找9. 时间和日期操作10. 注册表操作 Windows系统命令非常丰富&#xff0c;涵盖了操作系统管理、文件操作、网络配置、系统维护等诸多方面…
阅读更多...
Java网络编程——UDP通信原理

Java网络编程——UDP通信原理

一、TCP和UDP概述 传输层通常以TCP和UDP协议来控制端点与端点的通信 TCPUDP协议名称传输控制协议用户数据包协议是否连接面向连接的协议。数据必须要建立连接无连接的协议&#xff0c;每个数据报中都给出完整的地址信息&#xff0c;因此不需要事先建立发送方和接受方的连接是…
阅读更多...
FPGA 多路分频器实验

FPGA 多路分频器实验

1 概述 在 FPGA 中&#xff0c;时钟分频是经常用到的。本节课讲解 2 分频、3 分频、4 分频和 8 分频的 Verilog 实现并且学习 generate 语法功能的应。 2 程序设计思路 1&#xff09;整数倍分频&#xff0c;为 2、4、8&#xff0c;这种 2^n 次方倍数倍数关系的…
阅读更多...
记一次DateTimeFormat注解的坑

记一次DateTimeFormat注解的坑

记一次DateTimeFormat注解的坑 背景&#xff1a;在用Echarts做图表时&#xff0c;前端传两个日期参数&#xff0c;获取日期区间的图表数据。想遵循RESTful风格&#xff0c;所以使用get请求获取date参数。前端读取当前日期&#xff0c;将七天前日期和当前日期作为参数传给后端&…
阅读更多...
享元模式介绍

享元模式介绍

目录 一、享元模式介绍 1.1 享元模式定义 1.2 享元模式原理 1.2.1 享元模式类图 1.2.2 模式角色说明 1.2.3 示例代码 二、享元模式的应用 2.1 需求说明 2.2 需求实现 2.2.1 类图 2.2.2 具体实现 2.2.2.1 抽象享元类 2.2.2.2 共享享元类-白色棋子 2.2.2.3 共享享元…
阅读更多...
JAVA SECS发送Report C#处理SECS Report SECS发送事件资料大全 S6F11 建立通讯S1F13

JAVA SECS发送Report C#处理SECS Report SECS发送事件资料大全 S6F11 建立通讯S1F13

发送S6F11非常简单&#xff0c;只需5~6行代码&#xff0c;最核心是代码清晰易懂。 任何人都可以一看就能上手&#xff0c;如果说用代码可读性作为不可替代性的壁垒就无话可说了。 private void buttonS6F11_Click(object sender, EventArgs e) {int nTransaction 0;// 数据部…
阅读更多...
Rust之旅 - Rust概念、Windows安装、环境配置

Rust之旅 - Rust概念、Windows安装、环境配置

&#x1f339;作者主页&#xff1a;青花锁 &#x1f339;简介&#xff1a;Java领域优质创作者&#x1f3c6;、Java微服务架构公号作者&#x1f604; &#x1f339;简历模板、学习资料、面试题库、技术互助 &#x1f339;文末获取联系方式 &#x1f4dd; 系列专栏目录 [Java项目…
阅读更多...
【SpringBoot】SpringBoot 项目初始化方法

【SpringBoot】SpringBoot 项目初始化方法

github 搜索 springboot 模板 github 搜索 springboot 模板&#xff0c;拉取现成代码。 SpringBoot 官方的模板生成器 SpringBoot 官方的模板生成器&#xff08;https://start.spring.io/&#xff09; 在 IDEA 开发工具中生成 这里我修改成阿里的镜像主要是要使用 Java8。 …
阅读更多...
制作一个Python聊天机器人

制作一个Python聊天机器人

我们学习一下如何使用 ChatterBot 库在 Python 中创建聊天机器人&#xff0c;该库实现了各种机器学习算法来生成响应对话&#xff0c;还是挺不错的 什么是聊天机器人 聊天机器人也称为聊天机器人、机器人、人工代理等&#xff0c;基本上是由人工智能驱动的软件程序&#xff0…
阅读更多...
最多购买宝石数目 - 华为OD统一考试

最多购买宝石数目 - 华为OD统一考试

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C 题目描述 橱窗里有一排宝石&#xff0c;不同的宝石对应不同的价格&#xff0c;宝石的价格标记为 gems[i],0<i<n, n gems.length 宝石可同时出售0个或多个&#xff…
阅读更多...
test2测试

test2测试

欢迎关注博主 Mindtechnist 或加入【Linux C/C/Python社区】一起探讨和分享Linux C/C/Python/Shell编程、机器人技术、机器学习、机器视觉、嵌入式AI相关领域的知识和技术。 磁盘满的本质分析 专栏&#xff1a;《Linux从小白到大神》 | 系统学习Linux开发、VIM/GCC/GDB/Make工具…
阅读更多...
如何发挥 Sketch在UI和UX设计中的作用

如何发挥 Sketch在UI和UX设计中的作用

Sketch是一款专业的矢量图形设计软件&#xff0c;主要应用于UI设计、移动应用设计、Web设计等领域。假如你是一个交互设计师或UI设计师&#xff0c;那么你一定知道Sketch这一强大的矢量设计软件&#xff1b;如果你使用了Photoshop&#xff0c;那么在你接触到Sketch之后&#xf…
阅读更多...
物联网协议Coap之C#基于Mozi的CoapServer实现解析

物联网协议Coap之C#基于Mozi的CoapServer实现解析

目录 前言 一、C#的Coap Server实现 1、CoapServer相关类 2、主要类解析 3、资源控制器定义 4、ResourceManager管理器 二、CoapServer生命周期 1、Server创建代码 2、服务端创建 3、绑定endpoint 4、准备接收请求 总结 前言 在之前的关于物联网协议的介绍中&#…
阅读更多...
最新文章

Copyright @ 2022~2023