AVL树详解

目录

AVL树的概念

旋转的介绍

单旋转

双旋转

旋转演示

具体实现

通过高度判断的实现

通过平衡因子判断的实现


AVL树的概念

AVL树是一种自平衡的平衡二叉查找树,它是一种高效的数据结构,可以在插入和删除节点时保持树的平衡,从而保证树的操作时间复杂度能够达到O(log n)。

所谓平衡就是保证每个节点的左右子树的高度差不能超过1。例如

bd8189489ce848318a977ea8ebd479f6.jpeg

对AVL树进行插入或删除操作时,可能会导致某些节点的高度差超过1,即不再平衡。这时就需要进行旋转操作来恢复AVL树的平衡性。所以,AVL树的核心内容就是旋转。

旋转的介绍

一般来讲,我们将旋转类型分为两大类。左-左、右-右类型的为单旋转,左-右、右-左类型的为双旋转。下面是这四种旋转的操作方式。

单旋转

AVL树的单旋转指的是在树的某个节点上进行的一种旋转操作,通过左旋或右旋使该节点成为旋转后的子树的根节点,并使树保持平衡状态。在单旋转过程中,节点的左右子树高度变化不超过1,旋转操作其实是把子树的位置进行调整,使得整棵树的平衡因子尽可能地符合平衡树的要求。

具体来说,如果在某个节点的左子树中插入了一个新节点导致该节点的左子树高度比右子树高度多2,那么就需要在该节点进行一次右旋转操作。右旋转将该节点的左子节点变为子树的根节点,该节点的原父节点成为子树的新根节点的右子节点,子树的其他节点位置不变。

同理,如果在某个节点的右子树中插入了一个新节点导致该节点的右子树高度比左子树高度多2,那么就需要在该节点进行一次左旋转操作。左旋转将该节点的右子节点变为子树的根节点,该节点的原父节点成为子树的新根节点的左子节点,子树的其他节点位置不变。

 具体的图解如下: 

5cb4b4d6000447a7b69892d8ff0b10da.png

图片出处:AVL树的旋转图解和简单实现_avl树旋转-CSDN博客

 单旋转的过程可以概况为如下的三个步骤(以下图为模型,以单左旋为例):

        1、让k2原本指向k1的指针现在指向k1内侧的节点

        2、让k1原本指向内侧的指针现在指向k2

        3、让原来指向k2的指针现在改为指向k1,并更新各节点的高度

74a2c69e473f46ec9a0b9d2803ffca99.png

双旋转

AVL树的双旋转是指在某个节点的子树中进行两次旋转操作以保持平衡的一种树旋转方式。双旋转包含两种情况:左旋-右旋和右旋-左旋。

具体来说,假设在AVL树的某个节点的左子树中插入了一个新节点,导致该节点的左子树高度比右子树高度多2,但是进行一次右旋转不能转换成平衡状态,此时需要进行左旋-右旋操作。该操作可以分解为两步:

  1. 对该节点的左子节点进行一次左旋转。

  2. 对该节点进行一次右旋转。

左旋转操作会使得该节点的左子节点变为子树的根节点,同时该节点成为新根节点的右子节点,然后对该节点进行右旋转时,子树的根节点发生了变化,新的根节点是之前的左子节点,原本的根节点成为新节点的右子节点,最后使得整棵树重新平衡。

同样的,假如在AVL树的某个节点的右子树中插入了一个新节点,导致该结点的右子树高度比左子树高度多2,但进行一次左旋转不能转换成平衡状态,此时需要进行右旋-左旋操作。该操作可以分成两步:

  1. 对该节点的右子节点进行一次右旋转。

  2. 对该节点进行一次左旋转。

右旋转操作会使得该节点的右子节点变为子树的根节点,同时该节点成为新根节点的左子节点,然后对该节点进行左旋转时,子树的根节点发生了变化,新的根节点是之前的右子节点,原本的根节点成为新节点的左子节点,最后使得整棵树重新平衡。

具体图解如下:

a3965d75ae3d472785c49be89acffefd.png

图片出处:AVL树的旋转图解和简单实现_avl树旋转-CSDN博客


双旋转其实就是两次单旋转,先将内侧的节点通过单旋转“移出来”到外侧。然后再用一次单旋转,最终成为我们想要的平衡状态。

旋转演示

AVL树动画演示

也可以自己尝试:

AVL Tree Visualzation (usfca.edu)icon-default.png?t=N7T8https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

具体实现

通过高度判断的实现

AVL树一个最直接的方式就是每个节点的信息中增加了一个高度信息(Height),每个节点在插入后向上回溯到根,进行高度信息的调整更新,并判断是否要进行旋转。这种实现方式比较直观好想,每次判断是否需要进行旋转的时候就直接判断高度差即可。

如下是一种实现方式(C语言实现,以递归的方式进行插入和回溯,每个节点只有左右孩子两个指针,维护平衡条件的信息是节点的高度),仅供参考。

/* 忽略了相关头文件 */

typedef char ElementType; //暂定节点内容只有单个字符

typedef struct AvlTreeNode
{
	ElementType Data; 
	int Height;
	struct AvlTreeNode* Left;
	struct AvlTreeNode* Right;
}AvlTree; 

int Height(AvlTree* Node)
{
	if (Node == NULL)
		return -1;
	return Node->Height;
}
AvlTree* SingleLeftRotate(AvlTree* k2) //单左旋,LL旋转(k2的由来详见数据结构与算法分析P94)
{
	//旋转节点
	AvlTree* k1 = k2->Left; 
	k2->Left = k1->Right;
	k1->Right = k2;
	//更新高度
	k2->Height = max(Height(k2->Left), Height(k2->Right)) + 1;
	k1->Height = max(Height(k1->Left), Height(k1->Right)) + 1;
	//返回
	return k1;
}
AvlTree* SingleRightRotate(AvlTree* k2) //单右旋,RR旋转(k2的由来详见数据结构与算法分析P94)
{
	//旋转节点
	AvlTree* k1 = k2->Right;
	k2->Right = k1->Left;
	k1->Left = k2; 
	//更新高度
	k2->Height = max(Height(k2->Left), Height(k2->Right)) + 1;
	k1->Height = max(Height(k1->Left), Height(k1->Right)) + 1;
	//返回
	return k1;
}
AvlTree* DoubleLRRotate(AvlTree* k3) //双左右旋,LR旋转(k3的由来详见数据结构与算法分析P95)
{
	/*一次双旋转等于两次单旋转。
	可以理解为先将需要旋转的移至同一方向(即左左、右右这种),然后再用单旋转的方式处理*/
	k3->Left = SingleRightRotate(k3->Left); 
	return SingleLeftRotate(k3);  
}
AvlTree* DoubleRLRotate(AvlTree* k3) //双右左旋,RL旋转(k3的由来详见数据结构与算法分析P95)
{
	/*一次双旋转等于两次单旋转。
	可以理解为先将需要旋转的移至同一方向(即左左、右右这种),然后再用单旋转的方式处理*/
	k3->Right = SingleLeftRotate(k3->Left);
	return SingleRightRotate(k3);
}
AvlTree* InsertElement(AvlTree** root, ElementType data)
{
	//走到空节点(即插入位置),执行插入操作
	if ((*root) == NULL)
	{
		//开辟空间并赋值
		*root = (AvlTree*)calloc(1, sizeof(AvlTree));
		//成功开辟空间
		if ((*root) != NULL)
			(*root)->Data = data; 
		//开辟空间失败
		else	
			puts("heap area is full!");
	} 
	//根节点无内容(值为0),说明为空树,则直接将data插入到根节点
	else if ((*root)->Data == 0) 
	{
		(*root)->Data = data;
	}
	//data比节点内容小,在左侧插入
	else if (data < (*root)->Data) 
	{
		//向左走,并更新左子树内容
		(*root)->Left = InsertElement(&(*root)->Left, data);	
		//判断是否需要旋转
		if (Height((*root)->Left) - Height((*root)->Right) == 2)
		{
			//如果data小于左子树的data,说明是data插入到左子树的左节点,符合单旋转的情况(3个节点都在左侧)
			if (data < (*root)->Left->Data) 
				*root = SingleLeftRotate(*root); //左侧单旋转,并更新节点内容
			//如果data不小于左子树的data,说明是插入到左子树的右节点,是LR型的双旋转情况
			else
				*root = DoubleLRRotate(*root); //左右双旋转,并更新节点内容
		}
	}
	//data比节点内容大,在右侧插入
	else if (data > (*root)->Data) 
	{
		//向右走,并更新左子树内容
		(*root)->Right = InsertElement(&(*root)->Right, data); 
		//判断是否旋转
		if (Height((*root)->Right) - Height((*root)->Left) == 2) 
		{
			//如果data大于右子树的data,说明是data插入到右子树的右节点,符合单旋转的情况(3个节点都在右侧)
			if (data > (*root)->Right->Data) 
				*root = SingleRightRotate(*root);  //右侧单旋转,并更新节点内容
			//如果data不大于右子树的data,说明是插入到右子树的左节点,是RL型的双旋转情况
			else
				*root = DoubleRLRotate(*root);
		}
	}
	//data与节点内容值相同
	else {  /*暂定如果插入的元素内容相同,则什么都不做*/  }
	//最后更新节点高度
	(*root)->Height = max(Height((*root)->Left), Height((*root)->Right)) + 1; 
	//返回
	return *root;
}

通过平衡因子判断的实现

相比通过高度的直观,平衡因子就有些复杂了。这里的平衡因子指的是右子树的高度减左子树的高度,每个节点都有一个平衡因子信息,初始化为0。每次插入节点后也是向上回溯,进行平衡因子的更新调整与判断是否需要旋转,不过这种方式不一定要走到根,如果更新后的平衡因子信息为0,就说明不用再往上调了。

如下是一种实现方式(C++实现,通过迭代循环的方式进行插入和回溯,为了能够不通过递归进行回溯操作,除了基准的左右儿子指针,这种实现方式为每一个节点还为维护了一个双亲指针,维护平衡条件的信息是平衡因子),仅供参考。

/* 忽略了相关头文件 */

// 节点类型
template<typename T>
struct AVLNode
{
	AVLNode(const T& val)
		: _val(val)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}

	T _val;  // 数据内容
	int _bf; // 平衡因子:右高度减左高度
	AVLNode<T>* _left;
	AVLNode<T>* _right;
	AVLNode<T>* _parent;
};

// 树的类型
template<typename T>
class AVLtree
{
	AVLNode<T>* _root = nullptr; // 根节点
public:
	bool insert(const T& val)
	{
		/* 初始情况,树为空 */
		if (_root == nullptr)
		{
			_root = new AVLNode<T>(val);
			return true;
		}

		/* 一般情况,插入数据 */
		AVLNode<T>* pre = nullptr;
		AVLNode<T>* cur = _root;
		// 先找到对应位置
		while (cur)
		{
			// 要插入数据已存在 - 插入失败
			if (val == cur->_val)
				return false;
			// 要插入数据不存在,继续寻找
			pre = cur;
			if (val > cur->_val)
				cur = cur->_right;
			else if (val < cur->_val)
				cur = cur->_left;
		}
		// cur找到了插入位置,new一个新节点并插入
		cur = new AVLNode<T>(val);
		if (val > pre->_val)
			pre->_right = cur;
		else
			pre->_left = cur;
		cur->_parent = pre;

		/* 向上回溯,随之更新平衡因子,并进行旋转调整 */
		while (pre != nullptr)
		{
			// 根据cur的位置,更新父节点的平衡因子信息
			if (cur == pre->_right)
				pre->_bf++;
			else
				pre->_bf--;
			// bf为0或者正负2的情况都退出,所以就合并处理了
			// 因为2这里给限制死了,所以不会出现abs(bf)大于等于3的情况
			if (abs(pre->_bf) != 1)
			{
				if (abs(pre->_bf) == 2)
					rotatenode(pre, cur->_bf);
				break;
			}
			// 没遇到特殊情况,继续向上回溯
			cur = pre;
			pre = cur->_parent;
		}
		return true;
	}
private:
	// 需要旋转节点的情况 - 旋转的4种情况
	void rotatenode(AVLNode<T>* parent, int cur_bf)
	{
		if (parent->_bf == 2)
		{
			if (cur_bf == 1)
				rotateRR(parent);
			else if (cur_bf == -1)
				rotateRL(parent);
		}
		else if (parent->_bf == -2)
		{
			if (cur_bf == 1)
				rotateLR(parent);
			else if (cur_bf == -1)
				rotateLL(parent);
		}
	}

	/* 旋转的4个函数 */
	// 左左单旋(节点都在左侧的情况)
	void rotateLL(AVLNode<T>* parent)
	{		
		// 调整节点位置及父子关系
		AVLNode<T>* cur = parent->_left;
		AVLNode<T>* rchild = cur->_right;
		parent->_left = rchild;
		if (rchild != nullptr)
			rchild->_parent = parent;
		cur->_right = parent;
		// 进行旋转
		AVLNode<T>* super = parent->_parent;
		cur->_parent = super;
		parent->_parent = cur;
		AVLNode<T>*& port = super == nullptr ? _root : (super->_left == parent ? super->_left : super->_right);
		port = cur;
		// 调节平衡因子
		cur->_bf = 0;
		parent->_bf = 0;

	}
	// 右右单旋(节点都在右侧的情况)
	void rotateRR(AVLNode<T>* parent)
	{
		// 调整节点位置及父子关系
		AVLNode<T>* cur = parent->_right;
		AVLNode<T>* lchild = cur->_left;
		parent->_right = lchild;
		if (lchild != nullptr)
			lchild->_parent = parent;
		cur->_left = parent;
		// 进行旋转
		AVLNode<T>* super = parent->_parent;
		cur->_parent = super;
		parent->_parent = cur;
		AVLNode<T>*& port = super == nullptr ? _root : (super->_left == parent ? super->_left : super->_right);
		port = cur;
		// 调节平衡因子
		cur->_bf = 0;
		parent->_bf = 0;
	}
	// 左右双旋
	void rotateLR(AVLNode<T>* parent)
	{
		// 先把里面的节点旋出来,再按照单旋转处理
		AVLNode<T>* cur = parent->_left;
		AVLNode<T>* sub = cur->_right;
		int bf = sub->_bf;
		rotateRR(cur);
		rotateLL(parent);
		// 调整平衡因子
		if (bf == 1)
			cur->_bf = -1;
		else if (bf == -1)
			parent->_bf = 1;
	}
	// 右左双旋
	void rotateRL(AVLNode<T>* parent)
	{
		// 先把里面的节点旋出来,再按照单旋转处理
		AVLNode<T>* cur = parent->_right;
		AVLNode<T>* sub = cur->_left;
		int bf = sub->_bf;
		rotateLL(cur);
		rotateRR(parent);
		// 调整平衡因子
		if (bf == 1)
			parent->_bf = -1;
		else if (bf == -1)
			cur->_bf = 1;
	}
};

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

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

相关文章

vivado时序分析-1

AMD Vivado ™ 集成设计环境 (IDE) 提供了多项报告命令 &#xff0c; 用于验证设计是否满足所有时序约束 &#xff0c; 以及是否准备好加载到应用开发板上。“Report Timing Summary ” &#xff08; 时序汇总报告 &#xff09; 属于时序验收报告 &#xff0c; 等同于 ISE De…

uniapp中picker 获取时间组件如何把年月日改成年月日默认时分秒为00:00:00

如图所示&#xff0c;uniapp中picker组件的日期格式为&#xff1a; 但后端要 2023-11-08 00:00:00格式 如何从2023-11-08转化为 2023-11-08 00:00:00&#xff1a;&#x1f447; const date new Date(e.detail.value);//"2023-11-17" date.setHours(0, 0, 0); // 2…

springboot actuator:开放全部(部分)端点、端点映射、端点保护

目录 开放全部端点&#xff08;不安全&#xff09;&#xff1a; 开放部分端点 端点映射 端口保护 1、 添加Spring Security依赖&#xff1a; 2、Spring Security简单配置类&#xff1a; 3、application.yml配置规则 4、写一个简单的controller 5、简单登录页面 目…

【hcie-cloud】【2】华为云Stack解决方案介绍、缩略语整理 【下】

文章目录 华为文档获取方式、云计算发展背景、坚实基座华为云Stack&#xff0c;政企只能升级首选智能数据湖仓一体&#xff0c;让业务洞见更准&#xff0c;价值兑现更快MRS&#xff1a;一个架构可构建三种数据湖&#xff0c;业务场景更丰富离线数据湖&#xff1a;提供云原生、湖…

强化您的应用安全,从app加固开始

强化您的应用安全&#xff0c;从app加固开始 目录 强化您的应用安全&#xff0c;从app加固开始 摘要 引言 1. 加密和数据保护 2. 代码混淆 3. 防止反编译 4. 安全测试 5. 更新和补丁 6. 权限控制 7. 输入验证和输出过滤 8. 日志记录和监控 9. 安全设计和架构 10.…

GoLong的学习之路(二十二)进阶,语法之并发(go最重要的特点)(channel的主要用法)

这一章是接上一章内容继续&#xff0c;上一章说到协程也就是goroutine&#xff0c;如何使用它&#xff0c;这一张是讲一种数据结构。当然这个章节的数据结构非常重要。可以说这个数据结构就是为了方便协程&#xff0c;才制作出来的。 单纯地将函数并发执行是没有意义的。函数与…

echart宽度100px原因(解决el-tabs里的echarts图表宽度不自适应,只有100px问题)

目录 问题描述产生原因处理方法1.使用echart 的API —— resize()2.使用 v-if 总结 问题描述 项目中在el-tabs下面使用了图表&#xff0c;发现图表的宽度始终只有100px 产生原因 首先echart初始化的组件宽度设置了width: 100%&#xff0c;那么本来这个时候&#xff0c;echar…

Flutter android和ios闪屏页配置

一.概念理解 闪屏页 1.当点击app开始的一瞬间&#xff0c;所呈现出来的页面就是闪屏页。 2.为什么会有闪屏也&#xff0c;由于app启动需要加载代码&#xff0c;这个过程需要耗时&#xff0c;在没有加载完成之前&#xff0c;是看不到app真正的页面。所以app在没有完全加载完时…

计算摄像技术03 - 数字感光器件

一些计算摄像技术知识内容的整理&#xff1a;感光器件的发展过程、数字感光器件结构、数字感光器件的指标。 目录 一、感光器件的发展过程 二、数字感光器件结构 &#xff08;1&#xff09;CCD结构 ① 微透镜 ② 滤光片 ③ 感光层 电荷传输模式 &#xff08;2&#xff09;CMOS结…

nigix安装以及遇到的问题

Nginx配置 nginx双击闪退如何解决 修改配置文件 端口冲突&#xff0c;将端口改为90 Nginx 动静分离&#xff08;前端的代码单独运行&#xff09; 将html文件夹里面的东西放到nginx里面的HTMl文件夹里面 负载均衡&#xff08;轮询&#xff0c;权重&#xff0c;哈希&#xff…

三数之和(双指针)

15. 三数之和 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三…

企业如何落地搭建商业智能BI系统

随着新一代信息化、数字化技术的应用&#xff0c;引发了新一轮的科技革命&#xff0c;现代化社会和数字化的联系越来越紧密&#xff0c;数据也变成继土地、劳动力、资本、技术之后的第五大生产要素&#xff0c;这一切都表明世界已经找准未来方向&#xff0c;前沿科技也与落地并…

数据库 高阶语句

目录 数据库 高阶语句 使用select 语句&#xff0c;用order by来对进行排序 区间判断查询和去重查询 如何对结果进行分组查询group by语句 limit 限制输出的结果记录&#xff0c;查看表中的指定行 通配符 设置别名&#xff1a;alias 简写就是 as 使用select 语句&#x…

CVE-2023-0179-Nftables整型溢出

前言 Netfilter是一个用于Linux操作系统的网络数据包过滤框架&#xff0c;它提供了一种灵活的方式来管理网络数据包的流动。Netfilter允许系统管理员和开发人员控制数据包在Linux内核中的处理方式&#xff0c;以实现网络安全、网络地址转换&#xff08;Network Address Transl…

19、Flink 的Table API 和 SQL 中的自定义函数及示例(3)

Flink 系列文章 1、Flink 部署、概念介绍、source、transformation、sink使用示例、四大基石介绍和示例等系列综合文章链接 13、Flink 的table api与sql的基本概念、通用api介绍及入门示例 14、Flink 的table api与sql之数据类型: 内置数据类型以及它们的属性 15、Flink 的ta…

2023年破圈:盘点11个新零售商业模式,永远不再打商业价格战

2023年破圈&#xff1a;盘点11个新零售商业模式&#xff0c;永远不再打商业价格战 前沿&#xff1a;纵观今年互联网各种类型项目&#xff0c;基本都是又短又快&#xff0c;但依然也有风靡的短跑冠军&#xff0c;那么互联网的项目能否跑的长久&#xff0c;是否是商业模式的原因&…

C++ —— map 和 multimap

一、map 1.介绍 1. map是关联容器&#xff0c;它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元 素。 2. 在map中&#xff0c;键值key通常用于排序和惟一地标识元素&#xff0c;而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同&am…

NAT协议

目录 NAT 前言 NAT地址转换表 NAT分类 前言 静态NAT 192.168.1.2访问200.1.1.2执行过程 动态NAT 192.168.1.2访问200.1.1.2执行过程 NAPT 192.168.1.2的5000端口访问200.1.1.2的80端口执行过程 基本命令 配置动态NAPT转换 定义内外网接口 配置NAPT 静态NAPT配置…

Linux基础【Linux知识贩卖机】

偶尔的停顿和修整&#xff0c;对于人生是非常必要的。 --随记 文章目录 Linux目录目录结构磁盘分区相关命令 相对路径和绝对路径 文件权限用户分类umask创建文件权限计算方法粘滞位 总结 Linux目录 目录结构 Linux 操作系统采用了一种层次化的目录结构&#xff0c;常被称为标…

使命担当 守护安全 | 中睿天下获全国海关信息中心感谢信

近日&#xff0c;全国海关信息中心向中睿天下发来感谢信&#xff0c;对中睿天下在2023年网络攻防演练专项活动中的大力支持和优异表现给予了高度赞扬。 中睿天下对此次任务高度重视&#xff0c;紧密围绕全国海关信息中心的行动要求&#xff0c;发挥自身优势有效整合资源&#x…