C++/数据结构：AVL树

目录

一、AVL树的概念

二、AVL树的实现

2.1节点定义

 2.2节点插入

三、AVL树的旋转

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

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

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

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

四、AVL树的性能

一、AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M. A delson- V elskii
和E.M. L andis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
$O(log_2 n)$，搜索时间复杂度logn。

二、AVL树的实现

2.1节点定义

template <class K,class V>
class AVLtreeNode
{
	AVLtreeNode<K, V>* _left;
	AVLtreeNode<K, V>* _right;
	AVLtreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int bf;
	AVLtreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, bf(0)
	{}
};

 2.2节点插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
AVL树的插入过程可以分为两步：
1. 按照二叉搜索树的方式插入新节点
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的平衡因子违反平衡树的性质，需要对其进行旋转处理 
bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}			
		}

		cur = new Node(kv);
		if (parent->_kv.first>cur->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		} 
		cur->_parent = parent;

		//调整avl树的结构，处理parent的平衡因子
		while (parent)
		{
			if (parent->left == cur)
			{
				parent->bf--;
			}
			else if (parent->right == cur)
			{
				parent->bf++;
			}

			//不断向上更改avl树中的bf平衡因子
			if (parent->_bf == 1 || parent->_bf == -1)
			{
				//更新去上面的父节点的bf
				parent = parent->_parent;
				cur = cur->parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转处理
				//单旋
				if (parent->_bf == 2 && cur->_bf == 1)//右边高 
				{
					RotateL(parent);//左单旋
				}
				else if (parent->_bf == -2 && cur->_bf == -1)//左边高
				{
					RotateR(parent);//右单旋
				}
				//双旋处理
				else if (parent->_bf==-2&&cur->_bf==1)//左边高的右边高,先左旋再右旋
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent)//右边高的左边高，先右旋再左旋
				}
				else
				{
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

三、AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

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

上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层，即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
1. 30节点的右孩子可能存在，也可能不存在。
2. 60可能是根节点，也可能是子树如果是根节点，旋转完成后，要更新根节点如果是子树，可能是某个节点的左子树，也可能是右子树。 
void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* pparent = parent->_parent;

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

		subL->_right = parent;
		parent->_parent = subL;

		if (pparent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left == subL;
			}
			else
			{
				pparent->_right == subL;
			}
			subL->_parent = pparent;
		}
		subL->_bf = parent->_bf = 0;
		return true;
	}
	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;
			subLR->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)//新增节点在左
		{
			parent->_bf = 1;
			subLR->_bf = 0;
			subL->_bf = 0 ;
		}
		else if (bf == 0)//本身就是新增节点直接导致出现左边高的右边高
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

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

和右单旋的思路以及实现方式大相径庭。只需略微改动。

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

		Node* pparent = parent->_parent;
		parent->right = subRL;
		if(subRL)
		subRL->_parent = parent;

		subR->left = parent;
		parent->_parent = subR;

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

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

将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再
考虑平衡因子的更新。 
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;
			subLR->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)//新增节点在左
		{
			parent->_bf = 1;
			subLR->_bf = 0;
			subL->_bf = 0 ;
		}
		else if (bf == 0)//本身就是新增节点直接导致出现左边高的右边高
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

3.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)
		{
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
总结：
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR。
当pSubR的平衡因子为1时，执行左单旋。
当pSubR的平衡因子为-1时，执行右左双旋。
2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL。
当pSubL的平衡因子为-1是，执行右单旋。
当pSubL的平衡因子为1时，执行左右双旋。
旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。

四、AVL树的性能

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不 错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

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

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

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

相关文章

数据结构篇十：红黑树

数据结构篇十：红黑树

文章目录 前言1. 红黑树的概念2. 红黑树的性质3. 红黑树节点的定义4. 红黑树的插入4.1 情况一&#xff1a; cur为红&#xff0c;p为红&#xff0c;g为黑&#xff0c;u存在且为红4.2 情况二: cur为红&#xff0c;p为红&#xff0c;g为黑&#xff0c;u不存在/u存在且为黑。4.2.1 …
阅读更多...
C++：内存管理|new和delete

C++：内存管理|new和delete

创作不易&#xff0c;感谢三连支持&#xff01; 一、内存分布 为什么需要内存管理呢&#xff1f;&#xff1f;因为我们在程序的运行过程中会需要各种各样的数据&#xff0c;而我们根据数据的不同存储在不同的区域里面&#xff0c;是为了更高效地处理数据。而C语言相比Java来说…
阅读更多...
Docker与虚拟机比较

Docker与虚拟机比较

在对比Docker和虚拟机前&#xff0c;先简单了解下虚拟化&#xff0c;明确Docker和虚拟机分别对应的虚拟化级别&#xff0c;然后对Docker和虚拟机进行比较。需要注意的是&#xff0c;Docker和虚拟机并没有什么可比性&#xff0c;而是Docker使用的容器技术和虚拟机使用的虚拟化技…
阅读更多...
Linux 基础之 sar 工具详解

Linux 基础之 sar 工具详解

文章目录 一、前言二、配置说明三、使用说明&#xff08;一&#xff09;sar语法&#xff08;二&#xff09;sar选项&#xff08;三&#xff09;示例示例1示例2示例3示例4示例5示例6示例7示例8示例9示例10其他示例11其他示例12用于排查性能常用的命令 一、前言 sar(System Acti…
阅读更多...
【无标题】TMGM官网平台切尔西足球俱乐部合作

【无标题】TMGM官网平台切尔西足球俱乐部合作

TMGM作为一家在三大洲均设有办事处的行业领导者&#xff0c;TMGM 被视为可靠的差价合约交易提供商&#xff0c;其重点是监管合规、技术创新与他联系➕&#x1f6f0;️TMGM818卓越的客户服务。 切尔西足球俱乐部在亚太地区拥有庞大的球迷群体&#xff0c;并在该地区建立了多种亚…
阅读更多...
Java中==与equals()的区别

Java中==与equals()的区别

关于“对比”类型的面试题，建议回答时包括： 多个对比项有什么相同/相似之处 多个对比项的区别 在应用中应该如何选取 可能的话，加入一些扩展。 变量与对象是2个不同的概念 Object a = new Object(); 以上代码中的a就是变量，在内存中实际存在的数据就是对象。 所有引…
阅读更多...
五大跨平台桌面应用开发框架：Electron、Tauri、Flutter等

五大跨平台桌面应用开发框架：Electron、Tauri、Flutter等

hello&#xff0c;我是贝格前端工场&#xff0c;本次介绍跨平台开发的框架&#xff0c;欢迎大家评论、点赞。 一、什么是跨平台桌面应用开发框架 跨平台桌面应用开发框架是一种工具或框架&#xff0c;它允许开发者使用一种统一的代码库或语言来创建能够在多个操作系统上运行的…
阅读更多...
使用 frp 实现 windows 远程

使用 frp 实现 windows 远程

前提条件&#xff1a; 拥有一台公网 ip 的服务器&#xff1b; 被远程控制的 windows 系统为专业版&#xff08;家庭版的其它方式没有尝试过&#xff09;&#xff1b; frp 下载包及使用说明 frp release 包的下载网址&#xff1a;https://github.com/fatedier/frp/releases 中…
阅读更多...
人工智能基础——模型部分：模型介绍、模型训练和模型微调 ！！

人工智能基础——模型部分：模型介绍、模型训练和模型微调 ！！

文章目录 前言 一、什么是模型 二、什么是模型训练 三、什么是模型微调 前言 本文将从什么是模型&#xff1f;什么是模型训练&#xff1f;什么是模型微调&#xff1f;三个问题&#xff0c;来展开介绍人工智能基础的模型部分。 模型族谱 一、什么是模型 模型是一个函数&#x…
阅读更多...
set和multiset

set和multiset

1. set基本概念 简介&#xff1a; 所有元素都会在插入时自动被排序 本质&#xff1a; set/multiset属于关联式容器&#xff0c;底层结构是用二叉树实现。 set和multiset区别&#xff1a; set不允许容器中有重复的元素 multiset允许容器中有重复的元素 2. set构造和赋值 功能描述…
阅读更多...
MySql安全加固：配置不同用户不同账号禁止使用旧密码禁止MySql进程管理员权限

MySql安全加固：配置不同用户不同账号禁止使用旧密码禁止MySql进程管理员权限

MySql安全加固&#xff1a;配置不同用户不同账号&禁止使用旧密码&禁止MySql进程管理员权限 1.1 检查是否配置不同用户不同账号1.2 检查是否禁止使用旧密码1.3 禁止MySql进程管理员权限 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496…
阅读更多...
uview2中上传文件和若依前后端分离配合的代码

uview2中上传文件和若依前后端分离配合的代码

uview2中的上传文件需要配合着自己后端的上传的代码 uview2 代码&#xff1a; uploadFilePromise(url) {return new Promise((resolve, reject) > {// 后续自己封装let a uni.uploadFile({//自己的请求路径url: that.$baseURL /uploadAvater, //上传的文件filePath: tha…
阅读更多...
4.1.CVAT——目标检测的标注详细步骤

4.1.CVAT——目标检测的标注详细步骤

文章目录 1. 进入任务1. 创建任务2. 已创建的task3. 进入标注界面 2. 选择标注类型2.1 选择标注类型2.2 进行标注2.3 遮挡 2.快捷键3.导出标注结果 1. 进入任务 登录后会看到如下图界面&#xff0c;CVAT的标注最小单位是Task&#xff0c;每个Task为一个标注任务。点击Task按钮…
阅读更多...
数据安全无忧，SQL Server 2014数据库定时备份解密

数据安全无忧，SQL Server 2014数据库定时备份解密

一、为什么要执行数据库定时备份 在SQL Server数据库中&#xff0c;完整备份和差异备份是常见的备份策略组合。它们的目的是提供数据的备份和恢复能力&#xff0c;以确保数据的可靠性和可恢复性。 完整备份&#xff08;Full Backup&#xff09; 完整备份是对整个数据库进行备份…
阅读更多...
为什么要在业务系统中引入大宽表？

为什么要在业务系统中引入大宽表？

在高度系统化驱动的业务中&#xff0c;查看业务报表已经是一个很常见的需求了。在分工非常明确的大型企业里&#xff0c;往往有专门的数据分析团队 BI 或者数据开发团队&#xff0c;他们能够胜任此类需求&#xff08;但也未必是轻松的&#xff0c;或者说高效的&#xff09;。 …
阅读更多...
‘conda‘ 不是内部或外部命令，也不是可运行的程序 或批处理文件

‘conda‘ 不是内部或外部命令，也不是可运行的程序 或批处理文件

如果你在运行 conda 命令时收到了 ‘conda’ 不是内部或外部命令&#xff0c;也不是可运行的程序或批处理文件。 的错误消息&#xff0c;这可能意味着 Anaconda 并没有正确地添加到你的系统路径中。 1.你可以尝试手动添加 Anaconda 到系统路径中。以下是在 Windows 系统上添加…
阅读更多...
前端按钮动画

前端按钮动画

效果示例 代码示例 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevic…
阅读更多...
自测-2 素数对猜想

自测-2 素数对猜想

文章预览&#xff1a; 题目算法 题目 算法 本题用python写不能用一般的算法去求会超时&#xff0c;应该采用欧拉素数筛选法去求&#xff0c;算法复杂度为O&#xff08;n&#xff09;比其他的算法优秀的多&#xff0c; 算法思想: &#xff08;1&#xff09;我们安排一个数组或者…
阅读更多...
AJAX 学习笔记（Day1）

AJAX 学习笔记（Day1）

「写在前面」 本文为黑马程序员 AJAX 教程的学习笔记。本着自己学习、分享他人的态度&#xff0c;分享学习笔记&#xff0c;希望能对大家有所帮助。 目录 0 课程介绍 1 AJAX 入门 1.1 AJAX 概念和 axios 使用 1.2 认识 URL 1.3 URL 查询参数 1.4 常用请求方法和数据提交 1.5 HT…
阅读更多...
华为笔记本自带windows11如何改为win10

华为笔记本自带windows11如何改为win10

目录 一、前言 二、遇到问题 三、问题解决 一、前言 新购买的华为笔记本电脑自带windows11系统&#xff0c;虽然是正版系统&#xff0c;但还是希望能重新装Windows10版本。一是我已经习惯此系统&#xff0c;二是该系统上运行的开发工具比较稳定。 二、遇到问题 说干就干&…
阅读更多...
最新文章

Copyright @ 2022~2023