【C++】AVL

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

前言

一、AVL 树

1.1、AVL树的概念

1.2、AVL树节点的定义

1.3、AVL树的插入

1.4、AVL树的旋转

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

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

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

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

1.5、AVL树的验证

总结

前言

世上有两种耀眼的光芒，一种是正在升起的太阳，一种是正在努力学习编程的你!一个爱学编程的人。各位看官，我衷心的希望这篇博客能对你们有所帮助，同时也希望各位看官能对我的文章给与点评，希望我们能够携手共同促进进步，在编程的道路上越走越远！

提示：以下是本篇文章正文内容，下面案例可供参考

一、AVL 树

1.1、AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年

发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。

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

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

  • a、节点8的右子树 - 左子树，节点8的平衡因子为1；在8的左子树新增一个节点，则8的平衡因子--，为0；
  • b、节点2的右子树新增一个节点，2的右子树 - 左子树，则2的平衡因子++，为1；
  • d、2节点的平衡因子为1，则1节点右子树所在高度变了，继续往上更新，执行b操作，1节点平衡因子++，为1。

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

1.2、AVL树节点的定义

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;// 该节点的左孩子
	AVLTreeNode<K, V>* _right;// 该节点的右孩子
	AVLTreeNode<K, V>* _parent;// 该节点的父亲节点
	pair<K, V> _kv;// pair类型的对象

	int _bf;  // balance factor平衡因子

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

1.3、AVL树的插入

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

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子
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 = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			// 当前子树出问题了，需要旋转平衡一下
			if (parent->_bf == -2 && cur->_bf == -1)
			{
				RotateR(parent);
			}
			else if (parent->_bf == 2 && cur->_bf == 1)
			{
				RotateL(parent);
			}
			else if (parent->_bf == 2 && cur->_bf == -1)
			{

			}
			else if (parent->_bf == -2 && cur->_bf == 1)
			{

			}

			break;// 旋转完成之后：1、变平衡；2、高度不变，在往上的父亲节点的平衡因子为0
		}
		else
		{
			// 理论而言不可能出现这个情况
			assert(false);
		}
	}

	return true;
}

1.4、AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构， 使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

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

/*
上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左
子树增加了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子
树增加一层，即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有
右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
1. 30节点的右孩子可能存在，也可能不存在
2. 60可能是根节点，也可能是子树
如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树*/

// 右单旋 ---> 从下往上更新到parent的平衡因子为-2的时候，需要发生旋转(传的是平衡因子为-2的父亲节点)
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;
	// subL节点的右子树不为空的话，才能更改subLR的父亲节点
	if (subLR)
		subLR->_parent = parent;

	subL->_right = parent;

	Node* ppNode = parent->_parent;// parent节点不是根的话，提前保留parent节点的父亲节点
	parent->_parent = subL;
	// parent为根
	if (parent == _root)
	{
		_root = subL;// 根更新
		_root->_parent = nullptr;
	}
	// parent不为根
	else
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}

		subL->_parent = ppNode;
	}

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

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

// 左单旋 ---> 从下往上更新到parent的平衡因子为2的时候，需要发生旋转(传的是平衡因子为2的父亲节点)
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	// subRL节点不为空的话，才能更改subRL的父亲节点
	if (subRL)
		subRL->_parent = parent;

	subR->_left = parent;
	Node* ppNode = parent->_parent;// parent节点不是根的话，提前保留parent节点的父亲节点

	parent->_parent = subR;
	// parent为根
	if (parent == _root)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	// parent不为根
	else
	{
		if (ppNode->_right == parent)
		{
			ppNode->_right = subR;
		}
		else
		{
			ppNode->_left = subR;
		}
		subR->_parent = ppNode;
	}

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

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

三种情况会引发旋转：

  1. 如果h > 0，b插入，c的高度变为h，引发旋转；
  2. 如果h > 0，c插入，c的高度变为h，引发旋转；
  3. 如果h == 0，60为新增引发旋转。

将双旋变成单旋后再旋转，即：先对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);
	}
}

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

三种情况会引发旋转：

  1. 如果h > 0，b插入，c的高度变为h，引发旋转；
  2. 如果h > 0，c插入，c的高度变为h，引发旋转；
  3. 如果h == 0，60为新增引发旋转。
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

	RotateR(subR);
	RotateL(parent);

	subRL->_bf = 0;
	if (bf == 1)
	{
		// 在c位置插入
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		// 在b位置插入
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else
	{
		// 60为新增
		parent->_bf = 0;
		subR->_bf = 0;
	}
}

总结：

假如以Parent为根的子树不平衡，即Parent的平衡因子为2或者-2，分以下情况考虑

1. Parent的平衡因子为2，说明Parent的右子树高，设Parent的右子树的根为SubR

  • 当SubR的平衡因子为1时，执行左单旋
  • 当SubR的平衡因子为-1时，执行右左双旋

2. Parent的平衡因子为-2，说明Parent的左子树高，设Parent的左子树的根为SubL

  • 当SubL的平衡因子为-1是，执行右单旋
  • 当SubL的平衡因子为1时，执行左右双旋

旋转完成后，原Parent为根的子树个高度降低，已经平衡，不需要再向上更新。

1.5、AVL树的验证

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

1. 验证其为二叉搜索树

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

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

		_InOrder(root->_left);
		cout << root->_kv.first << endl;
		_InOrder(root->_right);
	}

	void InOrder()
	{
		// 一般在类里面写递归都要套一层
		_InOrder(_root);
	}
void TestAVLTree1()
{
	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> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}

	t.InOrder();
}

2. 验证其为平衡树

  • 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
  • 节点的平衡因子是否计算正确
bool _IsBalance(Node* root, int& height)
{
	if (root == nullptr)
	{
		height = 0;
		return true;
	}

	int leftHeight = 0, rightHeight = 0;
	// 递归式的检查每一个节点的左右子树高度差与平衡因子是否相等
    // 改成后序，效率提高了
	if (!_IsBalance(root->_left, leftHeight)
		|| !_IsBalance(root->_right, rightHeight))
	{
		return false;
	}

	if (abs(rightHeight - leftHeight) >= 2)
	{
		cout << root->_kv.first << "不平衡" << endl;
		return false;
	}
	// 左右子树的高度差与平衡因子不相等
	if (rightHeight - leftHeight != root->_bf)
	{
		cout << root->_kv.first << "平衡因子异常" << endl;
		return false;
	}
	// 保存该节点的高度
	height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

	return true;
}

bool IsBalance()
{
	int height = 0;
	return _IsBalance(_root, height);
}
void TestAVLTree1()
{
	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> t;
	for (auto e : a)
	{
		// 这是一个很好的调试技巧
		// 在if条件语句里打断点来进行调试(空语句是打不住断点的)
		if (e == 14)
		{
			int x = 0;
		}

		t.Insert(make_pair(e, e));

		// 1、先看是插入谁导致出现的问题
		// 2、打条件断点，画出插入前的树
		// 3、单步跟踪，对比图一一分析细节原因
		cout << e << "->" << t.IsBalance() << endl;
	}

	t.InOrder();
	cout << t.IsBalance() << endl;
}

总结

好了，本篇博客到这里就结束了，如果有更好的观点，请及时留言，我会认真观看并学习。
不积硅步，无以至千里；不积小流，无以成江海。

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

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

相关文章

深度论证-高速走线控制100欧姆阻抗一定是最好的选择吗？

深度论证-高速走线控制100欧姆阻抗一定是最好的选择吗？

高速先生成员--黄刚 对于高速差分信号到底需要控制多少欧姆的阻抗&#xff0c;高速先生相信大部分工程师首先都会看下例如信号的协议文档或者芯片的文档&#xff0c;看看里面有没有推荐的控制阻抗值。例如像PCIE信号&#xff0c;在4.0之后的阻抗会明确要求按照85欧姆来控制&…
阅读更多...
240W 宽电压输入 AC/DC 导轨式开关电源——TPR/SDR-240-XS 系列

240W 宽电压输入 AC/DC 导轨式开关电源——TPR/SDR-240-XS 系列

TPR/SDR-240-XS 导轨式开关电源&#xff0c;额定输出功率为240W&#xff0c;产品输入范围&#xff1a;85-264VAC。提供24V、48V输出&#xff0c;具有短路保护&#xff0c;过载保护等功能&#xff0c;并具备高效率&#xff0c;高可靠性、高寿命、更安全、更稳定等特点&#xff0…
阅读更多...
Docker容器中的SSH免密登录

Docker容器中的SSH免密登录

简介&#xff1a;在日常的开发和测试环境中经常需要创建和管理Docker容器。有时&#xff0c;出于调试或管理的目的&#xff0c;可能需要SSH到容器内部。本文将介绍如何创建一个Docker容器&#xff0c;它在启动时自动运行SSH服务&#xff0c;并支持免密登录。 构建支持SSH的Doc…
阅读更多...
对于fastjson之rmi利用问题的解决

对于fastjson之rmi利用问题的解决

前言 也是被一个问题困扰了好久&#xff0c;都要崩溃了&#xff0c;就为了一个问题调试半天的代码&#xff0c;最后终于解决了&#xff0c;现在做一个记录&#xff0c;幸好没有放弃&#xff0c;感觉学java是比较慢的&#xff0c;但是学java就是重在分析能力的提升&#xff0c;…
阅读更多...
关于使用git拉取gitlab仓库的步骤（解决公钥问题和pytho版本和repo版本不对应的问题）

关于使用git拉取gitlab仓库的步骤（解决公钥问题和pytho版本和repo版本不对应的问题）

先获取权限&#xff0c;提交ssh-key 虚拟机连接 GitLab并提交代码_gitlab提交mr-CSDN博客 配置完成上诉步骤之后&#xff0c;执行下列指令进行拉去仓库的内容 sudo apt install repo export PATHpwd/.repo/repo:$PATH python3 "实际路径"/repo init -u ssh://gitxx…
阅读更多...
是谁，又被分布式锁给锁住了？（上）

是谁，又被分布式锁给锁住了？（上）

大家好&#xff0c;我是徒手敲代码。 今天来介绍一下分布式锁。首先思考下这些问题&#xff1a; 为什么需要分布式锁&#xff1f; 基于 Redis 如何实现分布式锁&#xff1f; 单纯使用setNx命令来加锁&#xff0c;会存在什么问题&#xff1f; 经常听到的RedLock&#xff0c;…
阅读更多...
winserver系统设置图片查看器

winserver系统设置图片查看器

新建 .bat 批处理执行文件&#xff0c;内容如下&#xff1a; echo off&cd&color 0a&cls echo Set Win10 Photo Viewer reg add "HKLM\SOFTWARE\Microsoft\Windows Photo Viewer\Capabilities\FileAssociations" /v ".jpg" /t REG_SZ /d Photo…
阅读更多...
SQLserver - 笔记

SQLserver - 笔记

1 SQLserver - 用户管理 4、SQL SERVER数据库用户管理_哔哩哔哩_bilibili 创建用户 - user 2.选择用户&#xff0c;修改属性
阅读更多...
YOLOv8_seg训练流程-原理解析[实例分割理论篇]

YOLOv8_seg训练流程-原理解析[实例分割理论篇]

本篇将介绍一下YOLOv8实例分割网络的训练流程，同样在看此篇文章之前先去看一下预测流程YOLOv8_seg预测流程-原理解析[实例分割理论篇]-CSDN博客 ，还有目标检测任务的训练流程YOLOv8训练流程-原理解析[目标检测理论篇]-CSDN博客 ，这两篇都是前置课程，下图是YOLOv8实例分割的…
阅读更多...
中国教育报，不带广告字样征稿

中国教育报，不带广告字样征稿

急转&#xff01;机会难得&#xff01;《中国教育报》考试版征稿&#xff0c;不带广告字样&#xff01;2300字符&#xff0c;全包操作&#xff0c;两个月左右出&#xff0c;不需要盖章、合同&#xff01;小学初高中老师均可&#xff01; 《中国教育报》是由教育部主管的国家级…
阅读更多...
2024年3月 青少年等级考试机器人理论真题二级

2024年3月 青少年等级考试机器人理论真题二级

202403 青少年等级考试机器人理论真题二级 第 1 题 一个机器小车&#xff0c;用左右两个电机分别控制左右车轮&#xff0c;左侧电机转速是100rpm&#xff0c;右侧电机转速是50rpm&#xff0c;则此机器小车&#xff1f;&#xff08; &#xff09; A&#xff1a;原地右转 B&am…
阅读更多...
深兰科技AI数字伙伴亮相共青团中央12355爱“心”百校行系列活动现场

深兰科技AI数字伙伴亮相共青团中央12355爱“心”百校行系列活动现场

5月12日&#xff0c;共青团中央12355爱“心”百校行活动在江苏南京拉开帷幕。高校心理健康社团师生代表、12355青少年服务台心理咨询师代表&#xff0c;以及相关单位负责同志等共700余人参加&#xff0c;深兰科技AI数字伙伴作为武汉12355青少年服务台的重要青少年心理健康服务产…
阅读更多...
PyQt5中的Tabel View

PyQt5中的Tabel View

文章目录 1. 简介2. 常用方法和信号2.1 常用方法&#xff1a;2.2 常用信号&#xff1a; 3. 常用方法举例说明4. 常用信号举例说明 1. 简介 PyQt5中的TableView是一个用于显示表格数据的组件&#xff0c;它通常用于显示和编辑二维数据集&#xff0c;比如数据库查询结果、CSV文件…
阅读更多...
C++复习 -- 常用关键字

C++复习 -- 常用关键字

this 关键字: 概念 在 C 中&#xff0c; this 关键字是一个指向调用对象的指针。它在成员函数内部使用&#xff0c;用于引用调用该函数的对象。使用 this 可以明确指出成员函数正在操作的是哪个对象的数据成员。 case :证明他就是一个指向被调用对象的指针: #include <iost…
阅读更多...
2024版OWASP移动应用系统10大安全风险简析

2024版OWASP移动应用系统10大安全风险简析

这是自2016年以来该机构首次对移动应用系统相关的风险进行更新&#xff0c;重点增加了对供应链安全、隐私保护等方面的风险关注。 随着移动互联网用户数量急剧增长&#xff0c;移动应用系统已经实现了典型生活场景的全覆盖&#xff0c;并渗透到了多个企业级应用领域。移动应用的…
阅读更多...
HTML飘落的花瓣

HTML飘落的花瓣

目录 写在前面 HTML​​​​​​​简介 完整代码 代码分析 系列推荐 写在最后 写在前面 本期小编给大家推荐HTML实现的飘落的花瓣&#xff0c;无需安装软件&#xff0c;直接下载即可打开~ HTML​​​​​​​简介 HTML&#xff08;Hypertext Markup Language&#xff…
阅读更多...
STM32学习和实践笔记（28）：printf重定向实验

STM32学习和实践笔记（28）：printf重定向实验

1.printf重定向简介 在C语言中printf函数里&#xff0c;默认输出设备是显示器&#xff0c;如果想要用这个函数将输出结果到串口或者LCD上显示&#xff0c;就必须重定义标准库函数里中printf函数调用的与输出设备相关的函数。 比如要使用printf输出到串口&#xff0c;需要先将f…
阅读更多...
灌区信息化管理平台软件如何建设？

灌区信息化管理平台软件如何建设？

随着科技的飞速发展&#xff0c;数字孪生技术正逐渐渗透到各个行业领域&#xff0c;其中&#xff0c;数字孪生灌区的建设成为了智慧水利的重要组成部分。那么&#xff0c;究竟如何进行数字孪生灌区信息化管理平台软件建设呢&#xff1f;本文将为您揭开这一神秘面纱&#xff0c;…
阅读更多...
引用和实体完整性

引用和实体完整性

本文将详细讲解在数据库服务器级具有引用和实体完整性的好处&#xff0c;包括如何在字段中设置默认值、检查约束和引用约束&#xff0c;以及在何时发生约束检查。通过遵循这些指导原则&#xff0c;可以确保数据的一致性和准确性。 1.完整性 完整性指数据库中数据的准确性或正确…
阅读更多...
【Linux线程（二）】线程互斥和同步

【Linux线程（二）】线程互斥和同步

前言&#xff1a; 在上一篇博客中&#xff0c;我们讲解了什么是线程以及如何对线程进行控制&#xff0c;那么了解了这些&#xff0c;我们就可以在程序中创建多线程了&#xff0c;可是多线程往往会带有许多问题&#xff0c;比如竞态条件、死锁、数据竞争、内存泄漏等问题&#…
阅读更多...
最新文章

Copyright @ 2022~2023