【平衡二叉搜索树(AVL)-- 旋转】

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

前言

打怪升级:第60天
【平衡二叉搜索树(AVL)-- 旋转】

AVLTree,也就是我们所说的:自平衡二叉搜索树,AVL命名由来是两位发明者的名字的首字母,并无其他含义。
AVL树有两个重要的特点:

  1. AVL树是一棵搜索树;
  2. AVL树左右子树的高度差的绝对值不大于1;
  3. AVL树的左右子树也是AVL树。
    高度差可取0,1,-1。

注:我们将左右子树的高度差称为平衡因子,简称为bf(Balance Factor)。

  • 既然AVL树是一棵搜索树它就需要满足搜索树的特征:
  1. 左子树不空,左子树上的值都小于根节点的值;
  2. 右子树不空,右子树上的值都大于根节点的值;
  3. 左右子树也都是二叉搜索树。
  • 既然要保持AVL树左右子树的高度差的绝对值不大于1,我们就需要记录以及修改它,这里我们采用的方法是旋转

下面我们首先从二叉搜索树的插入开始引入AVL树的插入,以及之后的旋转操作,话不多说,大家上车。


1、二叉搜索树的插入

根据二叉搜索树的性质:左子树节点的值都小于根,右子树节点的值都大于根,我们可以在插入的时候进行一下判断即可,
需要注意的是:如果出现相同的值我们不进行插入。

	template<class K>
	struct BSTreeNode 
	{
		BSTreeNode(const K& key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{}
	
		struct BSTreeNode* _left;
		struct BSTreeNode* _right;
		K _key;
	};

	bool Insert(const k& key)
	{
		if (_root == nullptr) // 空树 -- 插入的节点作为根
		{
			_root = new Node(key);
		}
		else
		{
			Node* prev = nullptr; // cur的父节点 
			Node* cur = _root;
			while (cur)  // 小放左,大放右,同不加
			{
				if (key < cur->_key)
				{
					prev = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					prev = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}

			if (key < prev->_key)  // 判断插入到prev的左边还是右边
				prev->_left = new Node(key);
			else
				prev->_right = new Node(key);
		}

		return true;
	}

上面的操作就可以让我们实现二叉搜索树的插入,因为AVL树也是一棵二叉搜索树,他也需要符合二叉搜索树的性质,因此有了二叉搜索树的插入我们就可以很方便的写出AVL树的插入过程,
但是AVL树不仅有二叉搜索树的性质还有自己的一些特性:bf的绝对值不大于1,但是插入的过程中我们只考虑了搜索树的性质,因此在插入之后我们需要检查是否符合AVL树的特性,如果符合我们就不做修改,否则就需要进行旋转。


2、AVL树的旋转

bf的计算我们采用右子树高度 减去 左子树高度

我们来理一理什么时候需要进行旋转:

  1. 插入节点后该节点一定是叶子结点没有左右子树,因此bf为0,
    而插入节点后高度收到影响的就是它的所有祖先节点,因此我们需要从该节点开始往上检查它的祖先节点的bf;

  2. 如果插入之后该节点的祖先节点变成了1/-1, 说明该祖先节点原本是0,此时插入之后高度改变了,我们就需要继续往上更新其他祖先节点。

  3. 而如果插入之后该节点的祖先节点变成了0,说明该祖先节点之前是不平衡的(1/-1),插入之后变成了完全平衡,此时整棵树的高度并没有改变,那么我们就不需要往上更新了。

  4. 既然bf的绝对值不可以大于1,那么当插入一个新的节点后它的某个祖先节点的bf变成了±2,就说明出现了问题,我们需要进行旋转,
    在正常情况下当bf变成±2时我们就要进行旋转,因此不会出现bf绝对值大于2的情况。

【平衡二叉搜索树(AVL)-- 旋转】

因为插入节点之后我们需要从该节点出发往上检查它的祖先节点,此处我们采用三叉链。
插入的操作同二叉搜索树,下面我们来将上面的分析过程通过代码实现出来:

struct AVLTreeNode
{
	AVLTreeNode(const int& val)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_val(val)
	{}

	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent; // 指向父亲
	int _bf; // 平衡因子
	int _val; // 数据
	};

 // insert中的调整操作
		parent = cur->_parent;
		while (parent)
		{
			if (cur == parent->_left) --parent->_bf;
			else ++parent->_bf;

			if (parent->_bf == 0) // 说明我们现在使得父亲的左右平衡了,整体h不变,结束调整
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1) // 父亲的h增加,继续向上调整
			{
				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) // 从下往上:左右高,先右旋再左旋
					RotateRL(parent);
				else if (parent->_bf == -2 && cur->_bf == 1) // 从下往上:右左高,先左旋再右旋
					RotateLR(parent);

				break;
			}
			else // 前面就出错了
			{
				assert(false);
			}
		}

旋转操作一共分为4种情况,上方是旋转操作的大框架,下面我们来对它们逐个击破。

(1)右单旋(LL)

右单旋:左子树高,将根节点向右旋转降低左子树的高度并且增加右子树的高度。
由下图我们可以看出 – 经过旋转后三个节点的bf都变为了0 – 根节点的变为了叶子结点,根节点的左子树变为了新的根并且右子树的高度+1。

【平衡二叉搜索树(AVL)-- 旋转】

那么通过上图我们是否可以尝试写出第一份代码?

	void RotateR(Node* parent) // 左高,右单旋
	{
		Node* nodeL = parent->_left;
		
		nodeL->_right = parent;
		parent->_parent = nodeL;
		_root = nodeL; // 更新根节点
		nodeL->parent=nullptr;

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

好像这样就结束了,也没有多复杂嘛,甚至,异常的简单?针对上面的情况我们的确解决了,但是我们来看一看下面的情况:

【平衡二叉搜索树(AVL)-- 旋转】
此时需要旋转的是中间的部分节点,既然是中间的部分,我们就需要链接旧根节点的父节点与新根节点。

【平衡二叉搜索树(AVL)-- 旋转】
此时需要旋转的部分确实是根节点,不过他好像很特殊,新根节点左右子树都有,我们想要将旧根节点作为新根节点的右子树,就需要先保存新根节点的右子树。

上方的就是我们右旋过程过程中会遇到的所以情况,下面我们对右旋的情况进行总结并且写出完整代码。
右旋的步骤:

  1. 旧根节点作为新根节点的右子树,因此我们需要保存新根节点的右子树;
  2. 新根节点的右子树作为旧根节点的左子树;
  3. 旧根节点改变,因此我们需要更改旧根节点的父亲节点,
  4. 通过上面的分析我们发现:最多有4个节点需要发生更改:旧根节点,旧根节点的父亲节点,旧根节点的左孩子(新根节点),新根节点的右孩子 ,而四个节点可以形成三组父子关系,因此我们在右旋时需要修改三组父子关系

下图中的方块表示一颗颗子树,h为树的高度,希望朋友们可以自行尝试画一画h=0、1 、2。。。的情况,可以加深我们对右旋的理解。
【平衡二叉搜索树(AVL)-- 旋转】

	void RotateR(Node* parent) // 左高,右单旋
	{
		Node* nodeL = parent->_left;  // 旧根节点的左节点 -- 新根节点
		Node* nodeLR = nodeL->_right;  // 左子树的右子树
		Node* nodePP = parent->_parent; // 旧根节点的父节点

		parent->_left = nodeLR;
		if (nodeLR != nullptr) //  左子树的右子树不为空
			nodeLR->_parent = parent;

		nodeL->_right = parent;
		parent->_parent = nodeL;

		nodeL->_parent = nodePP;
		if (nodePP == nullptr) // 根
		{
			_root = nodeL;
		}
		else // 更新父节点的孩子
		{
			if (nodePP->_left == parent)
				nodePP->_left = nodeL;
			else
				nodePP->_right = nodeL;
		}
		// 更新bf
		parent->_bf = nodeL->_bf = 0; 
	}

动图图解:
【平衡二叉搜索树(AVL)-- 旋转】【平衡二叉搜索树(AVL)-- 旋转】【平衡二叉搜索树(AVL)-- 旋转】

(2)左单旋(RR)

左旋的步骤:

  1. 旧根节点作为新根节点的左子树,因此我们需要保存新根节点的左子树;
  2. 新根节点的左子树作为旧根节点的右子树;
  3. 旧根节点改变,因此我们需要更改旧根节点的父亲节点,
  4. 通过上面的分析我们发现:最多有4个节点需要发生更改:旧根节点,旧根节点的父亲节点,旧根节点的右孩子(新根节点),新根节点的左孩子 ,而四个节点可以形成三组父子关系,因此我们在右旋时需要修改三组父子关系

同右单旋基本一样,下方给出统一图形以及代码解析:

【平衡二叉搜索树(AVL)-- 旋转】

	void RotateL(Node* parent) // 右高,左单旋 -- 或者说叫做右右高,左单旋
	{
		Node* nodeR = parent->_right;
		Node* nodeRL = nodeR->_left;
		Node* nodePP = parent->_parent;

		parent->_right = nodeRL;
		if (nodeRL) nodeRL->_parent = parent;

		nodeR->_left = parent;
		parent->_parent = nodeR;

		if (nodePP) // 不是根节点
		{
			if (parent == nodePP->_left)
				nodePP->_left = nodeR;
			else
				nodePP->_right = nodeR;
		}
		else
		{
			_root = nodeR;
		}
		nodeR->_parent = nodePP;

		// 更改bf
		parent->_bf = nodeR->_bf = 0;
	}

(3)右左双旋(LR)

在左单旋和右单旋的情况下,我们遇到的都是:根节点和它的孩子节点都是同一边高,如下图:
左:parent与nodeL都是左子树高
右:parent与nodeR都是右子树高

【平衡二叉搜索树(AVL)-- 旋转】

下边这种情况:
parent右子树高,nodeR左子树高,此时如果单单使用一次左旋或者右旋无法解决我们不平衡问题。
【平衡二叉搜索树(AVL)-- 旋转】
这种父亲和孩子高度差不在同一边的情况下我们可以将nodeR的方向转换一下,将nodeR右旋之后parent与nodeR的高度差就达到了统一,
此时再对根节点进行一次左旋就可以达到平衡的目的。

【平衡二叉搜索树(AVL)-- 旋转】

我们实际上会遇到的情况一共有以下三种:

【平衡二叉搜索树(AVL)-- 旋转】

只是看图的话好像看不出来点什么,那么我们看一看平衡之后 parent 与 nodeR的bf,新的根节点的bf一定为0,而parent与nodeR的bf却是不断变化的,那么为什么会有出现这三种情况?
这与nodeR的左孩子的孩子有关,它是否有孩子,以及有的是左孩子还是右孩子都会出现不一样的结果,
而单纯的左旋与右旋之后都会将parent与nodeR设置为0,因此这里需要我们进行特殊处理,
我们可以nodeR的左孩子的bf来判断parent与nodeR的bf
具体代码如下:

	void RotateRL(Node* parent) // 从下往上:左右高,先右旋再左旋
	{
		// 旋转
		Node* nodeR = parent->_right;
		Node* nodeRL = nodeR->_left;
		int bf = nodeRL->_bf;   // 用来判断
		RotateR(nodeR);       // 复用
		RotateL(parent);

		// 更改bf
		nodeRL->_bf = 0;
		if (bf == 1)
		{
			parent->_bf = -1;
			nodeR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			nodeR->_bf = 1;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			nodeR->_bf = 0;
		}
		else  // 走到这一步说明在插入新节点之前就出问题了
		{
			assert(false);
		}

	}

【平衡二叉搜索树(AVL)-- 旋转】

(4)左右双旋(RL)

类比右左双旋。
注:小标题中的 RL指的是:nodeL的右子树高,parent的左子树高
左右双旋指的是:先左旋再右旋

	void RotateLR(Node* parent)  // 从下往上:右左高,先左旋再右旋
	{
		
		Node* nodeL = parent->_left;
		Node* nodeLR = nodeL->_right;
		int bf = nodeLR->_bf;

		// 旋转
		RotateL(nodeL);
		RotateR(parent);

		// 更改bf
		nodeLR->_bf = 0;
		if (bf == -1)
		{
			nodeL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			nodeL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			nodeL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

完整插入代码以及打印验证

#pragma once
#include<iostream>
using namespace std;
#include<cassert>

class AVLTree
{
	typedef AVLTreeNode Node;
public:
	AVLTree()
		:_root(nullptr)
	{}

	bool Insert(const int& p)
	{
		// 插入 -- 找好位置后需要更新bf
		if (_root == nullptr)
		{
			_root = new Node(p);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_val < p)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_val > p)
			{
				parent = cur;
				cur = cur->_left;
			}
			else  // 已经存在
				return false; 
		}	

		cur = new Node(p);
		if (cur->_kv.first < parent->_kv.first)
			parent->_left = cur;
		else
			parent->_right = cur;
		cur->_parent = parent;

		// 开始向上调整bf,判断是否需要旋转 == 2/-2
		while (parent)
		{
			if (cur == parent->_left) --parent->_bf;
			else ++parent->_bf;

			if (parent->_bf == 0) // 说明我们现在使得父亲的左右平衡了,整体h不变,结束调整
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1) // 父亲的h增加,继续向上调整
			{
				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) // 从下往上:左右高,先右旋再左旋
					RotateRL(parent);
				else if (parent->_bf == -2 && cur->_bf == 1) // 从下往上:右左高,先左旋再右旋
					RotateLR(parent);

				break;
			}
			else // 前面就出错了
			{
				assert(false);
			}
		}

		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
	}
private:

	void _InOrder(Node* root)
	{
		if (root == nullptr) return;

		_InOrder(root->_left);
		cout << root->_val << ", \t" << root->_bf << endl;
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
};

3、为什么需要AVL树

有的朋友会有疑问:既然我们已经有了搜索二叉树,而且查找效率也十分不错,为什么还要专门来一个平衡二叉搜索树,这样有必要吗,
嗯~答案肯定是有的,而且,十分有,
在存储数据方面我们有了单链表与数组就已经足够了,之所以更加费事地设计二叉树这种结构并不是因为它长得更优美好看,而是想要利用它,通过对它的存储方式进行限制来达到快速查询的效果 – 二叉搜索树,二叉树在设计之初就不是为了插入和删除。
但是,实际情况下二叉搜索树的形态与插入数据的顺序有很大关系,乱序插入更有利于形成“健康的”二叉搜索树,
如果我的插入的数据是一组接近有序序列,那么得到的二叉树就是一棵“歪脖子树”,甚至是单链表:
【平衡二叉搜索树(AVL)-- 旋转】

这时对数据的查找效率接近O(N),基本上是遍历一整颗树,因此,在插入过程中我们需要对它进行调整,保证它是一棵“健康的”二叉树,
这样才可以保证查询的高效性:【平衡二叉搜索树(AVL)-- 旋转】


总结

旋转是为了在保持平衡树性质的前提下降低树的高度,右子树高就左旋,左子树高就右旋。
如果你还有一些疑问未得到解答,可以查看完整代码部分的旋转情况判断,这一些判断条件可以给你很好的启发,配合上自己动手画图,我相信你一定掌握它。

文章中的动图来源:AVL Tree测试文章来源地址https://www.toymoban.com/news/detail-431450.html



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

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

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

相关文章

  • 【数据结构】平衡二叉搜索树(AVL树)——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改

      为什么要引入平衡二叉搜索树?   在之前我们学习了二叉搜索树,二叉搜索树的结构类似于一个倒置的树,而左子树的值小于根节点的值,右节点的值大于根节点的值,这种结构使得二叉搜索树在处理有序数据时非常高效。但是如果 在传入的数据为有序或接近有序,

    2024年02月07日
    浏览(47)
  • C++数据结构之平衡二叉搜索树(一)——AVL的实现(zig与zag/左右双旋/3+4重构)

    本文是介绍众多平衡二叉搜索树(BBST)的第一篇——介绍AVL树。故先来引入BBST的概念。由于上一篇介绍的二叉搜索树(BST)在极度退化的情况下,十分不平衡,不平衡到只朝一侧偏,成为一条链表,复杂度可达 O ( n ) O(n) O ( n ) ,所以我们要在“平衡”方面做一些约束,以防

    2024年02月13日
    浏览(36)
  • 【C++】AVL树(平衡二叉树)

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

    2024年02月12日
    浏览(38)
  • AVL——平衡搜索树

    ✅1主页 :我的代码爱吃辣 📃2知识讲解 :数据结构——AVL树 ☂️3开发环境 :Visual Studio 2022 💬4前言 :AVL树是对二叉搜索树的严格高度控制,所以AVL树的搜索效率很高,但是这是需要付出很大的代价的,要维护父亲指针,和平衡因子。 目录 一.AVL的概念 二. AVL树节点及整体

    2024年02月11日
    浏览(30)
  • 【C++】AVL树(高度平衡二叉树)

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

    2024年02月11日
    浏览(34)
  • 【C++练级之路】【Lv.15】AVL树(双子旋转,领略绝对平衡之美)

    快乐的流畅:个人主页 个人专栏:《C语言》《数据结构世界》《进击的C++》 远方有一堆篝火,在为久候之人燃烧! 之前讲解了二叉搜索树,最优情况下它具有非常好的搜索性能,但是在极端场景下,它可能退化为单支树,可以形象地称为歪脖子树~ 这样的话,它搜索的时间

    2024年03月25日
    浏览(38)
  • C语言-实现顺序二叉树和平衡二叉树AVL

    在实现二叉树之前先看下结构体的一些使用方法 数组是保存一系列相同的数据。在实际问题中,一组数据往往有很多种不同的数据类型。例如,登记学生的信息,可能需要用到 char型的姓名,int型或 char型的学号,int型的年龄 访问结构成员 访问其中的各个元素,用结构成员运

    2023年04月14日
    浏览(30)
  • 【数据结构与算法】平衡二叉树(AVL树)

    给你一个数列{1,2,3,4,5,6},要求创建二叉排序树(BST),并分析问题所在。 BST 存在的问题分析 : 左子树全部为空,从形式上看,更像一个单链表。 插入速度没有影响。 查询速度明显降低(因为需要依次比较),不能发挥 BST 的优势,因为每次还需要比较左子树,其查询速度

    2024年02月13日
    浏览(39)
  • 计算机基础--->数据结构(6)【AVL树(平衡二叉树)】

    平衡二叉树是一种特殊的二叉搜索树,他的左子树与右子树的高度差不超过1。并且左右两个子树都是一颗平衡二叉树。保持平衡的特性使得平衡二叉树的查询、插入和删除操作在平均和最坏情况下的时间复杂度都是 O(logn) ,其中n是树中节点的数量。 相比于普通的二叉搜索树

    2024年02月12日
    浏览(54)
  • 【树】 二叉树 堆与堆排序 平衡(AVL)树 红黑(RB)树

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 有一个特殊的结点,称为根结点,根节点没有前驱结点 除根节点外,其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1= i= m)又是一棵结构与树类似的子树。每棵子

    2024年02月14日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包