【五一创作】|【C++】AVL树的实现

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

1.AVL树概念

二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查
找元素相当于在顺序表中搜索元素,效率低下,
所以在此基础上提出解决办法:
当向二叉搜索树中插入新节结点时,如果能保证每个节点的左右子树高度之差的绝对值不超过1即可降低树的高度,从而减少平均搜索长度
AVL树又称平衡二叉搜索树

2. AVL树性质

AVL树的性质:
1.它的左右子树都是AVL树
2.左右子树高度之差(平衡因子)的绝对值不超过1(1/0/-1)
平衡因子=右子树高度-左子树高度

【五一创作】|【C++】AVL树的实现

3.AVL树的实现

在实现结构与插入功能时,与二叉搜索树有很多相似的地方 :二叉搜索树
所以一部分关于二叉搜索树的地方就不详细说了


【五一创作】|【C++】AVL树的实现

与二叉搜索树定义结构不同的是,多了一个父节点parent以及平衡因子bf

insert

【五一创作】|【C++】AVL树的实现

insert的实现前半部分与二叉搜索树的insert实现大部分相同


【五一创作】|【C++】AVL树的实现

parent的右子树连接新节点为例,出while循环后,需要反向链接父节点,而此时的父节点就为刚才记录cur前一个节点的parent


插入情况分析


1.

【五一创作】|【C++】AVL树的实现

若新增节点作为parent的右子树即cur==parent->right
parent的平衡因子+1 即 parent->bf++


【五一创作】|【C++】AVL树的实现

若新增节点作为parent的左子树即cur==parent->left
parent的平衡因子 -1 即 parent->bf–


3.

【五一创作】|【C++】AVL树的实现

若新增节点作为parent的左子树即cur==parent->left
parent的平衡因子-1 即 parent->bf–


若parent的平衡因子等于1或者-1 即第一种与第二种情况,说明parent所在子树变了,需要继续向上更新爷爷节点
为什么需要继续更新?
说明插入前parent的平衡因子为0,插入前左右高度相等,现在一边高1,高度变了

若parent的平衡因子等于2或者-2 , 说明parent所在子树不平衡,需要以旋转的方式处理子树

若parent的平衡因子等于0, parent所在子树高度不变,就不需要向上更新,插入结束了
为什么插入结束了呢?
插入前parent的平衡因子是-1或者1,插入前一边高一边低,插入节点到矮的那边,高度不变

更新平衡因子

【五一创作】|【C++】AVL树的实现

插入新增节点后,更新平衡因子
如果更新之后,平衡因子没有问题(绝对值<=1),说明插入对树的平衡机构没有影响,不需要处理
如果更新之后,平衡出现问题,平衡结构受到影响(平衡因子为2/-2),需要旋转
插入新增节点,会影响部分/整体祖先

旋转处理

旋转的原则:保持继续是搜索树
旋转的目的:左右均衡,降低高度


【五一创作】|【C++】AVL树的实现

a/b/c分别代表高度为h的AVL子树
平衡因子=右子树深度-左子树深度


情况1——h=0
【五一创作】|【C++】AVL树的实现

当h=0时,60的平衡因子:0-1=-1
30的平衡因子:2-0=2
由于平衡因子出现2,所以需要旋转


情况2——h=1

【五一创作】|【C++】AVL树的实现
当h=2时,60的平衡因子:2-1=1,30的平衡因子:3-1=2
由于平衡因子出现2,所以需要旋转
在parent节点左右插入,都会引发平衡因子变为2


情况3——h=2

【五一创作】|【C++】AVL树的实现

对于c来说,必定是x形状
假设c为y形状

【五一创作】|【C++】AVL树的实现

在左子树新插入一个节点,那这颗子树的平衡因子变为-2,需要旋转,而不会去往上更新到30


【五一创作】|【C++】AVL树的实现

若右子树插入一个节点,parent的平衡因子变为0,不需要往上更新到30


对于a和b,必定是x、y、z中的一种形状

假设abc都是x形状,则在c中插入节点,无论插入左边还是右边,都会导致parent的平衡因子为2或者-2

【五一创作】|【C++】AVL树的实现

c的高度变化,必定引发旋转


【五一创作】|【C++】AVL树的实现

在红框中的四个位置任意一边插入,30的平衡因子都会变为2/-2

虽然分为三种情况,但是旋转的规则是相同

左单旋

以h=1为例

【五一创作】|【C++】AVL树的实现

左单旋的旋转方式:
把B变成30的右边,30变成60的左边,60变成整棵树的根


左单旋抽象图
【五一创作】|【C++】AVL树的实现

【五一创作】|【C++】AVL树的实现

父节点问题
把subR作为30的右子树时,需要更新sub的父节点为parent
把parent作为subR的左子树时,更新parent的父节点为subR

有可能当前旋转的是整棵树或者整棵树的一部分
设置一个ppnode,用于存放parent的父节点
若旋转一部分时,跟ppnode相连接,同时也要判断连接到左子树还是右子树
若旋转整棵树时,父节点置NULL,subR作为新的根


右单旋

【五一创作】|【C++】AVL树的实现
在a处新增节点,使其高度变为h+1,造成旋转
右单旋的旋转方式:
b作为60的左边,60作为30的右边,30变成整棵树的根
右单旋h与左单旋一样,都有h为1、2、3的三种情况,只不过右单旋的插入节点在a处,其他的条件都是相同的


【五一创作】|【C++】AVL树的实现

【五一创作】|【C++】AVL树的实现

右单旋跟左单旋思想相同,
只不过把b作为60的左子树,再把60作为30的右子树
同样考虑父节点问题以及旋转整棵树或者部分子树旋转问题


在insert中判断左右单旋的条件
【五一创作】|【C++】AVL树的实现

当parent的平衡因子为2并且cur的平衡因子为1时,为左单旋


【五一创作】|【C++】AVL树的实现

当parent的平衡因子为-2并且cur的平衡因子为-1时,为右单旋


【五一创作】|【C++】AVL树的实现

双旋转

抽象图

【五一创作】|【C++】AVL树的实现

当h=0时,60作为新增节点

【五一创作】|【C++】AVL树的实现

当h==1时,60的左右子树新增都会引用旋转

【五一创作】|【C++】AVL树的实现

假设在左子树处新增节点

【五一创作】|【C++】AVL树的实现

若h==2时

【五一创作】|【C++】AVL树的实现

a/d是x/y/z中的任意一种
b/c的孩子位置的任意一点插入节点,都会引发旋转

左右双旋

当h==2时, 假设在b的右子树插入节点

【五一创作】|【C++】AVL树的实现
将30进行左旋:30是parent的左子树
将b作为30的右子树,将30作为60的左子树,将60作为90的左子树


【五一创作】|【C++】AVL树的实现
将60进行右旋:60作为整棵树新的根
将60的右子树作为90的左子树,将90作为60的右子树


假设在c的右子树插入新增节点

【五一创作】|【C++】AVL树的实现
新增节点插入在b和c节点,各个位置的平衡因子是不一样的


【五一创作】|【C++】AVL树的实现
当h=0时,左右双旋后,平衡因子与上述两个也是不同的


【五一创作】|【C++】AVL树的实现

【五一创作】|【C++】AVL树的实现

当subLR即60节点处的平衡因子为-1时,说明在b处插入新增节点,
双旋后 subl的平衡因子为0,subLR的平衡因子为0,parent的平衡因子为1

当subLR即60节点处的平衡因子为1时,说明在c处插入新增节点,
双旋后 subl的平衡因子为-1,subLR的平衡因子为0,parent的平衡因子为0

当subLR即60节点处的平衡因子为0时,说明在60即为新增节点,
双旋后 subl的平衡因子为0,subLR的平衡因子为0,parent的平衡因子为0

右左双旋
【五一创作】|【C++】AVL树的实现

当h==0时,60作为新增节点


【五一创作】|【C++】AVL树的实现

当h==1时,60的左右新增节点都会引发旋转


【五一创作】|【C++】AVL树的实现

a/d是x/y/z中任意一个
b和c是一个节点的子树


【五一创作】|【C++】AVL树的实现

b/c的四个孩子位置的任意一个位置新增节点,都会引发旋转


假设在c处新增节点
【五一创作】|【C++】AVL树的实现


【五一创作】|【C++】AVL树的实现
对于90进行右单旋,将c作为90的左子树,将90作为60的右子树


【五一创作】|【C++】AVL树的实现

对30进行左单旋,将b作为30的右子树,将30作为60的左子树

插入引发双旋的场景

1.h==2时,c插入,c的高度变化为h
【五一创作】|【C++】AVL树的实现

刚开始60的平衡因子为1


2…h==2时,b插入,b的高度变化为h
【五一创作】|【C++】AVL树的实现

刚开始60的平衡因子为-1


3. h==1时,60本身就是新增节点

【五一创作】|【C++】AVL树的实现
刚开始60的平衡因子为0


【五一创作】|【C++】AVL树的实现

当subLR即60节点处的平衡因子为1时,说明在c处插入新增节点,
双旋后 subR的平衡因子为0,subRL的平衡因子为0,parent的平衡因子为-1

当subLR即60节点处的平衡因子为-1时,说明在b处插入新增节点,
双旋后 subR的平衡因子为1,subRL的平衡因子为0,parent的平衡因子为0

当subLR即60节点处的平衡因子为0时,说明在60即为新增节点,
双旋后 subR的平衡因子为0,subRL的平衡因子为0,parent的平衡因子为0


【五一创作】|【C++】AVL树的实现

当parent的平衡因子为2,并且cur的平衡因子为-1时,为右左双旋

【五一创作】|【C++】AVL树的实现

中序遍历

【五一创作】|【C++】AVL树的实现

平衡树的中序遍历与搜索树的中序遍历基本一致,root->_kv.first 实际上代表的是kv中key值

如果不懂可以查看:二叉搜索树

判断一颗二叉树是否为平衡树

因为平衡因子是自己更新的,如果更新错了,那检查将无意义
所以通过高度差去判断


在height函数中,求出其左右子树高度,并返回左右子树高度大的加1 即当前树的高度

【五一创作】|【C++】AVL树的实现

在_isbalance函数中,通过左右子树高度差的绝对值 ,判断是否为平衡树 ,即 高度差不超过2

【五一创作】|【C++】AVL树的实现
【五一创作】|【C++】AVL树的实现

在当前情况下,虽然左子树与右子树的高度差为1,
但是并不是平衡树,因为它的右子树节点6的高度差为2
所以还要判断子树是否符合平衡树

【五一创作】|【C++】AVL树的实现


若平衡因子异常,虽然在当前判断平衡树是没有影响的,但是在后续插入判断时,使不该旋转的进行旋转了
所以需要判断下当前root的平衡因子是否与左右子树高度差相等,若不想等则平衡因子异常

【五一创作】|【C++】AVL树的实现文章来源地址https://www.toymoban.com/news/detail-440129.html


整体代码

#include<iostream>
#include<cassert>
using namespace std;
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)
	{
	}
};


template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
   public:
	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;//用于记录cur的前一个节点
		Node* cur = _root;
		while (cur)
		{
			//若插入的值比当前树的值小 插入左边
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			//若插入的值比当前树的值大 插入右边
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//若插入的值,在树中有相同的值 ,则插入失败
				return false;
			}
		}
		cur = new Node(kv);
		//再次判断parent当前节点值与插入值大小
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//cur的上一个节点即为 刚才的记录cur前一个节点的parent
		cur->_parent = parent;



		//更新平衡因子
		while (parent)
		{
			//若插入节点在parent的右子树
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			//若插入节点在parent的左子树
			else
			{
				parent->_bf--;
			}


			if (parent->_bf == 1 || parent->_bf == -1)
			{
				//继续向上更新
				parent = parent->_parent;
				cur = cur->_parent;
			}
			//平衡因子为0,不需要向上更新
			else if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转
				//1.让这颗子树平衡 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);
				}
				else
				{
					assert(false);
				}
				//旋转后整颗树已经平衡了,就不需要在继续了
				break;
			}
		}

		return true;
	}


	void inorder()//中序遍历
	{
		_inorder(_root);
		cout << endl;
	}
	//判断一颗二叉树是否为平衡树
	bool isbalance()
	{
		return _isbalance(_root);
	}
private:
	
	int height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftH = height(root->_left);//左子树高度
		int rightH = height(root->_right);//右子树高度
		//返回左右子树高度大的加1
		return leftH > rightH ? leftH + 1 : rightH + 1;
	}
	bool _isbalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftH = height(root->_left);
		int rightH = height(root->_right);

		if (rightH - leftH != root->_bf)
		{
			cout << root->_kv.first << "节点平衡因子异常" << endl;
			return false;
		 }
		//判断最终绝对值是否小于2
		return abs(leftH - rightH) < 2&&_isbalance(root->_left)&&_isbalance(root->_right);
	}
	 
	void _inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inorder(root->_left);
		cout << root->_kv.first << " ";
		_inorder(root->_right);
	}
	void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL != nullptr)
		{
			subRL->_parent = parent;
		}
		Node* ppnode = parent->_parent;//记录parent的前一个节点

		subR->_left = parent;
		parent->_parent = subR;

		if (ppnode == nullptr)//说明parent是根即代表整棵树
		{
			_root = subR;//subR作为新的根
			_root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
		}
		else//说明旋转的是一部分,所以要跟ppnode相连接
		{
			if (ppnode->_left == parent)//若连接在左子树上
			{
				ppnode->_left = subR;
			}
			else//若连接在右子树上
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;//将subR父节点置为ppnode
		}
		parent->_bf = subR->_bf = 0;//平衡因子都为0
	}

	void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR != nullptr)
		{
			subLR->_parent = parent;
		}
		Node* ppnode = parent->_parent;//记录parent的父节点
		subL->_right = parent;
		parent->_parent = subL;

		if (ppnode == nullptr)//若旋转整棵树
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else//若旋转整棵树的部分子树
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;//使subL的父节点为ppnode
		}
		parent->_bf = subL->_bf = 0;

	}

	void RotateLR(Node* parent)//左右双旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;//记录平衡因子,在后续单旋会置为0
		
		//先对parent的左子树进行左单旋
		RotateL(parent->_left);
		//再对当前根进行右单旋
		RotateR(parent);

		if (bf == -1)//h==2时,在b处插入节点
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)//h==2时,在c处插入节点
		{
			subL ->_bf = -1;
			subLR ->_bf= 0;
			parent->_bf = 0;
		}
		else if (bf == 0)//当h==0时,60作为新增节点
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}

	}

	void RotateRL(Node* parent)//右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;//记录平衡因子,在后续单旋会置为0
		RotateR(parent->_right);
		RotateL(parent);
		//h==2时,c插入,c的高度变化为h
		if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
			subRL->_bf = 0;
		}
		//h==2时,b插入,b的高度变化为h
		else if (bf ==-1)
		{
			subR->_bf = 1;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		// h==1时,60本身就是新增节点
		else if(bf == 0 )
		{
			subR->_bf = 0;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			//不存在情况,若进入则出问题了
			assert(false);
		}
	}

private:
	Node* _root = nullptr;
};


void test_AVLTree1()
{
    //int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14};
	AVLTree<int, int>v1;
	for (auto e : a)
	{
		v1.insert(make_pair(e,e));
	}
	v1.inorder();
	cout << v1.isbalance() << endl;//返回值为布尔值
}


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

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

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

相关文章

  • 【C++】二叉搜索树的模拟实现

    🌇个人主页:平凡的小苏 📚学习格言:命运给你一个低的起点,是想看你精彩的翻盘,而不是让你自甘堕落,脚下的路虽然难走,但我还能走,比起向阳而生,我更想尝试逆风翻盘 。 🛸 C++专栏 : C++内功修炼基地 家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我真

    2024年02月13日
    浏览(36)
  • 【C++】二叉搜索树的原理及实现

      二叉搜索树(Binary Search Tree,BST)是一种常用的数据结构,本文将介绍二叉搜索树的原理与特性,并给出C++代码实现,最后对其性能进行详细的分析。    文章目录 简介 一、二叉搜索树的概念 二、二叉搜索树的操作及实现 2、1 二叉搜索树的插入 2、1、1 插入的原理 2、1、2

    2024年02月14日
    浏览(53)
  • 【C++】平衡二叉搜索树的模拟实现

    🌇个人主页:平凡的小苏 📚学习格言:命运给你一个低的起点,是想看你精彩的翻盘,而不是让你自甘堕落,脚下的路虽然难走,但我还能走,比起向阳而生,我更想尝试逆风翻盘 。 🛸 C++专栏 : C++内功修炼基地 家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我真

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

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

    2024年02月13日
    浏览(38)
  • 【C++庖丁解牛】自平衡二叉搜索树--AVL树

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 前面对map/multimap/set/multiset进行了简单的介绍,在其文档介绍中发现,这几个容器有个共同点是:其底层都

    2024年04月09日
    浏览(97)
  • 【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)

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

    2024年02月06日
    浏览(44)
  • 【C++】AVL树的实现及测试

    AVL树 AVL树也叫平衡二叉搜索树,通过旋转解决了搜索二叉树的不确定性,让整颗树趋近于一颗满二叉树。 1.左右都是一颗AVL树 2.平衡因子的绝对值不会超过1 上图的蓝字表示平衡因子,平衡因子=右子树的高度-左子树的高度 AVL树的插入和二叉搜索树一样,小的在左边,大的在

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

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

    2024年02月03日
    浏览(52)
  • 【C++】set和map的底层AVL树的实现

    AVL树 文章目录 前言 一、AVL树的实现 总结 上一篇文章对 map/multimap/set/multiset 进行了简单的介绍,在其文档介绍中发现,这几个容器有个共同点是: 其底层都是按照二叉搜索树来实现的 ,但是二叉搜索树有其自身的缺陷,假如往树中 插入的元素有序或者接近有序,二叉搜索

    2024年02月06日
    浏览(40)
  • C++力扣题目530--二叉搜索树的最小绝对值

    给你一个二叉搜索树的根节点  root  ,返回  树中任意两不同节点值之间的最小差值  。 差值是一个正数,其数值等于两值之差的绝对值。 示例 1: 示例 2: 树中节点的数目范围是  [2, 104] 0 = Node.val = 105 题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。 注意

    2024年02月02日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包