【1++的数据结构】之AVL树

这篇具有很好参考价值的文章主要介绍了【1++的数据结构】之AVL树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

👍作者主页:进击的1++
🤩 专栏链接:【1++的数据结构】


一,什么是AVL树

在说AVL树之前我们先来说说为什么会出现AVL树。在前面的文章中我们讲过二叉搜索树,虽然查找,插入效率比较高,但其有个缺陷:在某些情况下其可能会成为一颗单支树或其他高度较高的树,这时我们的效率就比较低了,甚至接近于O(n)。在此背景下,有两位俄罗斯数学家,便发明了AVL树----当插入新的结点后,保证每个结点的左右子树的高度差不大于1。则这颗树就会接近满二叉树,其高度就会降低,那么查找,插入效率也会提高。
【1++的数据结构】之AVL树,1++的数据结构,c++,AVL树

二,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 std::pair<K, V>& kv)
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _kv(kv)
			, _bf(0)
		{}

	};

了解了结点的结构后,我们就可以进行插入操作的学习。
与二叉搜索树一样,其先要找到要插入的位置,代码如下;

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->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;

与以前不同的是,由于是三叉链结构,因此当找到位置后,我们还要与其双亲结点进行链接。
当找到合适的位置进行插入后,便要进行控制平衡,使每个结点的左右子树高度差不超过1。

每个根节点的平衡因子的计算过程为;若插入的结点在其左侧,则根节点的平衡因子-1;若在右侧,则平衡因子+1。
根据平衡因子,我们总结出了三种控制平衡的规律:

  1. 若插入后根节点的平衡因子变为0,则说明在插入前其平衡因子为正负1,插入后被调整为0,满足AVL树的性质,则不做任何操作。
  2. 若插入后根节点的平衡因子变为正负1,则说明在插入前其平衡因子为0,插入后被改变,则向上继续更新,直到根节点。
  3. 若插入后平衡因子变为正负2,则违反了AVL树平衡的性质,需要进行旋转处理。

旋转操作,我们会在后面进行说明。

以下是控制其平衡的代码:

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

				if (parent->_bf == 0)
				{
					break;
				}
				else if (abs(parent->_bf) == 1)
				{
					parent = parent->_parent;
					cur = cur->_parent;
				}
				else if (abs(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 if (parent->_bf == 2 && cur->_bf == -1)
					{
						RotateRL(parent);
					}
					
						break;


				}
				else
				{
					assert(false);
				}
			}
		}

三,AVL树的旋转

3.1 向左旋转

以下是向左 旋转的代码:

void RotateL(Node* parent)
		{
			Node* SubR = parent->_right;
			Node* SubRL = SubR ->_left;
			parent->_right = SubRL;
			if (SubRL)
			{
				SubRL->_parent = parent;
			}

			Node* ppNode = parent->_parent;
			SubR->_left = parent;
			parent->_parent = SubR;
			if (_root == parent)
			{
				_root = SubR;
				SubR->_parent = nullptr;
			}
			else
			{
				if (ppNode->_left == parent)
				{
					ppNode->_left = SubR;
				}
				else
				{
					ppNode->_right = SubR;
				}
				SubR->_parent = ppNode;

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

		}

那么在什么情况下才会进行向左旋转呢?
【1++的数据结构】之AVL树,1++的数据结构,c++,AVL树

【1++的数据结构】之AVL树,1++的数据结构,c++,AVL树

如图,当我们的新插入的结点在较高子数的右侧时,此时30这个结点的平衡因子变为了2,满足了旋转的条件(图中h可为任何正整数或0)我们可以从图中清楚的看到,当插入新节点后平衡因子为2的结点的右子数明显高,为了平衡,我们则需要给其右子树将高度,我们将30称为parent,60称为SubR;60的左子树b称为SubRL。从图中我们看到,SubR成为了这颗树或者说是子树的新结点。而SubRL成为了parent的右子树。改变后仍遵循二叉搜索树的规则。此时,我们的左旋转就完成了。旋转后,平衡因子也发生了改变,所以要对平衡因子进行更新。对parent和SubR的平衡因子进行更新,更新后都变为0。

3.2 向右旋转

向右旋转与向左旋转相似
代码如下:

void RotateR(Node* parent)
		{
			Node* SubL = parent->_left;
			Node* SubLR = SubL->_right;
			parent->_left = SubLR;
			if (SubLR)
			{
				SubLR->_parent = parent;
			}
			Node* ppNode = parent->_parent;
			SubL->_right = parent;
			parent->_parent = SubL;
			if (_root == parent)
			{
				_root = SubL;
				SubL->_parent = nullptr;
			}
			else
			{
				if (ppNode->_left == parent)
				{
					ppNode->_left = SubL;
				}
				else
				{
					ppNode->_right = SubL;
				}

				SubL->_parent = ppNode;
			}
			SubL->_bf = parent->_bf = 0;

		}

向右旋转的情况如下图:
【1++的数据结构】之AVL树,1++的数据结构,c++,AVL树
当新插入的结点在较高左子树的左侧时,进行右旋转。
如图,我们可以看出其左子树高,我们仍将60称为parent,将30称为SubL,将30的右子树称为SubLR。旋转时,将SubL作为了根节点,SubLR给了parent的左侧。旋转完成后要进行平衡因子的更新,parent与SubL都更新为0。

3.3 左右双旋

代码如下:

void RotateLR(Node* parent)
		{
			Node* SubL = parent->_left;
			Node* SubLR = SubL->_right;
			int bf = SubLR->_bf;
			RotateL(parent->_left);
			RotateR(parent);
			SubLR->_bf = 0;
			if (bf == 1)
			{
				parent->_bf = 0;
				SubL->_bf = -1;
			}
			else if (bf == -1)
			{
				parent->_bf = 1;
				SubL->_bf = 0;
			}
			else if (bf == 0)
			{
				parent->_bf = 0;
				SubL->_bf = 0;
			}
			else
			{
				assert(false);
			}

		}

当新结点插入较高左子树的右侧时,则会进行左右双旋,就是先向左旋转,再向右旋转。
【1++的数据结构】之AVL树,1++的数据结构,c++,AVL树
先以30为parent进行左旋转,再以90为parent进行右旋转。
左右旋转我们在上面已经进行了讲述,接下来,我们的重点是平衡 因此的更新,在上图这种情况下,新插入的结点可以为60的左子树,也可以为右子树,或者60本身就为新插入的结点。
因此在不能的情况下,平衡因子的更新也不同。
主要有以下情况:
(SubL为30,parent为90)

			Node* SubL= parent->_left;
			Node* SubLR = SubL->_right;
			int bf = SubLR->_bf;
			SubLR->_bf = 0;
			if (bf == 1)
			{
				parent->_bf = 0;
				SubL->_bf = -1;
			}
			else if (bf == -1)
			{
				parent->_bf = 1;
				SubL->_bf = 0;
			}
			else if (bf == 0)
			{
				parent->_bf = 0;
				SubL->_bf = 0;
			}

3.4 右左双旋

代码如下:

void RotateRL(Node* parent)
		{
			Node* SubR = parent->_right;
			Node* SubRL = SubR->_left;
			int bf = SubRL->_bf;
			RotateR(parent->_right);
			RotateL(parent);
			SubRL->_bf = 0;
			if (bf == 1)
			{
				parent->_bf = -1;
				SubR->_bf = 0;
			}
			else if (bf == -1)
			{
				parent->_bf = 0;
				SubR->_bf = 1;
			}
			else if (bf == 0)
			{
				parent->_bf = 0;
				SubR->_bf = 0;
			}
			else
			{
				assert(false);
			}

		}

当新结点插入在较高右子树的左侧时,进行右左双旋(先向右旋转,在向左旋转)。
【1++的数据结构】之AVL树,1++的数据结构,c++,AVL树
与左右双旋相似,其平衡因子的更新也有几种情况:

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

四,验证AVL树是否平衡

AVL树最重要的一个性质就是其每个结点的左右子树之差的绝对值小于2。
并且等于该结点的平衡因子的绝对值。
我们以此来测试我们所写的AVL树是否正确
代码如下:文章来源地址https://www.toymoban.com/news/detail-681155.html


//求该子树的高度
int Height(Node* root)
		{
			if (root == nullptr)
			{
				return 0;
			}
			return max(Height(root->_left), Height(root->_right)) + 1;
				
		}

bool _Isbalance(Node* root)
		{
			if (root == nullptr)
			{
				return true;
			}
			int leftHT = Height(root->_left);
			int rightHT = Height(root->_right);
			int diff = rightHT - leftHT;
			if (diff != root->_bf)
			{
				cout << root->_kv.first << "平衡因子异常" << endl;
				return false;
			}
			return abs(diff) < 2 
				&& _Isbalance(root->_left)
				&& _Isbalance(root->_right);

		}

到了这里,关于【1++的数据结构】之AVL树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++&&数据结构——AVL树

    根据前面对二叉搜索树的学习我们可以了解到二叉搜索树可以提高查找的效率,但是如果数据本身有序,搜索树将退化成单支树,查找时相当于顺序表查找,效率低下,如下图: 为了解决上面的问题,来自俄罗斯的两位天才数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种方

    2024年01月19日
    浏览(66)
  • 数据结构进阶(一):AVL树

    所谓的AVL树也叫做高度平衡的二叉搜索树。 啥是高度平衡的二叉搜索树? 高度平衡的二叉搜索树: 意味着左右子树的高度最大不超过一 。 我们先来回顾一下二叉搜索树的概念: 二叉搜索树又称二叉排序树,它或者是一棵空树 ,或者是具有以下性质的二叉树: 若它的左子树

    2024年02月12日
    浏览(36)
  • 【1++的数据结构】之AVL树

    👍作者主页:进击的1++ 🤩 专栏链接:【1++的数据结构】 在说AVL树之前我们先来说说为什么会出现AVL树。在前面的文章中我们讲过二叉搜索树,虽然查找,插入效率比较高,但其有个缺陷:在某些情况下其可能会成为一颗单支树或其他高度较高的树,这时我们的效率就比较

    2024年02月11日
    浏览(35)
  • 数据结构与算法——18.avl树

    这篇文章我们来看一下avl树 目录 1.概述 2.AVL树的实现 我们前面讲了二叉搜索树,它是有一个key值,然后比父节点key值大的在左边,小的在右边。这样设计是为了便于查找。但是有一种极端的情况,就是所有的结点都在一边,那查找的时间复杂度和在链表的查找时间复杂度就

    2024年02月07日
    浏览(39)
  • 【数据结构】—AVL树(C++实现)

                                                            🎬慕斯主页 : 修仙—别有洞天                                                  💜 本文前置知识:  搜索二叉树                                                       ♈️ 今日夜电波

    2024年02月05日
    浏览(50)
  • 数据结构:AVL树讲解(C++)

    普通二叉搜索树: 二叉搜索树 二叉搜索树虽可以缩短查找的效率,但如果 数据有序或接近有序普通的二叉搜索树将退化为单支树 ,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法

    2024年02月04日
    浏览(42)
  • 【高阶数据结构】AVL树详解(图解+代码)

    前面对map/multimap/set/multiset进行了简单的介绍,在其文档介绍中发现。 这几个容器有个共同点是: 其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N),因此

    2024年02月13日
    浏览(50)
  • 【数据结构】AVL树的插入与验证

    普通的二叉搜索树在极端情况下会 退化成类似链表 的形状,从而使 查找的效率降低至O(N) 。 在此基础上,苏联与以色列数学家 A delson- V elskii 与 苏联数学家 L andis,发明出了 AVL树或者说平衡二叉搜索树。 注:第一张——Adelson-Velskii(1922-2014) ,第二张——Landis(1921——

    2024年02月09日
    浏览(37)
  • 数据结构(C++) : AVL树 实现篇

    目录 1.AVL树引入   (1)二叉搜索树缺点   (2)AVL树简介     [1]问题的解决     [2]AVL树的性质 2.AVL树的插入旋转操作   (1)术语解释   (2)左单旋     [1]插入到右侧的左边     [2]插入到右侧的右边   (3)右单旋     [1]插入到左侧的左边     [2]插入到左侧的右边   (4)左右双旋    

    2024年02月05日
    浏览(35)
  • [数据结构 C++] AVL树的模拟实现

    问题引入: 在上一篇文章中,我们提到了二叉搜索树在插入时,可能会形成单边树,会降低二叉搜索的性能。因此我们需要平衡二叉搜索树,降低二叉搜索树的高度,使得二叉搜索树趋于一颗完全二叉树的样子,这样就可以提高二叉搜索树的性能。本篇文章就来介绍一种平衡

    2024年02月03日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包