C++中高阶数据结构(AVL树的原理讲解)

AVL树

AVL树的定义

avl本质是搜索树,是高度平衡二叉搜索树.特点是:任何树的左右子树的高度差不超过1.最大的高度差值最大也只能是1,也称之为平衡因子,

平衡因子就是右子树减去左子树的值,这个值的绝对值的最大值只能是1.这个平衡因子不是必须的,只是一种控制方式,方便我们更便捷的控制树.

节点的定义

struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf; // balance factor
	pair<K, V> _kv;
	AVLTreeNode(const pair<K,V> kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
		, _kv(kv)
	{}
};

向AVL树插入节点

  • 先按着搜索树的规则插入节点
  • 接着利用平衡因子来观测该树是否还是AVL树
    • 新插入的节点可能会影响该节点的部分祖先的平衡因子的值.
    • 更新规则:在c的左边新增,那么p->bf–,在c的右边新增,那么p->bf++,那么是否还会继续影响祖先呢?取决于p的高度是否变化.
    • 更新之后:父亲的 平衡因子如果是0的话,那么p所在的子树的高度不变不会影响爷爷.(如果p的平衡因子更新之后是0,就说明过更新之前是1或者是-1,说明是在矮的那一边插入了节点,p的高度不变,不会影响爷爷.),此时更新结束
    • 更新之后p的平衡因子是1或者是-1,那么p所在的子树的高度变了.会影响爷爷,说明更新之前p->bf是0,在p的有一边插入之后,p的高度变化了,就会影响爷爷.
    • 更新之后p的平衡因子成了2或者是-2,此时p所在子树就不是AVL树了,那么就需要进行旋转处理了.
    • 最后c成了根节点之后,那么就是更新条件结束了
  • 三种结束条件:
    • 更新到root结束,p->bf==0结束,旋转让parent所在子树的高度回到了插入之前,不会对上层的bf有影响,结束.

代码实现:

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;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = cur->_parent;
				parent = parent->_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
				{
					RotateRL(parent);
				}

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

		return true;
	}

AVL中的旋转处理

根据插入数据的不同情况可以分为四种情况的

左单旋

当碰到如下图的情况:(红色的是插入节点之后节点对应的平衡因子的值,红色的方块代表插入了一个节点)

当c的右边增加了节点导致了p的平衡因子变成了2之后,此时将subR的左子树连接到parent的右子树上,紧接着将整个parent为根,a为左子树,b为右子树的整棵树连接到subR的左边.此时再计算平衡因子,发现都成了0,整棵树就满足了avl树的规则.
在这里插入图片描述

这里subR在插入节点之前,b子树和c子树的高度一定是相同的(高度也可以是0),只有如此,subR的节点的平衡因子才是0,假如b子树和c子树的高度不同,那么subR的平衡因子是值可能是1或者是-1,此时在subR的右边插入节点,subR节点的平衡因子可能会变成0或者是2,若变成0,avl树的更新就结束了,根本就不需要调整,若变成了2,那么需要调整的树就是subR这颗树,而不是parent这个树.

同理,a子树的节点的高度也一定是h

  • 如果a子树的高度是h+1,那么parent的平衡因子就是0了,此时无论是在parent的左边还是右边插入元素,都无法使parent的平衡因子更新成2或者是-2
  • 如果a子树的高度使h-1,那么此时这颗树根本就不是AVL树了,说明在新节点插入之前就不是AVL树

代码实现:

void RotateL(Node* parent)
{
	Node* subR = parent->_left;
    Node* subRL = subR->_right;
	Node* ppnode = parent->_parent;
    
    
    parent->_right = subRL;
    if(subRL) // subRL的高度可能是0
    subRL->_parent = parent;
    
    subR->_left = parent;
    parent->_parent = subR;
    
    // 假如插入节点之前parent就是整棵树的根
	if(ppnode == nullptr)
    {
        _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;
}

右单旋

当遇到如下图的情况时:(红色是更新之后的平衡因子的值):

新节点插入到较高左子树的左侧,就使用右单旋.因为此时的树看上去就是整个左侧高,右侧低的形式

右单旋的方法:将subL的b这个右子树连接到parent的左边,紧接着,以parent为根,b为左子树,c为右子树的整棵树连接到subL的右边.

在这里插入图片描述

代码实现:

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* grandParent = parent->_parent;
    
    parent->_left = subLR;
    // 同理,subLR的高度可能是0 
    if(subLR)
    subLR->_parent = parent;
    
    subL->_right = parent;
    parent->_parent = subL;
    
    // 假如插入节点之前parent就是整棵树的根
    if(_root == parent)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if(grandParent->_left ==  parent)
        {
            grandParent->_left = subL;
        }
        else
        {
            grandParent->_right = subL;
		}
        subL->_parent = grandParent;
    }
    parent->_bf =0;
    subL->_bf = 0;
}

左右双旋

当新的节点插入在较高左树的右边时,需要进行左右双旋.

假定是如下图的情况:
在这里插入图片描述

此时在h这个子树插入数据时,整棵树的左边是较高的,此时我们假如采用右旋转,则会:
在这里插入图片描述

会发现,右旋之后,值为30的节点的平衡因子还是-2,所以我们不能采用单旋了,使用双旋.

  • 假设h是大于0的情况:

    先将b子树拆分:
    在这里插入图片描述

    将b拆分为值为40(这里40只是例子,只要满足时大于30小于60即可)的节点和e子树和f子树,那么此时由e和f两个子树了,新的节点就会有两种选择了.

    • 当在e子树插入数据时:以30为断点进行左单旋,接着对整棵树进行右单旋
      在这里插入图片描述

      通过图可知,最后形成的树是符合要求的,并且各自的平衡因子经过计算都是满足要求的.

    • 当在f子树插入节点时:
      对仍然对局部进行左单旋,接着对整棵树进行右单旋.

      在这里插入图片描述

      并且经过计算之后的平衡因子经过计算之后也是符合要求的.

    当h==0时:
    此时e和f就不存在了,

    • 当在30的右边插入节点时,就先对30为根的树进行做单旋,对整棵树进行右单旋.如下图所示,最终计算出的平衡因子都是符合要求的.

    在这里插入图片描述

    • 当在30的左边插入节点时:可以直接对整棵树进行右单旋即可.

    最终形成的树的关键节点的平衡因子的如何确定:由上图可以看出规律

    • 当h!=0时
      • 当新节点在e子树插入时:40所在节点的平衡因子是0,30所在节点的平衡因子是0,60所在节点的平衡因子是1.
      • 当新节点在f子树插入时:40所在节点的平衡因子是0,30所在节点的平衡因子是-1,60所在节点的平衡因子是0.
    • 当h==0时,这个三个关键节点的平衡因子都是0

    如何确定规律呢?

    因为e和f这两颗子树的高度是相同的.所以在e树插入数据时,e的parent的平衡因子就会更新为-1,
    在这里插入图片描述

    当是在f树插入节点时,f的parent的平衡因子就会更新成1.
    在这里插入图片描述

    当e和f不存在时:
    在这里插入图片描述

    代码实现:

    可以就可以利用subL的右节点的平衡因子的值来确定关键节点的平衡因子的值

    这里可以复用前面的代码,但是前面的左旋和右旋都会将节点的平衡因子都改成0.所以需要提前保存这个值

    void RotateLR(Node* parent)
{
	// 记录节点,为了保存节点里的_bf的值.
    Node* subL = parent->_left;
	Node* subLR = subL->_right;
   
    // 提前保存好平衡因子,防止被修改
    int bf = subLR->_bf;
    // 直接调用
    RotateL(parent->_left);
    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
    {
        // 此时就不是AVL树. ![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/3a4298086b6f436385586435bd9eaad7.png)

        assert(false);  
    }
}

右左双旋

当新节点插入在较高右树的左侧时,需要右左双旋了.采用的是和左右双旋类似的思想

在这里插入图片描述

  • 当h!=0时

    • 当在e树插入时:
      在这里插入图片描述

    • 当在f树插入时:
      在这里插入图片描述

  • 当h==0时
    在这里插入图片描述

代码实现:

void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	
	int bf = subRL ->_bf;
	
	RotateR(parent->_right);
	RotateL(parent);

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

如何验证一个树是否是avl树

可以计算每一个子树的高度,观察高度差.

可以先写一个检查高度的函数

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);
	}

在写一个Isbalance函数检查函数的左右高度是否符合要求

bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;

		int balance = _Height(root->_right) - _Height(root->_left);

		if (abs(balance) <= 2)
		{
			cout << "平衡" << endl;
			return true;
		}
		else
		{
			cout << "不平衡" << endl;
			return false;
		}
		if (balance != root->_bf)
		{
			cout << " 平衡因子异常 ";
			return false;
		}

		return _IsBalance(root->_left) && _IsBalance(root->_right);
	}

但是这个函数使用的递归太多了,复杂度太高了.每次在计算高度差的时候,已经将高度给计算出来了,但是函数的最后还是要计算左右子树的高度.

balance的优化,使用一个引用来记录height的左右高度.

bool _IsBalance(Node* root,int& Height)
	{
		if (root == nullptr)
        {
            height = 0;
            return true;            
        }
			

		int balance = _Height(root->_right) - _Height(root->_left);
		int leftHeight = 0,rightHeight = 0;
    // 左右子树只要有一个不是平衡树,就返回false
    	if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight))
		{
			return false;
		}
		if (abs(rightHeight - leftHeight) >= 2)
		{
			cout <<root->_kv.first<<"不平衡" << endl;
			return false;
		}
		if (balance != root->_bf)
		{
			cout << " 平衡因子异常 ";
			return false;
		}
		height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    	return true;
	}

结束

关于AVL树的讲解就到这里啦,如有不足,请在评论区指正,下期见!

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

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

相关文章

赛氪网｜2024中国翻译协会年会“AI科技时代竞赛与就业”分论坛

赛氪网｜2024中国翻译协会年会“AI科技时代竞赛与就业”分论坛

在2024年中国翻译协会年会期间&#xff0c;赛氪网与中西部翻译协会共同体多边合作平台共同承办&#xff0c;于3月30日下午在长沙成功举办了“AI科技时代竞赛与就业分论坛”。该论坛汇聚了众多翻译界、科技界和教育界的专家学者&#xff0c;共同探讨科技、实践、就业与竞赛人才培…
阅读更多...
FreeRTOS学习 -- 再识

FreeRTOS学习 -- 再识

工作中一直使用FreeRTOS进行着开发&#xff0c;但是没有进行过系统的总结过。现在将快速使用几天时间将FreeRTOS相关知识点加以总结。 官网&#xff1a; https://www.freertos.org/zh-cn-cmn-s/ 参看资料&#xff1a; 正点原子 STM32F1 FreeRTOS开发手册_V1.2.pdf The FreeRTOS…
阅读更多...
OpenCV与AI深度学习 | 实战 | 使用OpenCV确定对象的方向(附源码)

OpenCV与AI深度学习 | 实战 | 使用OpenCV确定对象的方向(附源码)

本文来源公众号“OpenCV与AI深度学习”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;实战 | 使用OpenCV确定对象的方向(附源码) 导读 本文将介绍如何使用OpenCV确定对象的方向(即旋转角度&#xff0c;以度为单位)。 1 先决条件…
阅读更多...
Clarity AI：免费开源的AI无损图片放大图像升级器和增强工具

Clarity AI：免费开源的AI无损图片放大图像升级器和增强工具

可以作为Magnific AI的平替版本。Magnific AI是一款基于人工智能技术的图像处理工具&#xff0c;主要功能包括图像放大、像素级AI重绘、灵活的设置调整以及多种优化场景。它能够支持最高放大至16倍&#xff0c;甚至可以达到1亿像素的分辨率。此外&#xff0c;Magnific AI还具备…
阅读更多...
lua学习笔记13（一些特殊用法的学习和三目运算符的实现）

lua学习笔记13（一些特殊用法的学习和三目运算符的实现）

print("*****************************一些特殊用法的学习*******************************") print("*****************************多变量赋值*******************************") local a,b,c114514,8848,"凌少" print(a) print(b) print(c) -…
阅读更多...
电脑微信双开，微信微信多开支持多个微信同时登录，快速切换，方便快捷 电脑最简单的微信双开多开方法 电脑上怎么登录两个微信账号？电脑微信怎么能够双开？

电脑微信双开，微信微信多开支持多个微信同时登录，快速切换，方便快捷 电脑最简单的微信双开多开方法 电脑上怎么登录两个微信账号？电脑微信怎么能够双开？

支持多个微信账号同时登录&#xff0c;不限微信登录个数&#xff0c;运行快速&#xff0c;稳定不卡顿 集成所有聊天窗口&#xff0c;一键快捷切换&#xff0c;窗口再多也不乱&#xff0c;提高你的工作效率 同时管理多个微信号&#xff0c;且需要分别维护用户关系、粉丝社群 …
阅读更多...
lua学习笔记14（协程的学习）

lua学习笔记14（协程的学习）

print("*****************************协程的学习*******************************") --创建1 coroutine.create(function()) 使用1 coroutine.resume(co) -- 创建2 co2coroutine.wrap(fun) 使用2 co2() --协程的挂起函数 coroutine.yield() --协程的状态 --c…
阅读更多...
蓝桥杯刷题--RDay5

蓝桥杯刷题--RDay5

清理水域--枚举 8.清理水域 - 蓝桥云课 (lanqiao.cn)https://www.lanqiao.cn/problems/2413/learning/?page1&first_category_id1&second_category_id3&tags2023 小蓝有一个n m大小的矩形水域&#xff0c;小蓝将这个水域划分为n行m列&#xff0c;行数从1…
阅读更多...
layui后台框架，将左侧功能栏目 集中到一个页面，通过上面的tab切换 在iframe加载对应页面

layui后台框架，将左侧功能栏目 集中到一个页面，通过上面的tab切换 在iframe加载对应页面

实现上面的 功能效果。 1 html代码 <form class"layui-form layui-form-pane" action""><div class"layui-tab" lay-filter"demo"><ul class"layui-tab-title"><li id"a0" class"lay…
阅读更多...
Unity自己实现的中英文的切换（简单好抄）

Unity自己实现的中英文的切换（简单好抄）

关键技术&#xff08;读取文件的方法&#xff0c;Split()分割字符串&#xff09; 1.搭建一个这样的场景&#xff0c;场景中有3个文本&#xff08;用新版的&#xff09;&#xff0c;一个空对象&#xff0c;一个按钮 2.编写翻译文本&#xff08;编写一个txt文本&#xff0c;在文…
阅读更多...
土耳其航空2023年共运送旅客8340万人次，境内境外航线运力稳步增长

土耳其航空2023年共运送旅客8340万人次，境内境外航线运力稳步增长

2023年,尽管面对持续紧张的国际局势和摇摆不定的宏观经济,土耳其航空仍实现了里程碑式的业绩表现,共计运输旅客8340万人次。土耳其境内航线运力比2022年增长了23.5%,运送旅客突破3000万人次;国际航线运力增长16%,运送旅客达5300万人次,并实现了14%的同比增长。其中,来自欧洲国家…
阅读更多...
Python高级

Python高级

不定长参数 位置不定长参数&#xff0c;获取参数args会整合为一个元组 def info(*args):print(arg is, args)print(type(arg) is, type(args))info(1, 2, 3, 4, a, b)# 输出 # arg is (1, 2, 3, 4, a, b) # type(arg) is <class tuple> 关键字不定长参数&#xff0c;&…
阅读更多...
【STL】stack与queue的底层原理及其实现

【STL】stack与queue的底层原理及其实现

文章目录 stack的介绍库中stack的使用栈的模拟实现queue的介绍库中queue的使用queue的模拟实现 stack的介绍 &#xff08;图片来自知乎&#xff09; 1.stack是一种容器适配器&#xff0c;模拟了栈的数据结构。数据只能从一端进去&#xff0c;另一端出来&#xff08;先进后出&am…
阅读更多...
VM-UNet: Vision Mamba UNet for Medical Image Segmentation

VM-UNet: Vision Mamba UNet for Medical Image Segmentation

VM-UNet: Vision Mamba UNet for Medical Image Segmentation VM-UNet&#xff1a;基于视觉Mamba UNet架构的医学图像分割 论文链接&#xff1a;http://arxiv.org/abs/2402.02491 代码链接&#xff1a;https://github.com/JCruan519/VM-UNet 1、摘要 文中利用状态空间模型SS…
阅读更多...
JavaSE：图书管理系统

JavaSE：图书管理系统

目录 一、前言 二、内容需求 三、类的设计 &#xff08;一&#xff09;图书类 1.Book 类 2.BookList 类 &#xff08;二&#xff09;操作类 1.添加图书AddOperation类 2.借阅图书BorrowOperation类 3.删除图书DelOperation类 4.显示图书ShowOperation类 5.退出系统Ex…
阅读更多...
ExpressLRS开源代码之功能性能测试

ExpressLRS开源代码之功能性能测试

ExpressLRS开源代码之功能&性能测试 1. 源由2. 规格2.1 功能2.2 性能 3. 概念3.1 产品组成3.2 性能分解3.3 专业归口 4. 测试4.1 实验室测试4.2 简易实验方法4.3 外场测试4.4 终极验证 5. 调优5.1 RF调优5.2 模块调优5.3 产品调优 6. 总结 1. 源由 最近&#xff0c;在ELRS…
阅读更多...
【ArcGIS 小技巧】隐藏tif影像的黑边或白边

【ArcGIS 小技巧】隐藏tif影像的黑边或白边

tif影像是规划中常用的参考数据。 但是当我们把tif拖入到ArcGIS中查看时&#xff0c;经常会出现黑色或白色的多余区域遮挡显示。 下面介绍我碰到的两种情况及解决办法。 1、三波段tif 三波段指的是R、G、B三个波段&#xff0c;可在tif影像的属性中查看是否有RGB三波段。 这…
阅读更多...
无忧网络验证系统 getInfo SQL注入漏洞复现

无忧网络验证系统 getInfo SQL注入漏洞复现

0x01 产品简介 无忧网络验证是一套安全稳定高效的网络验证系统，基于统一核心的通用互联网+信息化服务解决方案，是为软件作者设计的一套完整免费的网络验证体系。可以为开发的软件增加收费授权的功能,让作者开发的软件可以进行销售、充值、登陆等操作,并且提供防破解验证功能…
阅读更多...
JS 轮播图点击左右切换

JS 轮播图点击左右切换

点击左右按钮实现轮播图切换图片 style&#xff1a; *{margin: 0;padding: 0;margin: auto;}#img1{width: 300px;height: 300px;position: relative;}#butto1{width: 50px;height: 100px;font-size: 50px;border: none;background-color: hsla(0, 0%, 0%, 0.2);position: abs…
阅读更多...
Flyway 数据库版本管理

Flyway 数据库版本管理

一、Flyway简介 Flyway是一款开源的数据库迁移工具&#xff0c;可以管理和版本化数据库架构。通过Flyway&#xff0c;可以跟踪数据库的变化&#xff0c;并将这些变化作为版本控制的一部分。Flyway支持SQL和NoSQL数据库&#xff0c;并且可以与现有的开发流程无缝集成&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023