【C++】AVL树的插入、旋转

目录

  • 一、AVL树介绍
    • 1.1 概念
    • 1.2 定义
  • 二、AVL树的实现
    • 2.1 插入
    • 2.2 旋转
      • 2.2.1 左单旋
      • 2.2.2 右单旋
      • 2.2.3 左右双旋
      • 2.2.4 右左双旋

一、AVL树介绍

1.1 概念

AVL树是高度平衡的二叉搜索树，相比普通的二叉搜索树，它防止了变成单支树的情况。因为AVL树每插入一个新的节点，它都会调整使左右子树的高度差的绝对值不超过1，从而降低了树的高度，提高了搜索效率。

特点：

  • 左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
  • 搜索时间复杂度O( l o g 2 n log_2 n log2​n)
  • 有平衡因子控制高度差：右子树高度减去左子树高度

在这里插入图片描述

1.2 定义

AVL树是三叉链结构，即左孩子指针、右孩子指针和双亲指针，多了一个双亲指针方便找到上一个节点。定义它的数据域，为kv模型的类型。定义平衡因子，作用是记录当前节点的左右子树高度之差。

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;
	pair<K, V> _kv;

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
		, _kv(kv)
	{}
};

二、AVL树的实现

2.1 插入

AVL树的插入过程与二叉搜索树的插入过程是一样的，只不过在此基础上增加了调整节点的平衡因子。所以总结为两个步骤：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子

没标数字的是新插入的节点

在这里插入图片描述
调整平衡因子，首先要从cur和parent入手，即新插入的节点和插入节点的上一个节点。如果插入节点cur是parent的右边，则parent的平衡因子+1；反之，则-1。整个调整过程是一个循环，因为刚开始改变的是下面的平衡因子，上面节点的平衡因子也可能会随之改变。循环条件为parent不为空，还要其他条件可以终止循环，下面细讲。

所以根据parent的平衡因子的值可以分为3步：

  1. parent的平衡因子为0
  2. parent的平衡因子为1或者-1
  3. parent的平衡因子为2或者-2

这里说明下，没有parent的平衡因子可能为3/-3的情况，如果出现了说明之前的树有问题

1️⃣parent的平衡因子为0
此情况说明原来的parent的左边或者右边存在一个节点，新插入的节点在parent没有节点的一侧，parent两边都有节点，平衡因子为0，不影响上面的节点，调整结束，跳出循环。

在这里插入图片描述

2️⃣parent的平衡因子为1或者-1
如果parent的平衡因子为1或者-1，则会影响上面的节点，所以让parent节点转换为它的上一个节点，cur转换为parent，向上更新，以次类推。每次循环还是要经过cur是parent的左边还是右边，才能确定parent的平衡因子是+1还是-1。直到cur为根节点，parent为空时循环结束。
在这里插入图片描述

3️⃣parent的平衡因子为2或者-2
当parent向上更新，到某个节点时(有可能不是根节点)它的平衡因子为2或者-2，这时违背了AVL树的规则，因此要进行处理——旋转，来改变树的高度差，使其左右之树的高度差的绝对值不超过1

下图的树插入节点后要发生旋转
在这里插入图片描述

旋转后，高度差恢复平衡，跳出循环。

总结：
AVL树插入节点要进行调整平衡因子，调整结束有3种：
1.parent为空——已经调整到根节点了
2.parent的平衡因子为0——不影响上面节点
3.旋转后——树恢复平衡状态

代码：

//插入
bool Insert(const pair<K, V>& kv)
{
	//如果根为空
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	//非空
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;//有重复不能插入
		}
	}
	cur = new Node(kv);
	if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;
	//调整平衡因子
	while (parent)
	{
		if (parent->_left == cur)
		{
			parent->_bf--;
		}
		else
		{
			parent->_bf++;
		}
		if (parent->_bf == 0)//不需要修改，直接跳出
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)//向上更新
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)//要旋转
		{
			//旋转有4种情况
			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
			{
				RotateRL(parent);//右左双旋-先右后左
			}
			break;//旋转后跳出
		}
		else
		{
			assert(false);//之前树就有问题
		}
	}
	return true;
}

2.2 旋转

这里就开始详细分析AVL树的旋转了，旋转分为4种情况，有左单旋、右单旋、左右双旋和右左双旋。发生这4种旋转的条件不一样，下面逐个分析：

2.2.1 左单旋

整体思路：cur的左孩子变成parent的右孩子（cur的左孩子可能为空），parent变成cur的左孩子，cur连接原来parent的双亲（有可能原来的parent就是根节点，如果是，cur变成根）

先来简单的图示分析：
在这里插入图片描述
parent是平衡因子为2的节点，cur是平衡因子为1的节点，为调整成平衡，parent要变成cur的左孩子，而在此之前，cur的左孩子要先变成parent的右孩子（上面的图节点较少，所以cur没有左孩子），最终平衡。

通过上面的例子，可以基本了解左单旋的整个过程，下面来较多节点的例子：
在这里插入图片描述
定义两个临时变量，subR指向parent的右孩子，即cur的位置(后面的操作就可以不用cur)，subRL为subR的左孩子。

按照上面的步骤，subRL变成parent的右孩子，parent变成subR的左孩子，定义一个ppnode节点为原来parent的双亲，如果parent是在ppnode的左边，则ppnode的左边连接subR，；反之，则右边连接subR。如果parent原来是根节点，那么根节点就变成subR。最后修改parent和subR的平衡因子，它们的平衡因子都变成了0
在这里插入图片描述

有个问题，旋转有4种情况，怎么知道用哪种呢？其实上面的两种图示已经显示出左单旋的条件。当parent的平衡因子为2，并且cur的平衡因子为1时，要进行的旋转为左单旋。

代码：

//左单旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	//不为空
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subR;
	//处理parent如果为根
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	//不为根，处理与ppnode的连接
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subR;
		}
		else
		{
			ppnode->_right = subR;
		}
		subR->_parent = ppnode;
	}
	//修改平衡因子
	parent->_bf = 0;
	subR->_bf = 0;
}

2.2.2 右单旋

整体思路：cur的右孩子变成parent的左孩子，parent变成cur的右孩子，cur连接原来parent的双亲。

简单图示：
在这里插入图片描述
parent是平衡因子为-2的节点，cur是平衡因子为-1的节点，为调整成平衡，cur的右孩子要先变成parent的右孩子，parent变成cur的右孩子，然后修改平衡因子，最终平衡。

用较多节点的例子来分析：
在这里插入图片描述
定义两个临时变量，subL指向parent的左孩子，subLR指向subL的右孩子。

subLR变成parent的左孩子，parent变成subL的右孩子，定义一个ppnode节点为原来parent的双亲，步骤同左单旋。最后修改parent和subL的平衡因子，它们的平衡因子都变成了0
在这里插入图片描述
通过例子可知，发生右单旋的条件是parent的平衡因子为-2，cur的平衡因子为-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* ppnode = parent->_parent;
	parent->_parent = subL;

	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subL;
		}
		else
		{
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
	//修改平衡因子
	parent->_bf = 0;
	subL->_bf = 0;
}

2.2.3 左右双旋

左右双旋是先左单旋，再右单旋。左单旋的是parent的左子树，右单旋的是包括parent的当前树。既然已经有单旋了，为什么还要双旋呢？如图：
在这里插入图片描述
通过上面例子可知，如果插入的位置与前面(左单旋或者右单旋插入时的位置)不同，只有左或者右旋转不能使树变平衡，因此要进行双旋。

左右双旋的情况主要分为以下3类：
在这里插入图片描述
当插入的节点是subLR时，subLR的平衡因子为0；插入的节点在subLR的左边，subLR的平衡因子为-1，插入的节点在subLR的右边，subLR的平衡因子为1；通过图示可知，发生左右双旋的条件是parent的平衡因子为-2，cur的平衡因子为1。这3种情况经过左右双旋后，subLR的平衡因子都变成0，但是parent和subL的平衡因子是有区别的。

下面来看看3种情况的旋转：
1️⃣插入的新节点是subLR
在这里插入图片描述

2️⃣插入的新节点在subLR的左边
在这里插入图片描述

3️⃣插入的新节点在subLR的右边
在这里插入图片描述

通过上面的图发现，当插入的新节点是subLR，subLR的平衡因子为0，旋转后，subL和parent的平衡因子也为0；插入的新节点在subLR的左边，subLR的平衡因子为-1，旋转后，subL的平衡因子为0，parent的平衡因子为1；插入的新节点在subLR的右边，subLR的平衡因子为1，旋转后，subL的平衡因子为-1，parent的平衡因子为0。

代码：

//左右双旋-先左后右
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;//提前保存原来的bf
	RotateL(subL);
	RotateR(parent);
	//旋转后，不同情况最后的bf会不一样
	subLR->_bf = 0;//确定的
	if (bf == -1)
	{
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 1)
	{
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

2.2.4 右左双旋

右左双旋是先右单旋，再左单旋。右单旋的是parent的右子树，左单旋的是包括parent的当前树。

右左双旋也分为3类：
在这里插入图片描述
当插入的节点是subRL时，subRL的平衡因子为0；插入的节点在subRL的左边，subRL的平衡因子为-1；插入的节点在subRL的右边，subRL的平衡因子为1；通过图示可知，发生右左双旋的条件是parent的平衡因子为2，cur的平衡因子为-1。这3种情况经过右左双旋后，subRL的平衡因子固定都变成了0，但是parent和subL的平衡因子有区别。

下面是3种情况的旋转：
1️⃣插入的新节点是subRL
在这里插入图片描述

2️⃣插入的新节点在subRL的左边
在这里插入图片描述

3️⃣插入的新节点在subRL的右边
在这里插入图片描述

插入的新节点是subRL，subRL的平衡因子为0，旋转后，subR和parent的平衡因子也为0；插入的新节点在subRL的左边，subRL的平衡因子为-1，旋转后，subR的平衡因子为1，parent的平衡因子为0；插入的新节点在subRL的右边，subRL的平衡因子为1，旋转后，subR的平衡因子为0，parent的平衡因子为-1。

代码：

//右左双旋-先右后左
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;
	RotateR(subR);
	RotateL(parent);

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

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

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

相关文章

bash: mysqldump: command not found

bash: mysqldump: command not found

问题&#xff1a;在linux上执行mysql备份的时候&#xff0c;出现此异常 mysqldump命令找不到 解决&#xff1a; 1、找到mysql目录&#xff08;找到mysql可执行命令目录&#xff09; which mysql 有图可知&#xff0c;mysql安装在&#xff1a; /usr1/local/java/mysql 2、my…
阅读更多...
redis 中的八大问题

redis 中的八大问题

前言 在分布式系统中&#xff0c;由于redis分布式锁相对于更简单和高效&#xff0c;成为了分布式锁的首先&#xff0c;被我们用到了很多实际业务场景当中。 但不是说用了redis分布式锁&#xff0c;就可以高枕无忧了&#xff0c;如果没有用好或者用对&#xff0c;也会引来一些意…
阅读更多...
世界的本质是旋转(7) 野路子PSK 接收机上层同步的技巧与缺陷

世界的本质是旋转(7) 野路子PSK 接收机上层同步的技巧与缺陷

上一篇文章里&#xff0c;我们以BPSK为例子&#xff0c;介绍了nPSK&#xff08;n2,4,8&#xff09;波形的接收、解调中的同步技术。 前文阐述的同步技术所工作的对象是复平面的坐标&#xff0c;X轴是实部、Y轴是虚部。当完成时钟、频率同步后&#xff0c;就获得了一串整数&…
阅读更多...
sqlserver中将csv非空间数据(带点坐标)转为空间数据

sqlserver中将csv非空间数据(带点坐标)转为空间数据

1、导入csv数据 2、修改字段shape为空间字段 ALTER TABLE FJPOIHB66 ALTER COLUMN shape geometry;3、空间字段转字符串 UPDATE FJPOIHB66 SET shape geometry::STGeomFromText(CONVERT(nvarchar(254),shape), 4326);4、设置主键字段 5、即可
阅读更多...
Instagram被封了？Ins封号的6个常见原因及防封技巧

Instagram被封了？Ins封号的6个常见原因及防封技巧

现在&#xff0c;Instagram 对于跨境电商和社交媒体营销人员来说十分重要。然而&#xff0c;许多用户发现他们的Instagram刚注册就被封&#xff0c;大家要知道 Instagram 和 Facebook 等其他平台一样&#xff0c;对账户管理的管控机制非常严格&#xff0c;不过&#xff0c;Inst…
阅读更多...
nut-ui组件库icon中使用阿里图标

nut-ui组件库icon中使用阿里图标

1.需求 基本每个移动端组件库都有组件 icon组件 图标组件、 但是很多组件库中并找不到我们需要的图标 这时候 大家有可能会找图标库 最大众的就是iconfont的图标了 2.使用 有很多方式去使用这个东西 比如将再限链接中的css引入 在使用 直接下载图标 symbol 方式 等....…
阅读更多...
【群环域】多项式环基础

【群环域】多项式环基础

目录 一. 多项式环的基本定义 二. 环与多项式环 三. 多项式环的性质 四. 多项式环的次数&#xff08;degree&#xff09; 五. 多变量多项式 六. 多变量多项式环R的同态 一. 多项式环的基本定义 令R代表环&#xff08;Ring&#xff09;&#xff0c;多项式环中x对应的系数…
阅读更多...
【C语言】自定义类型：结构体

【C语言】自定义类型：结构体

1. 结构体类型的声明 1.1 结构体回顾 结构是⼀些值的集合&#xff0c;这些值称为成员变量。结构的每个成员可以是不同类型的变量。 1.1.1 结构的声明 struct tag {member-list; }variable-list; 例如描述⼀个学⽣&#xff1a; struct Stu {char name[20];//名字int age;//年…
阅读更多...
【C语言】strcpy函数的超细节详解（什么是strcpy，如何模拟实现strcpy?）

【C语言】strcpy函数的超细节详解（什么是strcpy，如何模拟实现strcpy?）

目录 一、观察strcpy()库函数的功能与实现 二、模仿实现strcpy()函数 &#x1f50d;优化代码 &#x1f50d;assert断言拦截 &#x1f50d;const修饰常量指针 &#x1f50d;返回值的加入 三、共勉 一、观察strcpy()库函数的功能与实现 首先我们先来观察一下库函数strcpy去实现…
阅读更多...
forward请求转发、include请求转发

forward请求转发、include请求转发

forward请求转发&#xff0c;执行到这里就请求转发去执行Servlet4 include请求转发在执行完Servlet4之后&#xff0c;还会回来执行完。
阅读更多...
五大模型大比拼：Claude3、Gemini、Sora、GPTs与GPT-4的优缺点分析

五大模型大比拼：Claude3、Gemini、Sora、GPTs与GPT-4的优缺点分析

课程安排 学习内容 第一章 2024年AI领域最新技术 1.OpenAI新模型-GPT-5 2.谷歌新模型-Gemini Ultra 3.Meta新模型-LLama3 4.科大讯飞-星火认知 5.百度-文心一言 6.MoonshotAI-Kimi 7.智谱AI-GLM-4 第二章 OpenAI开发者大会后GPT最新技术 1.最新大模型GPT-4 Turbo详细介绍…
阅读更多...
鞋服品牌如何计算门店盈亏平衡？

鞋服品牌如何计算门店盈亏平衡？

在鞋服品牌的运营中&#xff0c;门店盈亏平衡是衡量门店经营效果的重要指标。盈亏平衡点意味着门店在达到这一销售水平时&#xff0c;既能够覆盖所有固定和变动成本&#xff0c;又能实现零利润或零亏损。计算门店盈亏平衡有助于品牌更好地理解门店的经营状况&#xff0c;制定合…
阅读更多...
解决LangChain构建知识向量库的过程中官方API无法自定义文本切割方式的问题-例如按行切分

解决LangChain构建知识向量库的过程中官方API无法自定义文本切割方式的问题-例如按行切分

自定义切分构成知识向量库的文本o(&#xffe3;▽&#xffe3;)ブ 在使用大模型和知识向量库进行问题问答的过程中&#xff0c;由于一些LangChain切分文本功能上的限制影响了模型的回答效果为了解决该问题故诞生此文档&#xff0c;如果有说的不对的&#xff0c;或者想交流的非…
阅读更多...
Vue3中computed、watch、watchEffect的区别

Vue3中computed、watch、watchEffect的区别

三者都是侦听工具&#xff0c;实现的是观察者模式&#xff0c;横向对比 &#xff08;1&#xff09;依赖&#xff1a;指的是响应性依赖&#xff0c;也就是侦听 ref、reactive 这类具有响应性的对象。 &#xff08;2&#xff09;watch&#xff1a;默认情况下&#xff0c;被侦听对…
阅读更多...
Spring AOP常见面试题

Spring AOP常见面试题

目录 一、对于AOP的理解 二、Spring是如何实现AOP的 1、execution表达式 2、annotation 3、基于Spring API&#xff0c;通过xml配置的方式。 4、基于代理实现 三、Spring AOP的实现原理 四、Spring是如何选择使用哪种动态代理 1、Spring Framework 2、Spring Boot 五…
阅读更多...
CUDA入门之统一内存

CUDA入门之统一内存

原文来自CUDA 编程入门之统一内存 &#x1f3ac;个人简介&#xff1a;一个全栈工程师的升级之路&#xff01; &#x1f4cb;个人专栏&#xff1a;高性能&#xff08;HPC&#xff09;开发基础教程 &#x1f380;CSDN主页 发狂的小花 &#x1f304;人生秘诀&#xff1a;学习的本质…
阅读更多...
X64 页表结构

X64 页表结构

PML4&#xff08;Page Map Level 4&#xff09;是x86-64架构中用于管理虚拟内存地址翻译的四级页表结构之一。它是一种树形结构&#xff0c;由多个页目录表&#xff08;Page Directory Pointer Table&#xff0c;PDPT&#xff09;组成&#xff0c;每个PDPT有512个指向下一级页表…
阅读更多...
低功耗DC-DC电压调整器IU5528D

低功耗DC-DC电压调整器IU5528D

IU5528D是一款超微小型,超低功耗,高效率,升降压一体DC-DC调整器。适用于双节,三节干电池或者单节锂电池的应用场景。可以有效的延长电池的使用时间。IU5528D由电流模PWM控制环路&#xff0c;误差放大器&#xff0c;比较器和功率开关等模块组成。该芯片可在较宽负载范围内高效稳…
阅读更多...
1_springboot_shiro_jwt_多端认证鉴权_Shiro入门

1_springboot_shiro_jwt_多端认证鉴权_Shiro入门

1. Shiro简介 Shiro 是 Java 的一个安全框架&#xff0c;它相对比较简单。主要特性&#xff1a; Authentication&#xff08;认证&#xff09;&#xff1a;用户身份识别&#xff0c;通常被称为用户“登录”&#xff0c;即 “你是谁”Authorization&#xff08;授权&#xff…
阅读更多...
webpack-dev-server5.0+ 版本问题

webpack-dev-server5.0+ 版本问题

webpack-dev-server版本选择 在使用webpack-dev-server搭建新项目时&#xff0c;需要依赖node 和webpack以及webpack-cli 这是需要注意各个应用之间的版本问题 通过npm官网查看webpack-dev-server使用的版本依赖对象 先看package.json&#xff0c;可以看到当前的版本 再找到依…
阅读更多...
最新文章

Copyright @ 2022~2023