【数据结构】AVL 树

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


【数据结构】AVL 树,数据结构,数据结构,c++

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

1. AVL 树的概念

二叉搜索树虽可以缩短查找的效率,但如果数据有序或者接近有序,二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法:当向二叉搜索树中插入新节点后,如果能保证每个节点的左右子树高度之差的绝对值不超过 1(需要对树中的节点进行调整),即可降低树的高度,从而减少平均搜索长度。

一棵 AVL 树或者是空树,或者是具有以下性质的二叉搜索树:

  • 它的左右子树都是 AVL 树;
  • 左右子树高度之差(简称平衡因子)的绝对值不超过 1(-1 / 0 / 1)。

【数据结构】AVL 树,数据结构,数据结构,c++

如果一棵二叉搜索树是高度平衡的,它就是 AVL 树。如果它有 n 个节点,其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n),搜索时间复杂度是 O ( l o g 2 n ) O(log_2 n) O(log2n)

2. AVL 树节点的定义

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data)
		: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
		, _data(data), _bf(0)
	{}
	
	AVLTreeNode<T>* _pLeft;		// 该节点的左孩子
	AVLTreeNode<T>* _pRight; 	// 该节点的右孩子
	AVLTreeNode<T>* _pParent; 	// 该节点的双亲
	T _data;
	int _bf; 					// 该节点的平衡因子
};

3. AVL 树的插入

AVL 树就是在二叉搜索树的基础上引入了平衡因子,因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步:

  1. 按照二叉搜索树的方式插入新节点;
  2. 调整节点的平衡因子。
bool Insert(const T& data)
{
	// 1. 先按照二叉搜索树的规则将节点插入到AVL树中
	// ...
	
	// 2. 新节点插入后,AVL树的平衡性可能会遭到破坏,此时就需要更新平衡因子,并检测是否破坏了AVL树的平衡性
	
	/*
	pCur插入后,pParent的平衡因子一定需要调整,在插入之前,pParent
	的平衡因子分为三种情况:-1,0, 1, 分以下两种情况:
		1. 如果pCur插入到pParent的左侧,只需给pParent的平衡因子-1即可
		2. 如果pCur插入到pParent的右侧,只需给pParent的平衡因子+1即可

	此时:pParent的平衡因子可能有三种情况:0,正负1,正负2
		1. 如果pParent的平衡因子为0,说明插入之前pParent的平衡因子为正负1,插入后被调整
		   成0,此时满足AVL树的性质,插入成功
		2. 如果pParent的平衡因子为正负1,说明插入前pParent的平衡因子一定为0,插入后被更
		   新成正负1,此时以pParent为根的树的高度增加,需要继续向上更新
		3. 如果pParent的平衡因子为正负2,则pParent的平衡因子违反平衡树的性质,需要对其进
		   行旋转处理
	*/

	while (pParent)
	{
		// 更新双亲的平衡因子
		if (pCur == pParent->_pLeft)
			pParent->_bf--;
		else
			pParent->_bf++;
			
		// 更新后检测双亲的平衡因子
		if (0 == pParent->_bf)
		{
			break;
		}
		else if (1 == pParent->_bf || -1 == pParent->_bf)
		{
			// 插入前双亲的平衡因子是0,插入后双亲的平衡因为为1或者-1,说明以双亲为根的二叉树
			// 的高度增加了一层,因此需要继续向上调整
			pCur = pParent;
			pParent = pCur->_pParent;
		}
		else
		{
			// 双亲的平衡因子为正负2,违反了AVL树的平衡性,需要对以pParent
			// 为根的树进行旋转处理
			if (2 == pParent->_bf)
			{
				// ...
			}
			else
			{
				// ...
			}
		}
	}
	return true;
}

4. AVL 树的旋转

如果在一棵原本是平衡的 AVL 树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡化。根据节点插入位置的不同,AVL 树的旋转分为四种:

  1. 新节点插入较高左子树的左侧 - 左左:右单旋

    【数据结构】AVL 树,数据结构,数据结构,c++

    /*
    	上图在插入前,AVL树是平衡的,新节点插入到30的左子树(注意:此处不是左孩子)中,30左
    子树增加了一层,导致以60为根的二叉树不平衡,要让60平衡,只能将60左子树的高度减少一层,右子
    树增加一层,即将左子树往上提,这样60转下来,因为60比30大,只能将其放在30的右子树,而如果30有
    右子树,右子树根的值一定大于30,小于60,只能将其放在60的左子树,旋转完成后,更新节点
    的平衡因子即可。在旋转过程中,有以下几种情况需要考虑:
    	1. 30节点的右孩子可能存在,也可能不存在
    	2. 60可能是根节点,也可能是子树
    	   如果是根节点,旋转完成后,要更新根节点
    	   如果是子树,可能是某个节点的左子树,也可能是右子树
    */
    
    void _RotateR(PNode pParent)
    {
    	// pSubL: pParent的左孩子
    	// pSubLR: pParent左孩子的右孩子,注意:该
    	PNode pSubL = pParent->_pLeft;
    	PNode pSubLR = pSubL->_pRight;
    	
    	// 旋转完成之后,30的右孩子作为双亲的左孩子
    	pParent->_pLeft = pSubLR;
    	// 如果30的左孩子的右孩子存在,更新亲双亲
    	if (pSubLR)
    		pSubLR->_pParent = pParent;
    		
    	// 60 作为 30的右孩子
    	pSubL->_pRight = pParent;
    	
    	// 因为60可能是棵子树,因此在更新其双亲前必须先保存60的双亲
    	PNode pPParent = pParent->_pParent;
    	
    	// 更新60的双亲
    	pParent->_pParent = pSubL;
    	
    	// 更新30的双亲
    	pSubL->_pParent = pPParent;
    	
    	// 如果60是根节点,根新指向根节点的指针
    	if (NULL == pPParent)
    	{
    		_pRoot = pSubL;
    		pSubL->_pParent = NULL;
    	}
    	else
    	{
    		// 如果60是子树,可能是其双亲的左子树,也可能是右子树
    		if (pPParent->_pLeft == pParent)
    			pPParent->_pLeft = pSubL;
    		else
    			pPParent->_pRight = pSubL;
    	}
    	
    	// 根据调整后的结构更新部分节点的平衡因子
    	pParent->_bf = pSubL->_bf = 0;
    }
    
  2. 新节点插入较高右子树的右侧 - 右右:左单旋

    【数据结构】AVL 树,数据结构,数据结构,c++

    实现及情况考虑可参考右单旋。

  3. 新节点插入较高左子树的右侧 - 左右:先左单旋再右单旋

    【数据结构】AVL 树,数据结构,数据结构,c++

    将双旋变成单旋后再旋转,即:先对 30 进行左单旋,然后再对 90 进行右单旋,旋转完成后再考虑平衡因子的更新。

    // 旋转之前,60的平衡因子可能是-1/0/1,旋转完成之后,根据情况对其他节点的平衡因子进行调整
    void _RotateLR(PNode pParent)
    {
    	PNode pSubL = pParent->_pLeft;
    	PNode pSubLR = pSubL->_pRight;
    	
    	// 旋转之前,保存pSubLR的平衡因子,旋转完成之后,需要根据该平衡因子来调整其他节点的平衡因子
    	int bf = pSubLR->_bf;
    	
    	// 先对30进行左单旋
    	_RotateL(pParent->_pLeft);
    	
    	// 再对90进行右单旋
    	_RotateR(pParent);
    	
    	if (1 == bf)
    		pSubL->_bf = -1;
    	else if (-1 == bf)
    		pParent->_bf = 1;
    }
    
  4. 新节点插入较高右子树的左侧 - 右左:先右单旋再左单旋

    【数据结构】AVL 树,数据结构,数据结构,c++

    参考左右双旋。

总结:

假如以 pParent 为根的子树不平衡,即 pParent 的平衡因子为 2 或者 -2,分以下情况考虑:

  1. pParent 的平衡因子为 2,说明 pParent 的右子树高,设 pParent 的右子树的根为 pSubR:

    • 当 pSubR 的平衡因子为 1 时,执行左单旋;
    • 当 pSubR 的平衡因子为 -1 时,执行右左双旋。
  2. pParent 的平衡因子为 -2,说明 pParent 的左子树高,设 pParent 的左子树的根为 pSubL:

    • 当 pSubL 的平衡因子为 -1 时,执行右单旋;
    • 当 pSubL 的平衡因子为 1 时,执行左右双旋。

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

5. AVL 树的验证

AVL 树是再二叉搜索树的基础上加入了平衡性的限制,因此要验证 AVL 树,可以分两步:

  1. 验证其为二叉搜索树

    如果中序遍历可得到一个有序的序列,就说明为二叉搜索树。

  2. 验证其为平衡树

    • 每个节点子树高度差的绝对值不超过 1(注意节点中如果没有平衡因子);

    • 节点的平衡因子是否计算正确。

      int _Height(PNode pRoot);
      bool _IsBalanceTree(PNode pRoot)
      {
      	// 空树也是AVL树
      	if (nullptr == pRoot) return true;
      	
      	// 计算pRoot节点的平衡因子:即pRoot左右子树的高度差
      	int leftHeight = _Height(pRoot->_pLeft);
      	int rightHeight = _Height(pRoot->_pRight);
      	int diff = rightHeight - leftHeight;
      	
      	// 如果计算出的平衡因子与pRoot的平衡因子不相等,或者pRoot平衡因子的绝对值超过1,则一定不是AVL树
      	if (diff != pRoot->_bf || (diff > 1 || diff < -1))
      		return false;
      		
      	// pRoot的左和右如果都是AVL树,则该树一定是AVL树
      	return _IsBalanceTree(pRoot->_pLeft) && _IsBalanceTree(pRoot -> _pRight);
      }
      
  3. 验证用例

    • 常规场景

      { 16, 3, 7, 11, 9, 26, 18, 14, 15 }

    • 特殊场景

      { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }

      【数据结构】AVL 树,数据结构,数据结构,c++

6. AVL 树的删除

因为 AVL 树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不过与删除不同的是,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。

7. AVL 树的性能

AVL 树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过 1,这样可以保证查询时高效的时间复杂度,即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对 AVL 树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的时在删除时,又可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑 AVL 树,但一个结构经常修改,就不太适合。文章来源地址https://www.toymoban.com/news/detail-848880.html


END

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

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

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

相关文章

  • 数据结构进阶(一):AVL树

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

    2024年02月12日
    浏览(35)
  • C++&&数据结构——AVL树

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

    2024年01月19日
    浏览(66)
  • 【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

领红包