【数据结构】AVL树（平衡二叉树）

目录

  • 一、AVL树的概念
  • 二、AVL树的节点
  • 三、AVL树的插入
  • 四、AVL树的旋转
    • 1.插入在较高左子树的左侧，使用右单旋
    • 2.插入在较高右子树的右侧，使用左单旋
    • 3.插入较高左子树的右侧，先左单旋再右单旋
    • 4.插入较高右子树的左侧，先右单旋再左单旋
  • 五、AVL树的验证
  • 六、AVL树的删除
  • 七、讲讲AVL树的性能

前言：
在前面我们学习了平衡二叉树，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现，下面我们要学习的AVL树就是处理二叉树自身缺陷的一种方式
在这里插入图片描述

一、AVL树的概念

在平衡二叉树中，如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素的时间复杂度会退化成O(N)。
因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
AVL树可以是一颗空树，如果不是，则它（或者它的任何一颗子树）需要具备以下性质：

  1. 它的左右孩子都是AVL树
  2. 左右子树的高度之差（平衡因子）的绝对值不超过1

如果它有n个节点，它的高度可以保持在log_n，时间复杂度为O(log_n)

二、AVL树的节点

AVL树的节点定义：

template<class K, class V>
struct 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)
		, _bf(0)
		, _kv
	{}
};

三、AVL树的插入

总的来说，AVL树就是在二叉搜索树的基础上加了一个平衡因子，所以AVL树的插入分两步：

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

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	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 (cur == parent->_left)
		{
			parent->_bf--;
		}
		else
		{
			parent->_bf++;
		}
		//没有改变高度，不继续向上更新平衡因子
		if (parent->_bf == 0)
		{
			break;
		}
       // 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者                 -1 ，说明以双亲为根的二叉树的高度增加了一层，因此需要继续向上调整
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		// 双亲的平衡因子为正负2，违反了AVL树的平衡性，需要对以Parent为根的树进行旋转处理
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			// 旋转处理
			.......

			break;
		}
		else
		{
			// 插入之前AVL树就有问题
			assert(false);
		}
	}

	return true;
}

四、AVL树的旋转

当插入一个新节点时，若是平衡因子到了2，则会导致树的不平衡，此时我们就要对这棵树进行旋转操作，使其重新满足AVL树的性质。
根据节点插入位置，AVL树的旋转分四种:

1.插入在较高左子树的左侧，使用右单旋

在这里插入图片描述
上图在插入前，AVL树是平衡的，新节点插入到4的左子树(注意：此处不是左孩子)中，2左子树增加了一层，导致以1为根的二叉树不平衡，要让1平衡，只能将1左子树的高度减少一层，右子树增加一层， 即将左子树往上提，这样1节点转下来，因为1节点比2节点大，只能将其放在2的右子树，而如果2节点有右子树，右子树根的值一定大于2节点，小于1节点，只能将其放在1节点的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：

  1. **2节点的右孩子可能存在，也可能不存在
  2. 1节点可能是根节点，也可能是子树
    如果是根节点，旋转完成后，要更新根节点
    如果是子树，可能是某个节点的左子树，也可能是右子树**

说白了就是把5节点给1节点，再把1节点给2节点，就像是用手把1节点按下来一样（画图理解更佳）

代码：

void RotateR(Node* parent)//以1为旋转点，进行右单旋
{
	Node* subL = parent->_left;//2节点
	Node* subLR = subL->_right;//5节点，也可能没有
	parent->_left = subLR;//5节点给1节点
	if (subLR)
	{
		subLR->_parent = parent;
	}
	subL->_right = parent;
	//1节点可能是根节点，也可能是子树
    // 如果是根节点，旋转完成后，要更新根节点
    // 如果是子树，可能是某个节点的左子树，也可能是右子树
	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;
	}
	//更新平衡因子
	subL->_bf = 0;
	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* ppnode = parent->_parent;
	parent->_parent = subR;

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

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

3.插入较高左子树的右侧，先左单旋再右单旋

在这里插入图片描述

将双旋变成单旋后再旋转，先以2节点为旋转点进行左单旋，然后再以1节点为旋转点进行右单旋，旋转完成后再考虑平衡因子的更新
代码：

void RorareLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	// 旋转之前，60的平衡因子可能是-1/0/1，旋转完成之后，根据情况对其他节点的平衡因子进行调整
	int bf = subLR->_bf;
	// 先对2节点进行左单旋
	RorateL(parent->_left);
	// 再对对1节点进行右单旋
	RotateR(parent);


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

4.插入较高右子树的左侧，先右单旋再左单旋

在这里插入图片描述
和上面的先左再右差不多

总结一下：假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑：

  1. parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR
    当subR的平衡因子为1，左单旋
    当subR的平衡因子为-1，右左单旋

  2. parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL
    当subL的平衡因子为1，左单旋
    当subL的平衡因子为-1，左右单旋

旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新

五、AVL树的验证

如何去验证我们写出来的是AVL树呢？
我们知道，AVL树是在二叉搜索树的基础上加入了控制高度平衡限制，所以对于验证AVL树，我们可以分两步：

  1. 验证是否为二叉搜索树
    对其来一次中序遍历，如果得到一个有序的序列，则为二叉搜索树

  2. 验证是否为平衡树
    (1) 各节点高度差的绝对值不超过1 （2）各节点的平衡因子是否正确

代码：

int _Height(Node* root)
{
	if (root == nullptr)
		return 0;

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

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

bool _IsBalance(Node* root, int& height)
{
	// 空树也是AVL树
	if (root == nullptr)
	{
		height = 0;
		return true;
	}

	int leftHeight = 0, rightHeight = 0;
	if (!_IsBalance(root->_left, leftHeight)
		|| !_IsBalance(root->_right, rightHeight))
	{
		return false;
	}

	if (abs(rightHeight - leftHeight) >= 2)
	{
		cout << root->_kv.first << "不平衡" << endl;
		return false;
	}

	if (rightHeight - leftHeight != root->_bf)
	{
		cout << root->_kv.first << "平衡因子异常" << endl;
		return false;
	}

	height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

	return true;
}

bool IsBalance()
{
	int height = 0;
	return _IsBalance(_root, height);
}

六、AVL树的删除

AVL树也算是二叉搜索树，所以我们可以用二叉搜索树删除节点的方式进行删除（可以看看之前讲的二叉搜索树删除操作：https://blog.csdn.net/liuty0125/article/details/139508094?spm=1001.2014.3001.5501），不过有差别的是，在删除后还要更新删除后的平衡因子，最坏情况可能会更新到根节点，所以一般不会对AVL树进行删除操作

七、讲讲AVL树的性能

先说优点：AVL树是一个平衡的二叉搜索树，它的每个节点的左右子树高度差的绝对值不超过1，因此，哪怕最坏也只是查找高度次，保证了查询时高效的时间复杂度O(log_n)。

但是它的缺陷也很明显：如果我们要对AVL树做一些修改方面的操作时，它的性能就十分低了，因为在修改时我们还要维护它的绝对平衡，旋转的次数比较多，而且在删除时，最坏情况可能会更新到根节点。

所以，如果只是需要一种查询高效且有序的数据结构，且数据个数为静态（不改变），比较适合AVL树，但如果你需要经常修改的话，AVL树可能就不太适合了。

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

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

相关文章

unity基础(五)地形详解

unity基础(五)地形详解

目录 一 创建地形 二 调整地形大小 三 创建相邻地形 四 创建山峰 五 创建树木 七 添加风 八 添加水 简介: Unity 中的基础地形是构建虚拟场景的重要元素之一。 它提供了一种直观且灵活的方式来创建各种地形地貌&#xff0c;如山脉、平原、山谷等。 通过 Unity 的地形…
阅读更多...
C51学习归纳9 --- I2C通讯学习（重点）

C51学习归纳9 --- I2C通讯学习（重点）

首先&#xff0c;我自己学习过以后的直观感觉&#xff0c;通信协议是单片机的灵魂之一&#xff0c;只有规定好了通信协议我们才能够正确的接收到信息&#xff0c;才能实现更加深入的研究。所以这一部分是需要好好学习的。 本节借助一个可存储的芯片AT24C02&#xff0c;进行在I2…
阅读更多...
开源低代码平台技术为数字化转型赋能！

开源低代码平台技术为数字化转型赋能！

实现数字化转型升级是很多企业未来的发展趋势&#xff0c;也是企业获得更多发展商机的途径。如何进行数字化转型&#xff1f;如何实现流程化办公&#xff1f;这些都是摆在客户面前的实际问题&#xff0c;借助于开源低代码平台技术的优势特点&#xff0c;可以轻松助力企业降低开…
阅读更多...
【设计模式】创建型设计模式之 建造者模式

【设计模式】创建型设计模式之 建造者模式

文章目录 一、介绍定义UML 类图 二、用法1 简化复杂对象具体构建过程省略抽象的 Builder 类省略 Director 类 三、用法2 控制对象构造方法、限制参数关系Guava 中使用建造者模式构建 cache 来进行参数校验 一、介绍 定义 建造者模式&#xff0c;将一个复杂的对象的构建过程与…
阅读更多...
互联网应用主流框架整合之SpringMVC初始化及各组件工作原理

互联网应用主流框架整合之SpringMVC初始化及各组件工作原理

Spring MVC的初始化和流程 MVC理念的发展 SpringMVC是Spring提供给Web应用领域的框架设计&#xff0c;MVC分别是Model-View-Controller的缩写&#xff0c;它是一个设计理念&#xff0c;不仅仅存在于Java中&#xff0c;各类语言及开发均可用&#xff0c;其运转流程和各组件的应…
阅读更多...
探索OrangePi AIpro：单板计算机的深度体验之旅

探索OrangePi AIpro：单板计算机的深度体验之旅

准备阶段&#xff1a;环境与资料 在开始我们的探索之旅前&#xff0c;确保您已准备好以下装备&#xff1a; OrangePi AIpro&#xff1a;我们的主角&#xff0c;一台功能强大的单板计算机。Windows 10笔记本电脑&#xff1a;作为我们的辅助工具&#xff0c;用于管理和测试。路…
阅读更多...
FastAPI：在大模型中使用fastapi对外提供接口

FastAPI：在大模型中使用fastapi对外提供接口

通过本文你可以了解到&#xff1a; 如何安装fastapi&#xff0c;快速接入如何让大模型对外提供API接口 往期文章回顾&#xff1a; 1.大模型学习资料整理&#xff1a;大模型学习资料整理&#xff1a;如何从0到1学习大模型&#xff0c;搭建个人或企业RAG系统&#xff0c;如何评估…
阅读更多...
python ---使用python操作mysql ---＞ pymysql

python ---使用python操作mysql ---＞ pymysql

本章内容: 1:能够完成从MySQL中读取出数据; [重点] 查询: execute()、fetchall() 2:能够将数据写入MySQL数据库。 [重点] 插入数据: execute() sql insert into xxx [掌握]pymysql模块的安装 目标&#xff1a;了解如何安装pymysql模块&#xff1f; 当要使用Python和M…
阅读更多...
操作系统复习-存储管理之虚拟内存

操作系统复习-存储管理之虚拟内存

虚拟内存概述 有些进程实际需要的内存很大&#xff0c;超过物理内存的容量。多道程序设计&#xff0c;使得每个进程可用物理内存更加稀缺。不可能无限增加物理内存&#xff0c;物理内存总有不够的时候。虚拟内存是操作系统内存管理的关键技术。使得多道程序运行和大程序运行称…
阅读更多...
永久免费的iPhone，iPad，Mac，iWatch锁屏，桌面壁纸样机生成器NO.105

永久免费的iPhone，iPad，Mac，iWatch锁屏，桌面壁纸样机生成器NO.105

使用这个壁纸样机生成器&#xff0c;生成iPhone&#xff0c;iPad&#xff0c;Mac&#xff0c;iWatch锁屏&#xff0c;桌面壁纸&#xff0c;展示你的壁纸作品&#xff0c;一眼就看出壁纸好不好看&#xff0c;适不适合 资源来源于网络&#xff0c;免费分享仅供学习和测试使用&am…
阅读更多...
【C语言初阶】分支语句

【C语言初阶】分支语句

&#x1f31f;博主主页&#xff1a;我是一只海绵派大星 &#x1f4da;专栏分类&#xff1a;C语言 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 目录 一、什么是语句 二、if语句 悬空else 三、switch语句 default 四、switch语句与if-else语句性能对比如何&#xff1f…
阅读更多...
【Python核心数据结构探秘】：元组与字典的完美协奏曲

【Python核心数据结构探秘】：元组与字典的完美协奏曲

文章目录 &#x1f680;一、元组⭐1. 元组查询的相关方法❤️2. 坑点&#x1f3ac;3. 修改元组 &#x1f308;二、集合⭐1. 集合踩坑❤️2. 集合特点&#x1f4a5;无序性&#x1f4a5;唯一性 ☔3. 集合&#xff08;交&#xff0c;并&#xff0c;补&#xff09;&#x1f3ac;4. …
阅读更多...
手撕设计模式——克隆对象之原型模式

手撕设计模式——克隆对象之原型模式

1.业务需求 ​ 大家好&#xff0c;我是菠菜啊&#xff0c;前俩天有点忙&#xff0c;今天继续更新了。今天给大家介绍克隆对象——原型模式。老规矩&#xff0c;在介绍这期之前&#xff0c;我们先来看看这样的需求&#xff1a;《西游记》中每次孙悟空拔出一撮猴毛吹一下&#x…
阅读更多...
【电赛】STM32-PID直流减速电机小车【寻迹+避障+跟随】【更新ing】

【电赛】STM32-PID直流减速电机小车【寻迹+避障+跟随】【更新ing】

一.需求分析 1.主控&#xff1a;STM32C8T6&#xff08;没什么好说的哈哈&#xff09; 2.电机&#xff1a;JAG25-370电机 【问】为什么要用直流减速电机&#xff1f;&#xff1f; PID控制器需要依靠精确的反馈信号来调整其输出&#xff0c;确保电机按照预定的速度和位置运行…
阅读更多...
简单聊一下Oracle，MySQL，postgresql三种锁表的机制，行锁和表锁

简单聊一下Oracle，MySQL，postgresql三种锁表的机制，行锁和表锁

MySQL&#xff1a; MySQL使用行级锁定和表级锁定。行级锁定允许多个会话同时写入表&#xff0c;适用于多用户、高并发和OLTP应用。表级锁定只允许一个会话一次更新表&#xff0c;适用于只读、主要读取或单用户应用。 比如mysql开启一个窗口执行 begin; update xc_county_a…
阅读更多...
激光点云配准算法——Cofinet / GeoTransforme / MAC

激光点云配准算法——Cofinet / GeoTransforme / MAC

激光点云配准算法——Cofinet / GeoTransformer / MAC GeoTransformer MAC是当前最SOTA的点云匹配算法&#xff0c;在之前我用总结过视觉特征匹配的相关算法 视觉SLAM总结——SuperPoint / SuperGlue 本篇博客对Cofinet、GeoTransformer、MAC三篇论文进行简单总结 1. Cofine…
阅读更多...
jquery.datetimepicker无法添加清除按钮的问题

jquery.datetimepicker无法添加清除按钮的问题

项目场景&#xff1a; 自从决定用现有新技术实现CRM老项目起&#xff0c;就开始了我的折腾之路&#xff0c;最近一直在折腾前端页面&#xff0c;不像后端Java&#xff0c;写的有问题运行会报错&#xff0c;大多数报错一搜就能找到解决方案&#xff0c;前端这个倒好&#xff0c…
阅读更多...
【Qt】TreeWidget中Item的UserCheckable注意事项，没有出现多选框

【Qt】TreeWidget中Item的UserCheckable注意事项，没有出现多选框

1. 异常 开启 ItemIsUserCheckable以后&#xff0c;界面上没有出现多选框。 QTreeWidgetItem *item new QTreeWidgetItem();item->setText(0, "hello");item->setFlags(Qt::ItemIsUserCheckable | Qt::ItemIsSelectable |Qt::ItemIsEnabled | Qt::ItemIsAuto…
阅读更多...
Linux---防火墙

Linux---防火墙

文章目录 目录 文章目录 前言 一.静态防火墙&#xff1a;iptables iptables五链 iptables 四表 iptables控制类型 iptables命令配置 前言 这儿主要介绍Linux系统本身提供的软件防火墙的功能&#xff0c;即数据包过滤机制。 数据包过滤&#xff0c;也就是分析进入主机的网络数…
阅读更多...
k8s 1.28 搭建rabbitmq集群

k8s 1.28 搭建rabbitmq集群

1.环境 1.1 k8s 1.28 1.2 rabbit 3.8 1.3 工作空间default 1.4 注意&#xff0c;内存最好充足一点&#xff0c;因为我就两个节点一个master、一个node&#xff0c;起初我的node是8g&#xff0c;还剩3~4G&#xff0c;集群竟然一直起不来&#xff0c;后来将虚拟机内存扩大&#x…
阅读更多...
最新文章

Copyright @ 2022~2023