【C++杂货铺铺】AVL树

目录

🌈前言🌈 

📁 概念

📁 节点的定义

📁 插入

📁 旋转

1 . 新节点插入较高左子树的左侧---左左：右单旋

2. 新节点插入较高右子树的右侧---右右：左单旋

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

📁 性能

📁 完整代码

📁 总结

🌈前言🌈 

        欢迎观看本期【C++杂货铺】，这期内容讲解AVL树，包括了什么是AVL树，如何实现AVL树，此外还会分析二叉搜索树的性能。

        学习本期内容之前，需要你对什么是二叉搜索树有一定的了解，如果不会很了解，或忘记可以快速阅览下面这篇文章：

【C++杂货铺】二叉搜索树-CSDN博客

📁 概念

        在二叉搜索树中，规定比节点小的值都放在节点的左边，比几点大的值都放在节点的右边，可以大大缩短查找的效率。

        但是如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率底下。

        因此俄罗斯的两位数学家在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树之差绝对值不超过1(需要对树中节点进行调整)，即可降低树的高度，从而减少平均搜索长度。

 一颗AVL树必须具有以下性质：

        1. 它的左右子树都是AVL树.

        2. 左右子树高度之差（简称平衡因子）的绝对值不超过1( -1  /  0  / 1).

        如果一颗二叉搜索树是高度平衡的，那么它就是AVL树。如果它有n个节点，其高度可以维持在O(log N) ，搜索时间复杂度O(log N)。

📁 节点的定义

template<class T>
struct AVLTreeNode
{
 AVLTreeNode(const T& data)
     : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
 , _data(data), _bf(0)
 {}
 AVLTreeNode<T>* _pLeft;   // 该节点的左孩子
 AVLTreeNode<T>* _pRight;  // 该节点的右孩子
 AVLTreeNode<T>* _pParent; // 该节点的双亲
 T _data;
 int _bf;                  // 该节点的平衡因子
};

📁 插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。

那么 AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点

2. 调整节点的平衡因子

bool Insert(const T& data)
{
	// 1. 先按照二叉搜索树的规则将节点插入到AVL树中

	// 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否
	破坏了AVL树的平衡性

	 /*
	 pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent
	 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
	  1. 如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可
	  2. 如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可
	  
	 此时：pParent的平衡因子可能有三种情况：0，正负1， 正负2
	  1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整
	成0，此时满足
	     AVL树的性质，插入成功
	  2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更
	新成正负1，此
	     时以pParent为根的树的高度增加，需要继续向上更新
	  3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进
	行旋转处理
	 */
	while (pParent)
	{
		// 更新双亲的平衡因子
		if (pCur == pParent->_pLeft)
			pParent->_bf--;
		else
			pParent->_bf++;
		// 更新后检测双亲的平衡因子
		if (0 == pParent->_bf)
		{
			break;
		}
		else if (1 == pParent->_bf || -1 == pParent->_bf)
		{
			pCur = pParent;
			pParent = pCur->_pParent;
		}
		else
		{
            //根据不同情形，进行旋转
		    ...
		}
	}
	return true;
}

📁 旋转

1 . 新节点插入较高左子树的左侧---左左：右单旋

void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;

parent->_left = subLR;
if (subLR)
	subLR->_parent = parent;

subL->_right = parent;

Node* pparent = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
	_root = subL;
	_root->_parent = nullptr;
}
else
{
	if (parent == pparent->_right)
	{
		pparent->_right = subL;
	}
	else
	{
		pparent->_left = subL;
	}
	subL->_parent = pparent;

}
			
subL->_bf = parent->_bf = 0;
}

2. 新节点插入较高右子树的右侧---右右：左单旋

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;

	subR->_left = parent;
	Node* pparent = parent->_parent;
	parent->_parent = subR;

	if (parent == _root)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == pparent->_right)
		{
			pparent->_right = subR;
		}
		else
		{
			pparent->_left = subR;
		}
		subR->_parent = pparent;

	}
			
	subR->_bf = parent->_bf = 0;
}

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	int bf = subLR->_bf;

	RotateL(parent->_left);
	RotateR(parent);

	if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if(bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == 0)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

//右左单旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
			
	int bf = subRL->_bf;

	RotateR(parent->_right);
	RotateL(parent);

	if (bf == 1)
	{
		subRL->_bf = 0;
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == -1)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if(bf == 0)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}


Node* _root = nullptr;
};

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

        1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

        2. 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确

📁 性能

        AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这 样可以保证查询时高效的时间复杂度，即log2 N。但是如果要对AVL树做一些结构修改的操 作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时， 有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数 据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。


📁 完整代码

template<class T>
struct AVLTreeNode
{
	typedef AVLTreeNode<T> Node;

	AVLTreeNode(const T& val = T())
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _val(val)
		, _bf(0)
	{}

	Node* _left;
	Node* _right;
	Node* _parent;
	T _val;
	//平衡因子
	int _bf;
};

template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:

	//插入
	bool Insert(const T& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(val);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_val> val)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_val < val)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(val);
		if (parent->_val < val)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//调整平衡因子
		while (parent)
		{
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//ROTATE

				//1. 右单旋
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}

				//2. 左单旋
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}

				//3. 左右单旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}

				//4. 右左单旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
			return true;
	}

	//遍历
	void Inorder()
	{
		_Inorder(_root);
	}

	//判断是否是平衡二叉树
	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	int Height()
	{
		return _Height(_root);
	}

protected:
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		return max(_Height(root->_right), _Height(root->_left)) + 1;
	}

	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;

		int leftsize = _Height(root->_left);
		int rightsize = _Height(root->_right);

		//检查右子树 - 左子树 < 2
		if (abs(rightsize - leftsize) >= 2)
		{
			return false;
		}

		//检查平衡因子是否正确
		if (rightsize - leftsize != root->_bf)
			return false;

		return _IsBalance(root->_right)
			&& _IsBalance(root->_left);
	}

	void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_val << endl;
		_Inorder(root->_right);
	}

	//左单旋
		void RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;

			parent->_right = subRL;
			if (subRL)
				subRL->_parent = parent;

			subR->_left = parent;
			Node* pparent = parent->_parent;
			parent->_parent = subR;

			if (parent == _root)
			{
				_root = subR;
				_root->_parent = nullptr;
			}
			else
			{
				if (parent == pparent->_right)
				{
					pparent->_right = subR;
				}
				else
				{
					pparent->_left = subR;
				}
				subR->_parent = pparent;

			}
			
			subR->_bf = parent->_bf = 0;
		}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;

		Node* pparent = parent->_parent;
		parent->_parent = subL;
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == pparent->_right)
			{
				pparent->_right = subL;
			}
			else
			{
				pparent->_left = subL;
			}
			subL->_parent = pparent;

		}
			
		subL->_bf = parent->_bf = 0;
	}

	//左右单旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if(bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	//右左单旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
			
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 1)
		{
			subRL->_bf = 0;
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (bf == -1)
		{
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else if(bf == 0)
		{
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}


	Node* _root = nullptr;
};

📁 总结

        以上就是本期【C++杂货铺】的主要内容了，主要验证了什么是AVL树，即一颗绝对平衡的二叉搜索树，通过平衡因子进行旋转平衡。展示了AVL树的模拟实现代码，深入理解了AVL树。

        最后，如果感觉本期内容对你有帮助，欢迎点赞，收藏，关注。Thanks♪(･ω･)ﾉ

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

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

相关文章

57 读取/写出/读取 文件的过程的调试

57 读取/写出/读取 文件的过程的调试

前言 问题来自于文章 请教文件读写问题 请教文件读写问题 - 内核源码-Chinaunix vim 编辑文件, 实际上删除了原有的文件建立了一个新的文件? Ls –ail . 查看 inode 编号不一样了 这里主要是 调试一下 这一系列流程 测试用例 就是一个程序, 读取 1.txt 两次, 两次之间间隔…
阅读更多...
49. UE5 RPG 使用Execution Calculations处理对目标造成的最终伤害

49. UE5 RPG 使用Execution Calculations处理对目标造成的最终伤害

Execution Calculations是Unreal Engine中Gameplay Effects系统的一部分&#xff0c;用于在Gameplay Effect执行期间进行自定义的计算和逻辑操作。它允许开发者根据特定的游戏需求&#xff0c;灵活地处理和修改游戏中的属性&#xff08;Attributes&#xff09;。 功能强大且灵…
阅读更多...
国内智能搜索工具实战教程

国内智能搜索工具实战教程

大家好，我是herosunly。985院校硕士毕业，现担任算法研究员一职，热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名，CCF比赛第二名，科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…
阅读更多...
C++新特性-线程

C++新特性-线程

主要内容 thread、condition、mutexatomicfunction、bind使用新特性实现线程池&#xff08;支持可变参数列表&#xff09;异常协程其他 1 C11多线程thread 重点&#xff1a; join和detach的使用场景thread构造函数参数绑定c函数绑定类函数线程封装基础类互斥锁mutexconditi…
阅读更多...
网络基础-Telnet协议

网络基础-Telnet协议

Telnet&#xff08;Telecommunication Network&#xff09;是一种基于文本的远程终端协议&#xff0c;允许用户通过网络连接到远程计算机&#xff0c;并在远程计算机上执行命令&#xff1b;它使用TCP作为传输层协议&#xff0c;并依赖于网络连接在客户端和服务器之间进行通信&a…
阅读更多...
FPGA SDRAM读写控制器

FPGA SDRAM读写控制器

感谢邓堪文大佬 &#xff01; SDRAM 同步动态随机存取内存&#xff08;synchronousdynamic randon-access menory&#xff0c;简称SDRAM&#xff09;是有一个同步接口的动态随机存取内存&#xff08;DRAM&#xff09;。通常DRAM是有一个异步接口的&#xff0c;这样它可以随时响…
阅读更多...
计算机毕业设计 | vue+springboot调查问卷管理系统(附源码)

计算机毕业设计 | vue+springboot调查问卷管理系统(附源码)

1&#xff0c;研究目的 在进入21世纪以后&#xff0c;互联网得到了蓬勃的发展&#xff0c;电子问卷调查也开始逐渐流行起来。传统纸质问卷和电子问卷相比较后&#xff0c;传统问卷还存在很多弊端&#xff1a; 问卷分发起来比较困难&#xff0c;并且分发试卷耗费大量的金钱和时…
阅读更多...
基于STC12C5A60S2系列1T 8051单片机实现一主单片机给多个从单片机发送数据的串口通信功能

基于STC12C5A60S2系列1T 8051单片机实现一主单片机给多个从单片机发送数据的串口通信功能

基于STC12C5A60S2系列1T 8051单片机实现一主单片机给多个从单片机发送数据的串口通信功能 STC12C5A60S2系列1T 8051单片机管脚图STC12C5A60S2系列1T 8051单片机串口通信介绍STC12C5A60S2系列1T 8051单片机串口通信的结构基于STC12C5A60S2系列1T 8051单片机串口通信的特殊功能寄…
阅读更多...
基于深度学习神经网络的AI图像PSD去雾系统源码

基于深度学习神经网络的AI图像PSD去雾系统源码

第一步&#xff1a;PSD介绍 以往的研究主要集中在具有合成模糊图像的训练模型上&#xff0c;当模型用于真实世界的模糊图像时&#xff0c;会导致性能下降。 为了解决上述问题&#xff0c;提高去雾的泛化性能&#xff0c;作者提出了一种Principled Synthetic-to-real Dehazing (…
阅读更多...
STC8增强型单片机开发【LED呼吸灯(PWM)⭐⭐】

STC8增强型单片机开发【LED呼吸灯(PWM)⭐⭐】

目录 一、引言 二、硬件准备 三、PWM技术概述 四、电路设计 五、代码编写 EAXSFR&#xff1a; 六、编译与下载 七、测试与调试 八、总结 一、引言 在嵌入式系统开发中&#xff0c;LED呼吸灯是一种常见的示例项目&#xff0c;它不仅能够展示PWM&#xff08;脉冲宽度调制…
阅读更多...
2024 cleanmymac有没有必要买呢，全反面分析

2024 cleanmymac有没有必要买呢，全反面分析

在使用mac时&#xff0c;小编遇到了运行内存不足、硬盘空间不足的情况。遇到这种情况&#xff0c;我们可以借助经典的电脑深度清理软件——CleanMyMac X&#xff0c;清理不常用的软件和系统垃圾&#xff0c;非常好用&#xff01;不过&#xff0c;有许多网友发现CleanMyMac X有免…
阅读更多...
SQLite利用事务实现批量插入（提升效率）

SQLite利用事务实现批量插入（提升效率）

在尝试过SQLite批量插入一百万条记录&#xff0c;执行时长高达20多分钟后&#xff0c;就在想一个问题&#xff0c;这样的性能是不可能被广泛应用的&#xff0c;更不可能出现在真实的生产环境中&#xff0c;那么对此应该如何优化一下呢&#xff1f; 首先分析一下批量插入的逻辑 …
阅读更多...
社区送水小程序软件开发

社区送水小程序软件开发

uni-app框架&#xff1a;使用Vue.js开发跨平台应用的前端框架&#xff0c;编写一套代码&#xff0c;可编译到Android、小程序等平台。 框架支持:springboot/Ssm/thinkphp/django/flask/express均支持 前端开发:vue.js 可选语言&#xff1a;pythonjavanode.jsphp均支持 运行软件…
阅读更多...
端午节线上活动方案怎么写？

端午节线上活动方案怎么写？

一年一端午&#xff0c;一岁一安康。 如果您想组织端午活动&#xff0c;却不知道如何安排&#xff0c;可以看看何策网&#xff0c;有很多案例参考&#xff0c;仿造模板修改即可。 下面分享一个线上端午节活动策划方案&#xff0c;希望能帮到你&#xff01; 端午节作为祭祖祈…
阅读更多...
Remix 集成 MUI

Remix 集成 MUI

Remix 如何接入 MUI 组件库&#xff0c;MUI 官网提供了一个 Remix 接入 MUI 的例子&#xff0c;用的是老的 Remix版本&#xff0c;如何接入新的 Vite 版本呢&#xff1f; 由于 MUI 支持 SSR&#xff0c;只需要改造对应的 Client 和 Server 即可实现。安装 MUI 组件组件库&…
阅读更多...
Java类与对象（一）

Java类与对象（一）

类的定义与使用 在Java中使用关键字class定义一个类&#xff0c;格式如下&#xff1a; class 类名{// 成员变量/字段/属性//成员方法/行为 }Java中类和c语言中的结构体有点类似&#xff0c; 在Java中类名一般采用大驼峰&#xff08;每个首字母大写&#xff09;的形式&#xf…
阅读更多...
Java SE基础知识(12)

Java SE基础知识(12)

知识梳理&#xff1a; package ZoomId;import java.time.ZoneId; import java.time.ZoneOffset; import java.time.ZonedDateTime; import java.util.Set;public class demo1 {public static void main(String[] args) {//获取所有的时区名称Set<String> availableZoneId…
阅读更多...
Ansible剧本playbook之--------Templates 模块、roles角色详细解读

Ansible剧本playbook之--------Templates 模块、roles角色详细解读

目录 一、Templates 模块 1.1准备模板文件并设置引用的变量 1.2修改主机清单文件&#xff0c;使用主机变量定义一个变量名相同&#xff0c;而值不同的变量 1.3编写 playbook 1.4ansible主机远程查看修改参数 1.5验证 二、tags 模块 always应用 三、Roles 模块 3.1ro…
阅读更多...
公司网页设计思路

公司网页设计思路

在当今互联网时代&#xff0c;公司网页设计是一个极为重要的环节。一款精心设计的公司网页可以提升企业形象&#xff0c;增加用户粘性&#xff0c;吸引更多的潜在客户和合作伙伴。下面将为大家介绍一些公司网页设计的思路。 首先&#xff0c;要确立公司网页的整体风格。网页风格…
阅读更多...
适合优化yaml文件编辑效果的.vimrc简单配置

适合优化yaml文件编辑效果的.vimrc简单配置

yaml文件编辑最重要的就是缩进对齐&#xff08;一个tab键对应2个空格&#xff09;&#xff0c;最后加上添加横&#xff0c;纵线的效果 某xx.yaml文件或者xx.yml在vim编辑器中效果如图所示&#xff1a;&#xff1a; 简单的~/.vimrc文件配置内容&#xff1a; vim ~/.vimrc set…
阅读更多...
最新文章

Copyright @ 2022~2023