当前位置： 首页 > article >正文

【C++】AVL树|插入|单旋|双旋

article 2025/1/8 14:36:49

 

目录

一，AVL树的概念

 二，AVL树节点的定义

三、AVL树的插入 

四、AVL树的旋转 

4.1 左单旋

4.2 右单旋

4.3 左右双旋

 4.4右左双旋

 五、AVL树的验证

前文对map/multimap/set/multiset进行了介绍，其容器有个共同特点，底层都是红黑树（二叉搜索树），二叉搜索树有个自身的缺陷：当往树中插入的元素有序或者接近有序时，二叉搜索树会退化成单只树，时间复杂度也会退化成O(N)。在这种情况下，map,set等关联式容器对二叉树进行了平衡处理，采用平衡树(AVL).

一，AVL树的概念

当向二叉搜索树中插入新结点后，保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度，这棵树叫 AVL树 

一棵AVL树具有以下性质：

  1. 它的左右子树都是AVL树
  2. 左右子树高度之差(简称平衡因子)的绝对值不超过1 (-1/0/1)
  3. 如果一棵二叉搜索树是高度平衡的，它就是AVL树，如果它有n个结点，其高度可保持在O(logN)，搜索时间复杂度O(logN)

 二，AVL树节点的定义

AVL树节点的定义增加了一个指向父节点的指针，变成了三叉链结构，在原二叉树的基础上，加上平衡因子（调整平衡的作用）。

template<class K,class V>
struct AVLTreeNode	//AVL树节点定义
{
	//构造函数
	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}

	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	
	int _bf;	//平衡因子


};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:

private:
	Node* _root = nullptr;

};

三、AVL树的插入 

 AVL树只是在二叉搜索树的基础上加入了平衡因子，插入步骤也可以按照二叉搜索树来，插入其实只有两步骤：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子

两个步骤进行详细解释： 

（1）进行插入节点 

因为AVL树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照二叉搜索树的插入规则：

待插入结点的key值比当前结点小就插入到该结点的左子树
待插入结点的key值比当前结点大就插入到该结点的右子树
待插入结点的key值与当前结点的 key 值相等就插入失败

 （2）更新平衡因子

插入新节点后，更新平衡因子

  1. 新增结点在parent的右边，parent的平衡因子 ++
  2. 新增结点在parent的左边，parent的平衡因子 --

 更新完一个结点的平衡因子后，都需要进行以下判断： 

  • 如果 parent 的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子

解释：只有parent节点平衡因子为0的时候，才会因为因为插入新节点而改变了平衡因子++/--，所以当更新完平衡因子是-1/1的时候，说明新节点插入进来，打破了原有的平衡，改变了树的高度；

  • 如果 parent 的平衡因子等于0，表明无需继续往上更新平衡因子了

解释：只有原节点parent平衡因子是1/-1的时候（原本就有高度差），新插入节点在树高度较矮的那一边，才会使平衡因子为0，该操作没有改变以parent为根节点的树高度，自然不需要往上更新；

  • 如果parent的平衡因子等于 -2 或者 2，表明此时以 parent 结点为根结点的子树已经不平衡了，需要进行旋转处理

解释：插入前parent根节点树已经平衡因子为1，已经有高度差了，变成2/-2，说明新插入的节点在高度较高的子树上，此时parent节点的左右子树高度差大于1，需要旋转处理

 当parent的平衡因子为 -2或2，需要旋转处理，旋转处理又分四种情况

  1. 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋
  2. 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋
  3. 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋
  4. 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋

	bool insert(const pair<K, V>& kv)
	{
		//判断是否是空树，如若以此新建平衡二叉树
		if (_root == nulptr)
		{
			_root = new Node(kv)
				return true;
		}

		Node* parent = nullptr;
		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);
		if (parent->_kv.first > kv.first)	//插入左边
		{
			parent->_left = cur;
			//更新平衡因子
			parent->_bf--;
		}
		else
		{
			parent->_right = cur;
			parent->_bf++;

		}
		cur->_parent = parent;
	}

四、AVL树的旋转 

4.1 左单旋

步骤如下：

  1. 让 subR 的左子树作为parent的右子树
  2. 让parent作为subR的左子树
  3. 让subR作为整个子树的根
  4. 更新平衡因子

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

		//进行连接
		parent->_right = subRl;
		if(subrL)	//防止该节点不存在 空指针问题
		subRL->_parent = parent;

		subR->_left = parent;
		//判断两种情况，parent是根节点，parent不是跟节点
		Node* ppnode = parent->_parent;

		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else  //不是根节点
		{
			if (ppnode->_left = parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
		//调节平衡因子
		parent->_bf = subR->_bf = 0;
	}

4.2 右单旋

步骤如下：

  1. 让 subL 的右子树作为 parent 的左子树
  2. 让 parent 作为 subL 的右子树
  3. 让 subL 作为整个子树的根
  4. 更新平衡因子

void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;

		//记录
		Node* ppnode = parent->_parent;
		parent->_parent = subL;
		//判断parent节点是否为根节点
		if (parent == root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
				ppnode->_left = subL;
			else
				ppnode->_right = subL;

			subL->_parent = ppnode;
		}
		//调节平衡因子
		parent->_bf = subL->_bf = 0;
	}

4.3 左右双旋

步骤如下：

  1. 以 subL 为旋转点进行左单旋
  2. 以 parent 为旋转点进行右单旋
  3. 更新平衡因子

更新平衡因子  

左右双旋之后，需要进行更新平衡因子，正确更新平衡因子的关键是：记录没有旋转之前 subLR 节点的平衡因子，该平衡因子用于判断以下三种情况：

  • subLR 的平衡因子为1时，说明 subLR 的右子树是新增节点，左右双旋后 parent、subL、subLR 的平衡因子分别更新为0、-1、0
  • subLR 的平衡因子为-1时，说明 subLR 的左子树是新增节点，左右双旋后 parent、subL、subLR 的平衡因子分别更新为1、0、0
  • subLR 的平衡因子为0时，说明 subLR 自己就是新增节点，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0

（1） subLR == -1 

 （2） subLR == 1 

  （3） subLR == 0

左右双旋的代码如下： 

//左右双旋
	void RotateLR(Node* parent)
	{
		//记录subL subLR节点，和subLR翻转前的平衡因子
		//左右双旋
		//更新平衡因子

		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		
		//记录翻转前的subLR的平衡因子
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateLR(parent);

		//更新平衡因子
		if (bf == 1)		//新增节点在subLR右边
		{
			
			subL->_bf = -1;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1)		//新增节点在subLR左边
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 0)		//新增节点就是subLR本身
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			asser(false);
		}
	}

 4.4右左双旋

步骤如下：

  1. 以 subR 为旋转点进行右单旋
  2. 以 parent 为旋转点进行左单旋
  3. 更新平衡因子

更新平衡因子  

右左双旋之后，需要进行更新平衡因子，正确更新平衡因子的关键是：记录没有旋转之前 subLR 节点的平衡因子，该平衡因子用于判断以下三种情况：（与左右双旋一致，右左双旋就是在另一边）

  • subLR 的平衡因子为1时，说明 subLR 的右子树是新增节点，左右双旋后 parent、subL、subLR 的平衡因子分别更新为 -1、0、0
  • subLR 的平衡因子为-1时，说明 subLR 的左子树是新增节点，左右双旋后 parent、subL、subLR 的平衡因子分别更新为 0、1、0
  • subLR 的平衡因子为0时，说明 subLR 自己就是新增节点，左右双旋后parent、subL、subLR的平衡因子分别更新为 0、0、0

（1） subLR == 1

（2） subLR == -1

（3） subLR == 0 

代码如下： 

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

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

		//更新平衡因子
		if (bf == -1)//subRL 的左子树新增
		{
			subR->_bf = 1;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1)//subRL 的右子树新增
		{
			subR->_bf = 0;
			parent->_bf = -1;
			subRL->_bf = 0;
		}
		else if (bf == 0)//subLR 自己就是新增
		{
			subR->_bf = 0;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		else//不是上面三种情况，插入有问题
		{
			assert(false);
		}
	}

 五、AVL树的验证

（1）验证其为二叉搜索树

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

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

（2）验证其为平衡树 

 每个节点子树高度差的绝对值不超过1，进行验证节点的平衡因子是否计算正确，结果为 true 平衡因子正常

//判断平衡因子是否异常
bool IsBalance()
{
	return IsBalance(_root);
}
 
int Height(Node* root)
{
	if (root == nullptr)
		return 0;
 
	int lh = Height(root->_left);
	int rh = Height(root->_right);
 
	return lh > rh ? lh + 1 : rh + 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);
}

 


http://www.kler.cn/a/469998.html

相关文章：

  • visual studio 自动调整代码格式的问题：
  • Flutter鸿蒙化 在鸿蒙应用中添加Flutter页面
  • huggingface 下载方法 测试ok
  • 【HarmonyOS-ArkTS语言】面向对象【合集】
  • (已开源-AAAI25) RCTrans：雷达相机融合3D目标检测模型
  • 场馆预定平台高并发时间段预定实现V1
  • 反向代理模块开发，
  • type1-88
  • python打包open3d问题
  • 尚硅谷· vue3+ts 知识点学习整理 |14h的课程（持续更ing）
  • 如何分析 Nginx 日志
  • 并查集：合并集合
  • （leetcode算法题）137. 只出现一次的数字 II
  • cursor vip
  • AFFAM模型详解及分析
  • Mac软件介绍之录屏软件Filmage Screen
  • day01_ Java概述丶开发环境的搭建丶常用DOS命令
  • 银河麒麟高级服务器操作系统忘记root密码
  • vue管理后台搭建
  • 防止密码爆破debian系统
  • LLM中的Attention实现及优化
  • 【 算法设计与分析-回顾算法知识点】福建师范大学数学与计算机科学学院 2006 — 2007学年第二学期考试 A 卷
  • Spark和Mapreduce对比
  • SpringBoot开发——内置的 ObjectUtils 工具类详解
  • 【C++】类和对象（下）：友元、static成员、内部类、explicit 和 匿名对象
  • VUE3配置后端地址,实现前后端分离及开发、正式环境分离