【C++干货铺】会旋转的二叉树——AVLTree

这篇具有很好参考价值的文章主要介绍了【C++干货铺】会旋转的二叉树——AVLTree。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

=========================================================================

个人主页点击直达:小白不是程序媛

C++系列专栏:C++干货铺

代码仓库:Gitee

=========================================================================

目录

前言

AVL树

AVL树的概念

AVL树结点的定义

AVL树的插入

寻找插入结点的位置

修改平衡因子

 AVL树的旋转

右单旋

左单旋

先右旋再左旋 

先左旋再右旋

 AVL树的验证

AVL树的删除(了解)

AVL树的性能


前言

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


AVL树

AVL树的概念

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

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

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

【C++干货铺】会旋转的二叉树——AVLTree,C++干货铺,c++,开发语言,学习,数据结构,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)
		, _kv(kv)
		, _bf(0)
	{}
};

AVL树的插入

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

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子                                                                                                              3. 将插入后不符合的子树进行旋转调整

寻找插入结点的位置

AVL树是基于搜索二叉树的,搜索二叉树的原则是左小右大。根据这个规则可以找到插入结点的位置。

注:搜索二叉树是没有两个相同的结点的。

//根节点是否为空,如果为空开辟新的结点
		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
			{
				//AVL树是基于搜索二叉树的不会存在相等的情况
				return false;
			}
		}
		//找到要插入的位置进行插入
		//创建新的结点
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			//大于放右边
			parent -> _right = cur;
			cur->_parent = parent;
		}
		else
		{
			//小于放左边
			parent->_left = cur;
			cur->_parent = parent;
		}

修改平衡因子

无论是在哪里插入结点二叉树的高度一定会发生变化高度发生变化平衡因子也会发生变化,因此要对平衡因子进行修改。

		while (parent)
		{
			//当新增结点为左子树时相当于左子树高度加1
			//减数不变,被减数增加,结果减小
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				//当新增结点为右子树时相当于右子树高度加1
				//减数增加,被减数不变,结果增大
				parent->_bf++;
			}


			//添加后左右子树高度相等
			//对父节点往上的结点的平衡因子都没有影响
			if (parent->_bf == 0)
			{
				break;
			}
			//添加节点后对树的高度发生变化
			//继续向上修改平衡
			//对新增结点的父节点的父节点的平衡因子进行修改
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
        }

 AVL树的旋转

结点的插入必然会影响父代及以上结点的平衡因子,从插入结点的父节点往上修改平衡因子,一定会出现平衡因子异常(超过1/0/-1),这时候就要进行旋转操作了。根据插入节点的位置不同,AVL树的旋转分为四种

            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)
				{
					//先右旋在左璇
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					//先左璇在右璇
					RotateLR(parent);
				}

右单旋

新节点插入较高左子树的左侧

【C++干货铺】会旋转的二叉树——AVLTree,C++干货铺,c++,开发语言,学习,数据结构,AVL树,二叉树

抽象图 

【C++干货铺】会旋转的二叉树——AVLTree,C++干货铺,c++,开发语言,学习,数据结构,AVL树,二叉树 

	//右单璇
	void RotateR(Node* parent)
	{
		//拿到旋转结点
		Node* subL = parent->_left;
		//旋转结点的右孩子
		Node* subLR = subL->_right;
		
		//将父亲结点的左孩子更新为旋转结点的右孩子
		parent->_left = subLR;
		
		//判断旋转结点的右孩子是否为空
		if (subLR)
		{
			//不为空更新旋转结点右孩子的父亲
			subLR->_parent = parent;
		}
		//找到父亲节点的父亲结点,准备更新父亲结点未旋转结点
		Node* parentParent = parent->_parent;
		//更新旋转结点的右孩子未父亲结点
		subL->_right = parent;
		//将父亲节点的父节点设置为旋转结点
		parent->_parent = subL;
		//父亲节点有可能未空结点
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			//更新父亲节点为旋转结点
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else 
			{
				parentParent->_right = subL;
			}
			//更新旋转结点的父亲结点,此时选装结点彻底为父亲结点
			subL->_parent = parentParent;
		}
		//更新平衡因子
		subL->_bf = parent->_bf = 0;
	}

左单旋

新节点插入较高右子树的右侧

【C++干货铺】会旋转的二叉树——AVLTree,C++干货铺,c++,开发语言,学习,数据结构,AVL树,二叉树

void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
		{
			subRL->_parent == nullptr;
		}

		

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

先右旋再左旋 

新节点插入较高右子树的左侧

【C++干货铺】会旋转的二叉树——AVLTree,C++干货铺,c++,开发语言,学习,数据结构,AVL树,二叉树

抽象图 

【C++干货铺】会旋转的二叉树——AVLTree,C++干货铺,c++,开发语言,学习,数据结构,AVL树,二叉树 

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

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			// subRL自己就是新增
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			// subRL的右子树新增
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

先左旋再右旋

新节点插入较高左子树的右侧

【C++干货铺】会旋转的二叉树——AVLTree,C++干货铺,c++,开发语言,学习,数据结构,AVL树,二叉树

 

void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		int bf = curright->_bf;

		RotateL(cur);
		RotateR(parent);

		if (bf == 0)
		{
			parent->_bf = cur->_bf = curright->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			cur->_bf = -1;
			curright->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			cur->_bf = 0;
			curright->_bf = 0;
		}
	}

AVL树的验证

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

1. 验证其为二叉搜索树

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

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

2. 验证其为平衡树

  • 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
  • 节点的平衡因子是否计算正确
	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;
	}
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

AVL树的删除(了解)

 因为AVL树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不
错与删除不同的时,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。
具体实现大家可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。


AVL树的性能

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


今天的对数据结构中基于二叉搜索树的AVL树的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,个人主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是我前进的动力!文章来源地址https://www.toymoban.com/news/detail-792016.html

到了这里,关于【C++干货铺】会旋转的二叉树——AVLTree的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】六、线性表中的队列(链式结构实现队列)-CSDN博客  ===========================

    2024年02月08日
    浏览(45)
  • 823.带因子的二叉树

    题目 示例 提示 思路 题目中要的是 父亲节点的val = 左孩子.val * 右孩子的val , 根据题目的意思,单节点也算 c = b*a ,所有看看能不能枚举c =》是可以枚举的,将原有数组进行排序( 升序 ) 当枚举到下标的i的时候,有多少种呢?这里有一个dp数组来做存储 定义dp数组 long[]

    2024年02月10日
    浏览(48)
  • 二叉树 — 返回最大的二叉搜索子树大小

    题目: 给定一棵二叉树的head节点,返回这颗二叉树中最大的二叉搜索子树的大小。 一颗二叉树来讲,可能整棵树不是搜索二叉树,但子树是一颗搜索二叉树。如下图所示,这时要返回这颗子搜索二叉树的最大节点个数。下图中,最大的二叉搜索子树大小为:3(5 - 1 - 7)。

    2024年02月13日
    浏览(50)
  • 每日一题——对称的二叉树

    题目 给定一棵二叉树,判断其是否是自身的镜像(即:是否对称) 例如: 下面这棵二叉树是对称的 下面这棵二叉树不对称。 数据范围:节点数满足 0≤n≤1000,节点上的值满足 ∣val∣≤1000 要求:空间复杂度 O(n),时间复杂度 O(n) 参数说明:二叉树类,二叉树序列化是通过

    2024年02月13日
    浏览(40)
  • 数据结构:二叉树:第3关:基于二叉链表的二叉树的遍历

    任务描述 设二叉树中每个结点的元素均为一个字符,按先序遍历的顺序建立二叉链表,编写三个递归算法分别实现二叉树的先序、中序和后序遍历。 编程要求 输入 多组数据。每组数据一行,为二叉树的前序序列(序列中元素为‘0’时,表示该结点为空)。当输入只有一个

    2024年02月03日
    浏览(42)
  • 【树】建立二叉链表存储的二叉树+遍历二叉树(先序、中序、后序、层序)

    二叉树的构建利用了递归的原理,在按先序序列构建二叉树时,为了能让电脑知道每个结点是否有左右孩子,我们要对原二叉树进行 扩展 ,明确表示每个结点的左右孩子,若当前结点没有左右孩子,我们用’#\\\'表示。 由普通二叉树----扩展二叉树,如下图: 此时当我们按先序

    2024年02月07日
    浏览(39)
  • leetcode 823 带因子的二叉树

    用动态规划 如果两个节点值不同,要乘2,因为两个节点可以互换位置 dp[i] = dp[left] * dp[right] * 2 如果相同 dp[i] = dp[left] * dp[right]

    2024年02月11日
    浏览(36)
  • 头歌 二叉树的二叉链表存储及基本操作

    第1关 先序遍历创建二叉链表存储的二叉树及遍历操作   第2关 计算二叉树的高度、总节点个数和叶子节点个数   第3关 层次遍历二叉树   第4关 递归实现二叉树左右子树交换   第5关 非递归实现二叉树左右子树交换   第6关 非递归实现二叉树的中序遍历

    2024年02月03日
    浏览(31)
  • 【每日一题】823. 带因子的二叉树

    给出一个含有不重复整数元素的数组 arr ,每个整数 arr[i] 均大于 1。 用这些整数来构建二叉树,每个整数可以使用任意次数。其中:每个非叶结点的值应等于它的两个子结点的值的乘积。 满足条件的二叉树一共有多少个?答案可能很大,返回 对 109 + 7 取余 的结果。 示例

    2024年02月11日
    浏览(34)
  • day20 最大的二叉树 合并二叉树 二叉搜索树中的搜索 验证二叉搜索树

    题目链接:654 最大二叉树 题意 根据不重复的整数数组nums构建最大的二叉树 ,根节点是数组中的最大值,最大值左边的子数组构建左子树,最大值右边的子数组构建右子树 nums数组中最少含有1个元素,并且nums中的元素数值均大于等于0 递归  递归三部曲: 1)确定递归函数的

    2024年01月21日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包