当前位置： 首页 > article >正文

数据结构 -AVL Tree

article 2024/11/5 7:56:32

博客主页：【夜泉_ly】
本文专栏：【数据结构】
欢迎点赞👍收藏⭐关注❤️

在这里插入图片描述

文章目录

  • 💡AVL树
    • 1. 简介
    • 2. 基操
      • 2.1 树的节点
      • 2.2 树的框架
    • 3. 插入
      • 3.1 铺垫
      • 3.2 调整平衡因子
    • 4. 旋转
      • 4.1 左旋
      • 4.2 右旋
      • 4.3 双旋
      • 4.4 代码实现

💡AVL树

1. 简介

在数据结构 -Binary Search Tree -1和2中，我对普通的二叉搜索树做了简单的介绍，并指出其潜在的效率问题，比如变成类似链表的极端情况。

而AVL树是二叉搜索树的升级版，被称作自平衡二叉搜索树。
因此AVL树的特点有两个：

  1. 是二叉搜索树
  2. 平衡：规定任何一个节点的左右子树高度差不大于一。（在这里，一般将左右子树的高度差简称为平衡因子。）
    例如：
    在这里插入图片描述在这里插入图片描述

可见，普通二叉树的极端情况，在AVL树中不会出现，因为它必须控制子树的相对高度。

但完全的平衡AVL树也做不到，因此并没有规定左右子树高度相等（即平衡因子为0），而是放宽的一点要求，规定平衡因子的绝对值不大于一。

2. 基操

为了加深理解，接下来模拟实现AVL树的插入过程。

2.1 树的节点

首先还是建立树的节点，在这里，需要多加一个平衡因子：

template<class K, class V>
struct AVLTreeNode
{
	int _bf;

bf指balance factor，即平衡因子。

	pair<K, V> _kv;
	AVLTreeNode<K, V>* _pLeft;
	AVLTreeNode<K, V>* _pRight;

还需要注意一点，由于在后续操作中，需要调整树的节点来平衡高度，因此，AVL树的节点还多了一个指向父节点的指针：

	AVLTreeNode<k, V>* _pParent;

构造函数：

	AVLTreeNode(const pair<K, V>& kv)
		:_bf(0)
		,_kv(kv)
		,_pLeft(nullptr)
		,_pRight(nullptr)
		,_pParent(nullptr)
	{}
};

2.2 树的框架

开始写树：

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	// Insert
private:
	Node* _root = nullptr;
};

3. 插入

3.1 铺垫

接下来补充// Insert：
插入的前几步操作和之前二叉搜索树的类似：

void 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)
			return false;
			
		parent = cur;
		
		if(cur->_kv.first < kv.first)
			cur = cur->_pRight;
		else 
			cur = cur->_pLeft;
	}

	cur = new Node(kv);
	if(parent->_kv.first < kv.first)
		parent->_pRight = cur;
	else
		parent->_pLeft = cur;

和之前略有不同，插入时需要多调整一个_pParent指针：

	cur->_pParent = parent;

3.2 调整平衡因子

插入节点后，树的结构发生改变，接下来需要开始调整平衡因子：
这里我将平衡因子规定为右子树的高度 - 左子树的高度。

调整_bf时，新插入的节点的_bf == 0，不用变。
而从第一个父节点一直到根节点，平衡因子都有可能改变：（节点中的数字指的是_bf的值）
在这里插入图片描述
因此最外层是一个循环，结束条件是parent为nullptr：

	while (parent)
	{

如何调整_bf呢，首先，如果一个节点的左子树增加了，那么这个节点的_bf应该减一：
在这里插入图片描述在这里插入图片描述
相应的，如果右子树增加了，其_bf应该加一。
因此可以写出对应的代码：

		if (parent->_pLeft == cur)
		{
			parent->_bf--;
		}
		else 
		{
			parent->_bf++;
		}

调整完当前parent节点的_bf后，需要判断下一步的操作：

  • 如果结果为0，不需要继续调整，因为左右已经平衡了。
    这里可以通过画图进行理解：
    在这里插入图片描述

  • 如果结果为1或-1，说明之前parent的_bf必定为0，此时高度被改变，需要继续向上调整。
    在这里插入图片描述

  • 如果结果为2或-2，已经不满足规则了，需要对当前的树进行旋转，使其满足平衡的条件。

  • 如果为其他结果，说明之前的步骤已经出问题了，需要直接报错！

根据以上的讨论，可以写出以下代码：

		if (parent->_bf == 0)
		{
			return true;
		}
		else if (parent->_bf == -1 || parent->_bf == 1)
		{
			cur = parent;
			parent = cur->_pParent;
		}
		else if (parent->_bf == -2 || parent->_bf == 2)
		{
			// Rotate
			return true;
		}
		else
		{
			assert(false);
		}
	}

接下来补充// Rotate：

4. 旋转

在_bf等于2或-2时，可以确定的是 parent 的一个子树高了，而解决方法是对 parent 和这个子树进行旋转，相当于把 parent 这个节点给摁下去。
这里需要先补充几个函数：

4.1 左旋

首先是左旋，顾名思义，就是往左边旋转。
举个简单的例子：（提醒一下：节点旁的数字指的是_bf的值）

在这里插入图片描述
相当于直接将妮可降了下来，由于二叉搜索树左小于根，右大于根的性质，可以保证旋转的正确性。

再举个有一般性的例子：
在这里插入图片描述
可见，左旋就是将妮可的左节点给铃，然后妮可的左节点变成铃，而妮可的右节点不动，铃的左节点不动。

理清大致的步骤后，可以发现，在旋转时只需要处理 parent 节点（下面简称 P ），以及 parent->_pRight 节点（下面简称 PR ），有时还可能处理 PR->_pLeft 节点（下面简称 PRL ），和parent->_pParent节点(下面简称P_P)。
因此，我又理了理细节：

->_pLeft->_pRight->_pParent_bf
父节点（P）不变变为：PRL变为：PR变为0
右子树的根节点(PR)变为：P不变变为：P_P变为0
PRL(如果有)不变不变变为：P不变
P_P（如果有）可能变为PR可能变为PR不变不变

下面是代码实现：(其实就是照搬上面的表格😂)

void RotateL(Node* parent)
{
	Node* P = parent;
	Node* PR = parent->_pRight;
	Node* PRL = PR->_pLeft;
	Node* P_P = parent->_pParent;

	P->_pRight = PRL;
	P->_pParent = PR;
	P->_bf = 0;

	PR->_pLeft = P;
	PR->_pParent = P_P;
	PR->_bf = 0;

	if (PRL)
		PRL->_pParent = P;

	if (P_P)
	{
		if (P_P->_pLeft == parent)
			P_P->_pLeft = PR;
		else
			P_P->_pRight = PR;
	}
}

然后是右旋：

4.2 右旋

在理解左旋后，右旋本质就是左旋翻转一下，还是以图为例。
首先是简单的情况：（注意箭头也被翻了一下，请从右往左看）
在这里插入图片描述

然后是有一般性的情况：

在这里插入图片描述

再把上面那段话CV下来，稍微改改：
理清大致的步骤后，可以发现，在旋转时只需要处理 parent 节点（下面简称 P ），以及 parent->_pLight 节点（下面简称 PL ），有时还可能处理 PL->_pReft 节点（下面简称 PLR ），和parent->_pParent节点(下面简称P_P)。
因此，我又理了理细节：（注意这里->_pRight和->pLeft的位置也被我换了一下）

->_pRight->_pLeft->_pParent_bf
父节点（P）不变变为：PLR变为：PL变为0
左子树的根节点(PL)变为：P不变变为：P_P变为0
PLR(如果有)不变不变变为：P不变
P_P（如果有）可能变为PL可能变为PL不变不变

下面是代码实现：(其实还是照搬上面的表格🤣)

void RotateR(Node* parent)
{
	Node* P = parent;
	Node* PL = parent->_pLeft;
	Node* PLR = PL->_pRight;
	Node* P_P = parent->_pParent;

	P->_pLeft = PLR;
	P->_pParent = PL;
	P->_bf = 0;

	PL->_pRight = P;
	PL->_pParent = P_P;
	PL->_bf = 0;

	if (PLR)
		PLR->_pParent = P;

	if (P_P)
	{
		if (P_P->_pLeft == parent)
			P_P->_pLeft = PL;
		else
			P_P->_pRight = PL;
	}
}

接下来是双旋：

4.3 双旋

因为原理相同，这里只讲一种，即右左双旋。

在刚刚的过程中，单旋已经能够处理一部分的情况，但还有一部分不能处理，比如下面这种：
在这里插入图片描述
这时，就需要在不同方向旋转两次，第一次是将上图的V字型变直，第二次就是普通的单旋。
例如：
在这里插入图片描述
再来看看比较有一般性的情况：

在这里插入图片描述

首先需要强调的是，n可以为0，即安比就是插入的节点。
接下来看看具体的步骤：

  • 首先是对妮可的右旋，这会将妮可降到安比的下面。
    安比的右边指向妮可，左边不变；
    妮可的左边指向猫又，右边不变。
    如果复用之前的函数，这里调整完后_bf会自动变成0，不过没有关系，等会儿统一处理。
    在这里插入图片描述

  • 然后对铃进行左旋，这会将铃也降到安比下面。
    安比的左边指向铃，右边不变；
    铃的右边指向 . . . ，左边不变。
    在这里插入图片描述

  • 最后调平衡因子：由于妮可的右边比左边高，因此_bf为1
    在这里插入图片描述
    通过上面的操作，可以发现需要做事只有两件：

  1. 复用之前的函数
  2. 调整平衡因子

复用函数这块没问题，接下来看看怎么调整平衡因子：

  • 第一种情况，安比就是插入节点，这种情况最简单，_bf全部弄成0就行：
    在这里插入图片描述
  • 第二种情况，在安比的左边插入节点：
    在这里插入图片描述
    对于铃：经过之前的分析，可知安比左边的节点会变成铃右边的节点，而High = n + 1减去安比就是安比左边节点的高度，等于铃左边节点的高度，因此铃的_bf可以调整为0。
    对于安比：左边的高度为 铃+n 即n+1，右边调整后是妮可，高度为 妮可+n 也为n+1,因此安比的_bf可以调整为0。
    对于妮可：由于调整前安比->猫又这一条的高度为n，而调整后妮可左边变成猫又，高度为 n-安比 ，即n - 1，而右边高度为n，因此妮可的_bf调整为1。
    如图：
    在这里插入图片描述
  • 第三种情况，在安比的右边插入节点：
    在这里插入图片描述
    分析与第二种情况类似，最终结果：安比、妮可的_bf为0，铃的_bf为-1。
    如图：
    在这里插入图片描述

通过以上讨论，可以发现平衡因子的改变本质是由安比的左右高度差引起的：
安比左右高度差为0，即安比为插入节点，那么三人的_bf都为0；
安比的左边高，_bf == -1，调整后安比左边的铃平衡，0，右边的妮可不平衡，1；
安比的右边高，_bf == 1 ，调整后安比右边的妮可平衡，0，左边的铃不平衡，-1。

因此，对于双旋，还可以整体来看：
即安比的左右节点分别被铃和妮可瓜分，
之后，安比的左右分别变成铃和妮可，
而，铃和妮可得到节点更高的人平衡，低的人就不平衡。

如图：
在这里插入图片描述
在这里插入图片描述

4.4 代码实现

最后是代码实现，补充的是Insert函数中的// rotate部分：

else if (parent->_bf == -2 || parent->_bf == 2)
{

首先，如果是直线型，可以直接左旋右旋：

	if (parent->_bf == 2 && parent->_pRight->_bf == 1)
	{
		RotateL(parent);
	}
	else if (parent->_bf == -2 && parent->_pLeft->_bf == -1)
	{
		RotateR(parent);
	}

然后是V型，由于这时parent是铃，因此得先找到安比的值。

	else if (parent->_bf == 2 && parent->_pRight->_bf == -1)
	{

铃是2，妮可是-1，因此就是刚刚分析的右左双旋。
先保存三人的节点，以及安比的_bf：

		Node* Belle = parent;
		Node* Nicole = parent->_pRight;
		Node* Anby = Nicole->_pLeft;
		int bf = Anby->_bf;
		
		RotateR(Nicole);
		RotateL(Belle);
		
		if(bf == 0)
		{
			Belle->_bf = Nicole->_bf = Anby->_bf = 0;
		}
		else if(bf == 1)
		{
			Nicole->_bf = Anby->_bf = 0;
			Belle->_bf = -1;
		}
		else if(bf == -1)
		{
			Belle->_bf = Anby->_bf = 0;
			Nicole->_bf = 1;
		}
		else assert(false);
	}

然后就是左右双旋，这和右左双旋原理类似，稍微改改就行：

	else if (parent->_bf == -2 && parent->_pLeft->_bf == 1)
	{
		Node* Belle = parent;
		Node* Nicole = parent->_pLeft;
		Node* Anby = Nicole->_pRight;
		int bf = Anby->_bf;
		
		RotateL(Nicole);
		RotateR(Belle);
		
		if(bf == 0)
		{
			Belle->_bf = Nicole->_bf = Anby->_bf = 0;
		}
		else if(bf == 1)
		{
			Belle->_bf = Anby->_bf = 0;
			Nicole->_bf = -1;
		}
		else if(bf == -1)
		{
			Nicole->_bf = Anby->_bf = 0;
			Belle->_bf = 1;
		}
		else assert(false);
	}
	else
	{
		assert(false);
	}
	return true;
}

在这里插入图片描述

希望本篇文章对你有所帮助！并激发你进一步探索编程的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！


http://www.kler.cn/a/379845.html

相关文章：

  • 基于STM32的手式电视机遥控器设计
  • 【广度优先搜索】——岛屿数量
  • 软件对象粒度控制与设计模式在其中作用的例子
  • 用ChatGPT提升工作效率：从理论到实际应用
  • 云原生+AI核心技术＆最佳实践
  • 显存占用 显存测试
  • 【HarmonyOS】鸿蒙系统
  • 彻底解决idea不识别java项目
  • Java8 新特性 —— Optional API 详解
  • 《GAN 的基本原理》
  • 【Nextcloud】在 Ubuntu 22.04.3 LTS 上的 Nextcloud Hub 8 (29.0.0) 优化
  • Copilot功能
  • 在.net下后台设置前台UEditor编辑器不可编辑
  • WordPress网站添加嵌入B站视频,自适应屏幕大小,取消自动播放
  • Spring Boot框架：校园社团信息管理的现代化解决方案
  • SQL 数据结构查询
  • Python网络爬虫：入门与实战
  • GHuNeRF: Generalizable Human NeRF from a Monocular Video
  • ubunu安装官方微信 解决安装后更新系统变为atzlinux的问题 卸载微信
  • 基于python flask的知乎问答文本分析与情感预测系统
  • 让Erupt框架支持.vue文件做自定义页面模版
  • QT中QML例程-学习笔记-语法
  • N-155基于springboot,vue宿舍管理系统
  • 【docker compose】docker compose的hello world
  • 第100+31步 ChatGPT学习：概率校准 Quantile Calibration
  • UI自动化测试 —— CSS元素定位实践！