C++之AVL树的使用以及原理详解

1.AVL树

1.1AVL树的概念

 1.2AVL树的定义

1.3AVL树的插入

 1.4AVL树的旋转

 1. 右单旋

2. 左单旋

3. 左右双旋

4. 右左双旋

 1.5AVL树的验证

1.6AVL的实现

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

1.AVL树

1.1AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

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

A.它的 左右子树都是AVL树

B.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$O(log_2 n)$，搜索时间复杂度O($log_2 n$)

 1.2AVL树的定义

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left; //左子树
	AVLTreeNode<K, V>* _right;//右子树
	AVLTreeNode<K, V>* _parent;//父节点
	int _bf; //平衡因子
	pair<K, V> _kv;
	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

 AVLTreeNode 中的成员包括：

  • _left：指向左子节点的指针。
  • _right：指向右子节点的指针。
  • _parent：指向父节点的指针。
  • _kv：存储键值对的 pair 对象，其中键的类型为 K，值的类型为 V。
  • _bf：平衡因子，用于表示节点的平衡状态。
  • 对于_bf我们通常用一个树的右子树的高度减去左子树的高度来表示_bf

1.3AVL树的插入

AVL树，具有二叉搜索树的性质，同时还在二叉搜索树的基础上增加了平衡因子bf

AVL树的插入分为下面两步：

1、按搜索树规则插入
2、更新平衡因子

对于插入，分为三种情况：

1.插入该节点之后 父节点的平衡因子变为了0（-1变成0  或者   1变成0），这种情况说明插入节点没有对祖先的平衡因子造成影响，不需要进行处理。

更新后，p->bf == 0p所在的子树高度不变，不会影响爷爷说明更新前，p的bf是1 或者 -1，p的矮的那边插入了节点，左右均衡了，p的高度不变，不会影响爷爷
更新结束

2.插入之后父节点的平衡因子变成了1或者-1，这个时候以父节点的平衡因子是从0 变成1或者-1的，说明以父节点为根节点的树的高度发生了变化，并且高度的变化还有可能会影响祖先 的平衡因子，所以这个时候我们需要向上进行判断 祖先节点的平衡因子。

更新后，p->bf==1/-1，p所在的子树的高度变了，会影响爷爷说明更新前，p的bf是0，p的有一边插入，p变得不均衡，但是不违反规则会影响爷爷p的高度变了，
继续往上更新

3.插入之后父节点的平衡因子变成了2或者-2
更新后，p->bf==2/-2,说明p所在的子树违反了平衡规则，需要进行处理 ->旋转

bool Insert(const pair<K, V>& kv)
	{
		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
			{
				return false;
			}
		}

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

		while (parent)
		{
			if(cur == parent->left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
                //pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent
                //的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
                //1. 如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可
                //2. 如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = 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)
				{
					RotateLR(parent);
				}
				else
				{
					RotateRL(parent); //旋转函数的代码看下方
				}
				
				break;
			}
			else
			{
				// 插入之前AVL树就有问题
				assert(false);
			}
		}

		return true;
	}

 1.4AVL树的旋转

如果某个节点的平衡因子因为插入了新的节点变成了2/-2，此时不满足AVL树的规则，那我们就会对该树进行旋转，旋转之后 平衡因子就会回到插入节点之前的 状态，不会对上层产生影响。

 1. 右单旋

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

上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层，

即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：

1. 30节点的右孩子可能存在，也可能不存在

2. 60可能是根节点，也可能是子树

如果是根节点，旋转完成后，要更新根节点

如果是子树，可能是某个节点的左子树，也可能是右子树

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;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}

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

2. 左单旋

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

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

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

		subR->_left = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = subR;

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

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

3. 左右双旋

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

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

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

		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);

		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

4. 右左双旋

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

 

 假如以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为根的子树个高度降低，已经平衡，不需要再向上更新

 1.5AVL树的验证

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);
}

1.6AVL的实现

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf; // balance factor
	pair<K, V> _kv;

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
		, _kv(kv)
	{}
};

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;
		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
			{
				return false;
			}
		}

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

		while (parent)
		{
			if(cur == parent->left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = 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)
				{
					RotateLR(parent);
				}
				else
				{
					RotateRL(parent);
				}
				
				break;
			}
			else
			{
				// 插入之前AVL树就有问题
				assert(false);
			}
		}

		return true;
	}

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

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

		subR->_left = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = subR;

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

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

	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;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}

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

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

		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);

		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

private:
	Node* _root = nullptr;
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/574228.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

说说2024年暑期三下乡社会实践工作新闻投稿经验

说说2024年暑期三下乡社会实践工作新闻投稿经验

作为一名在校大学生,我有幸自去年起参与学院组织的暑期大学生三下乡社会实践团活动。这项活动不仅是我们深入基层、服务社会的重要平台,也是展现当代大学生风采、传递青春正能量的有效途径。然而,如何将这些生动鲜活的实践故事、感人至深的瞬间传播出去,让更多人了解并受到启发…
阅读更多...
火绒安全的应用介绍

火绒安全的应用介绍

火绒安全软件是一款集成了杀毒、防御和管控功能的安全软件&#xff0c;旨在为用户提供全面的计算机安全保障。以下是火绒安全软件的一些详细介绍&#xff1a; 系统兼容性强&#xff1a;该软件支持多种操作系统&#xff0c;包括Windows 11、Windows 10、Windows 8、Windows 7、…
阅读更多...
xgp加速器免费 微软商店xgp用什么加速器

xgp加速器免费 微软商店xgp用什么加速器

2001年11月14日深夜&#xff0c;比尔盖茨亲自来到时代广场&#xff0c;在午夜时分将第一台Xbox交给了来自新泽西的20岁年轻人爱德华格拉克曼&#xff0c;后者在回忆中说&#xff1a;“比尔盖茨就是上帝。”性能超越顶级PC的Xbox让他们趋之若鹜。2000年3月10日&#xff0c;微软宣…
阅读更多...
25-代码随想录第454题.四数相加II

25-代码随想录第454题.四数相加II

25-代码随想录第454题.四数相加II 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) &#xff0c;使得 A[i] B[j] C[k] D[l] 0。 为了使问题简单化&#xff0c;所有的 A, B, C, D 具有相同的长度 N&#xff0c;且 0 ≤ N ≤ 500 。所有整数的范…
阅读更多...
python 笔记ast.literal_eval

python 笔记ast.literal_eval

1 介绍 ast.literal_eval 是 Python 标准库 ast 模块中的一个函数&#xff0c;用于安全地评估表示 Python 字面量或容器&#xff08;如列表、字典、元组、集合&#xff09;的字符串 import ast # 解析并执行一个数字表达式 num ast.literal_eval("3.14") prin…
阅读更多...
OpenFeign微服务调用组件！！！

OpenFeign微服务调用组件！！！

1.Feign是什么 GitHub - OpenFeign/feign: Feign makes writing java http clients easierFeign makes writing java http clients easier. Contribute to OpenFeign/feign development by creating an account on GitHub.https://github.com/OpenFeign/feignFeign是Netflix开…
阅读更多...
项目十一：爬取热搜榜（小白实战级）

项目十一：爬取热搜榜（小白实战级）

首先&#xff0c;恭喜各位也恭喜自已学习爬虫基础到达圆满级&#xff0c;今后的自已python爬虫之旅会随着网络发展而不断进步。回想起来&#xff0c;我学过请求库requests模块、解析库re模块、lmxl模块到数据保存的基本应用方法&#xff0c;这一次的学习python爬虫之旅收获很多…
阅读更多...
Vu3+QuaggaJs实现web页面识别条形码

Vu3+QuaggaJs实现web页面识别条形码

一、什么是QuaggaJs QuaggaJS是一个基于JavaScript的开源图像识别库&#xff0c;可用于识别条形码。 QuaggaJs的作用主要体现在以下几个方面&#xff1a; 实时图像处理与识别&#xff1a;QuaggaJs是一款基于JavaScript的开源库&#xff0c;它允许在Web浏览器中实现实时的图像…
阅读更多...
ASP.NET Core 3 高级编程(第8版) 学习笔记 03

ASP.NET Core 3 高级编程(第8版) 学习笔记 03

本篇介绍原书的第 18 章&#xff0c;为 19 章 Restful Service 编写基础代码。本章实现了如下内容&#xff1a; 1&#xff09;使用 Entity Framework Core 操作 Sql Server 数据库 2&#xff09;Entity Framework Core 数据库迁移和使用种子数据的方法 3&#xff09;使用中间件…
阅读更多...
Qt Quick centerIn和fill 的用法

Qt Quick centerIn和fill 的用法

1&#xff09;Qt Quick centerIn和fill 的用法&#xff1a; import QtQuick 2.5 Rectangle { width:300; height:200; Rectangle { color: "blue"; anchors.fill: parent; border.width: 6; border.co…
阅读更多...
详解工业网关在线探测功能及用途

详解工业网关在线探测功能及用途

工业网关专为工业物联网应用设计&#xff0c;可实现包括不同通讯协议之间的兼容和转换&#xff0c;提供软硬件加密保障工业数据安全传输&#xff0c;发挥强大算力实现数据边缘预处理&#xff0c;联动联调工业网络设备实现高效协同等。在线探测功能是佰马工业网关的一项重要功能…
阅读更多...
unity学习（89）——unity塞满c盘！--删除editor下的log文件

unity学习（89）——unity塞满c盘！--删除editor下的log文件

卸了一个视频后强制续命打开详细信息&#xff1a; 这个再往下找也是没用的&#xff01; 显示隐藏文件夹后&#xff01;执行如下操作&#xff01; 30个g&#xff01; 其中unity占23g editer占了21g 删除C:\Users\王栋林\AppData\Local\Unity\Editor下的log文件 恢复到之前的水…
阅读更多...
使用 Flask 和 WTForms 构建一个用户注册表单

使用 Flask 和 WTForms 构建一个用户注册表单

在这篇技术博客中&#xff0c;我们将使用 Flask 和 WTForms 库来构建一个用户注册表单。我们将创建一个简单的 Flask 应用&#xff0c;并使用 WTForms 定义一个注册表单&#xff0c;包括用户名、密码、确认密码、邮箱、性别、城市和爱好等字段。我们还将为表单添加验证规则&…
阅读更多...
【C 数据结构】图

【C 数据结构】图

文章目录 【 1. 基本原理 】1.1 无向图1.2 有向图1.3 基本知识 【 2. 图的存储结构 】2.1 完全图2.2 稀疏图和稠密图2.3 连通图2.3.1 (普通)连通图连通图 - 无向图非连通图 的 连通分量 2.3.2 强连通图强连通图 - 有向图非强连通有向图 的 强连通分量 2.3.3 生成树 - 连通图2.3…
阅读更多...
美区视频带货“一哥”，一周销量狂干三十万美金！

美区视频带货“一哥”，一周销量狂干三十万美金！

“超店有数显示&#xff0c;Tybuggy上周带货狂揽34.3万美金&#xff0c;超出第二名近30倍。” TikTok风波再起&#xff0c;4月17日&#xff0c;美众议院推出援乌援以军事议案&#xff0c;值得注意的是&#xff0c;TikTok剥离法案被“打包”夹带其中&#xff0c;以此加大再参议…
阅读更多...
LLM应用实战：当KBQA集成LLM(二)

LLM应用实战：当KBQA集成LLM(二)

1. 背景 又两周过去了&#xff0c;本qiang~依然奋斗在上周提到的项目KBQA集成LLM&#xff0c;感兴趣的可通过传送门查阅先前的文章《LLM应用实战&#xff1a;当KBQA集成LLM》。 本次又有什么更新呢&#xff1f;主要是针对上次提到的缺点进行优化改进。主要包含如下方面&#…
阅读更多...
【Linux笔记】基本指令（一）

【Linux笔记】基本指令（一）

一道残阳铺水中 半江瑟瑟半江红 目录 Linux基本指令 罗列目录内容&#xff1a;ls 指令 显示当前目录位置信息&#xff1a;pwd 指令 切换工作目录&#xff1a;cd 指令 创建文件修改时间戳&#xff1a;touch指令 创建空目录&#xff1a;mkdir指令 删除空目录&#xff1a;rmdir指…
阅读更多...
1.3K Star我上位机项目中用了这个开源项目

1.3K Star我上位机项目中用了这个开源项目

软件介绍 ClientServerProject的软件是一款基于C-S&#xff08;客户端-服务器&#xff09;架构的通用开发框架&#xff0c;为中小型系统的快速开发提供强大的支持。该框架由服务端、客户端以及公共组件三部分组成&#xff0c;不仅提供了基础的账户管理、版本控制、软件升级、公…
阅读更多...
输入法重大漏洞曝光，仅华为幸免，近10亿用户受影响

输入法重大漏洞曝光，仅华为幸免，近10亿用户受影响

近日&#xff0c;Citizenlab研究人员调查了多家厂商的输入法应用安全漏洞并报告称&#xff1a;除华为以外&#xff0c;百度、荣耀、科大讯飞、OPPO、三星、腾讯、Vivo和小米等供应商的九款应用程序中有八款均存在安全漏洞。 随着用户规模的不断增长&#xff0c;云输入法应用的…
阅读更多...
kubernetes中DaemonSet控制器

kubernetes中DaemonSet控制器

一、概念 使用DaemonSet控制器&#xff0c;相当于在节点上启动了一个守护进程。通过DaemonSet控制器可以确保在每个节点上运行Pod的一个副本。如果有心的node节点加入集群&#xff0c;则DaemonSet控制器会自动给新加入的节点增加一个Pod的副本&#xff1b;反之&#xff0c;当有…
阅读更多...
最新文章

Copyright @ 2022~2023