【C++进阶】深度解析AVL树及其简单模拟实现

AVL树的解析和模拟实现

  • 一，什么是AVL树
  • 二，AVL树的特性
  • 三，模拟实现
    • 1. 基本框架
    • 2. 插入（不带旋转）
    • 2. AVL树的旋转
    • 3. AVL树的验证
  • 四，总结

一，什么是AVL树

之前我们学习了二叉搜索树，但是有时候因为节点插入的问题，可能会退化为单支树，这样会导致查找效率变得底下如顺序表。
因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度

这种树就是AVL树.

二，AVL树的特性

AVL树满足两个条件：

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

平衡因子=右子树高度-左子树高度

在这里插入图片描述
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2​n)，搜索时间复杂度O( l o g 2 n log_2 n log2​n)

三，模拟实现

1. 基本框架

AVL树是一种平衡二叉树，其内部存储的是pair键值对，我们模拟实现的时候直接用pair来存储即可。
我们先来写AVL的节点定义：
每个节点都要有一个平衡因子用来保证其AVL树特性

template<class K,class V>
struct AVLTreeNode {
	typedef AVLTreeNode<K, V> Node;

	AVLTreeNode(const pair<K,V> &kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
	
	Node* _left;
	Node* _right;
	Node* _parent;//记录当前节点的父亲
	int _bf;//记录节点的平衡因子
	pair<K, V> _kv;//保存记录的key,val

};

然后我们来写AVL的框架：

template<class K,class V>
class AVLTree {
	typedef AVLTreeNode<K, V> Node;
public:
	//...
private:
	Node* _root = nullptr;

};

2. 插入（不带旋转）

下面我们来实现AVL树的插入：
插入分为两步：

  1. 按照二叉搜索树那样插入节点
  2. 调整平衡因子

插入节点的部分和二叉搜索树的代码一样，主要是修改平衡因子的部分

当插入新节点后，这个新节点的双亲节点的平衡因子会发生变化:
1.新插入的节点cur在其双亲节点parent的左孩子时，parent的平衡因子-1
2. 新插入的节点在parent的右孩子时，parent的平衡因子+1

代码如下：

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 (kv.first > cur->_kv.first) {
				parent = cur;
				cur = cur->_right;
				
			}
			else if (kv.first < cur->_kv.first) {
				parent = cur;
				cur = cur->_left;
				
			}
			else {
				return false;
			}
		}
		//找到了插入位置
		cur = new Node(kv);
		if (kv.first > parent->_kv.first) {
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		cur->_parent = parent;

		//修改平衡因子
		while (parent) {
			if (cur == parent->_left) {//如果加在左边，则父节点的平衡因子--
				parent->_bf--;
			}
			else {
				parent->_bf++;//右边则++
			}
			//调整平衡因子
			//...

		}
		return true;
}

修改后这里有三种情况：

  1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功
  2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新
  3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理

我们先来说前两种情况，第三种我们在旋转中讲解

第一种情况：
修改后parent的平衡因子为0，这里就不用再进行调整了
在这里插入图片描述

第二种情况：
修改后平衡因子为1，则以parent为根的这颗树的高度发生了变化，则要继续向上调整平衡因子
在这里插入图片描述
代码：

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 (kv.first > cur->_kv.first) {
				parent = cur;
				cur = cur->_right;
				
			}
			else if (kv.first < cur->_kv.first) {
				parent = cur;
				cur = cur->_left;
				
			}
			else {
				return false;
			}
		}
		//找到了插入位置
		cur = new Node(kv);
		if (kv.first > parent->_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) {
				//旋转
				
			}
			else {
				assert(false);//说明插入之前就有问题
			}
		}
		return true;

	}

2. AVL树的旋转

上面的两种情况，更新parent的平衡因子后AVL树的特性还保持着，但是第三种情况更新后，双亲的平衡因子为2/-2，破坏了平衡二叉搜索树的特性，所以就要进行以parent为根的树的旋转

AVL树的旋转也分为四种情况

1. 新节点插入较高左子树的左侧：右单旋
2. 新节点插入较高右子树的右侧：左单旋
3. 新节点插入较高左子树的右侧—左右双旋：先左单旋再右单旋
4. 新节点插入较高右子树的左侧—右左双旋：先右单旋再左单旋

下面我们来依次解释：

右单旋：

右单旋是新插入的节点在左子树中，使其整棵树右高左低，所以要旋转右子树来降低高度差使这棵树变得平衡

具体过程看下图：
在这里插入图片描述
这里我们来看一下具体当各子树高度的情况：

在这里插入图片描述

下面我们来编写一下右单璇的代码：
首先我们定义两个节点用来标记当前需要旋转的节点。
在这里插入图片描述

对于右单旋，我们找当前parent的左孩子 subL 和该左孩子的右孩子 subLR

然后我们在旋转时还要注意一下：
（1） 30这个节点的右子树可能存在也可能不存在
不存在时我们就不能直接将subL的parent指针直接指向60

void RotateR(Node* parent) {//右单旋
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		
		parent->_left = subLR;
		if (subLR) {//当subLR存在时，subLR的parent才指向parent
			subLR->_parent = parent;
		}
		//...
}

（2） 60这个节点可能是根也可能不为根。
不为根时，我们还需要一个 ppnode 节点来标记parent的双亲节点，用来将新的’根’节点去链接到原来的树上。

void RotateR(Node* parent) {//右单旋
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		
		parent->_left = subLR;
		if (subLR) {//当subLR存在时，subLR的parent才指向parent
			subLR->_parent = parent;
		}
		if (parent == _root) {//如果p是根,则subL更新为根
			_root = subL;
			subL->_parent = nullptr;
		}
		else {//将旋转后的子树的根节点链接到原来的树上
			if (ppnode->_left == parent) {
				ppnode->_left = subL;
			}
			else {
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
		//...
}

最后一步就是修改平衡因子，旋转后的节点不用再调整，因为旋转后子树的两端高度都相等，达到平衡。

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

	parent->_left = subLR;
	if (subLR) {//当subLR存在时，subLR的parent才指向parent
		subLR->_parent = parent;
	}

	subL->_right = parent;
	Node* ppnode = parent->_parent;//保存p的parent指向
	parent->_parent = subL;

	if (parent == _root) {//如果p是根,则subL更新为根
		_root = subL;
		subL->_parent = nullptr;
	}
	else {//将旋转后的子树的根节点链接到原来的树上
		if (ppnode->_left == parent) {
			ppnode->_left = subL;
		}
		else {
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
	//更新节点的平衡因子
	parent->_bf = 0;
	subL->_bf = 0;
}

现在来看左单旋：

左单旋和右单旋相反，左边高右边低，所以进行左单旋来降低高度差

在这里插入图片描述
这里的情况都和右单旋转相反，我们直接上代码：

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

	parent->_right = subRL;
	if (subRL) {//当subRL存在时，subRL的parent才指向parent
		subRL->_parent = parent;
	}

	subR->_left = parent;
	Node* ppnode = parent->_parent;//保存p的parent指向
	parent->_parent = subR;

	if (parent == _root) {//如果p是根,则subR更新为根
		_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;
}

我们现在来看左右双旋，先左单旋再右单旋

这里的左右双旋其实就是相当右单旋的那种场景下，将b子树拆分成两颗子树，再将新增节点加在拆分后的子树上
在这里插入图片描述
我们以加在左子树为例讲解：
对新增节点后的树进行旋转，先以subL为根进行左旋，

在这里插入图片描述

再对parent为根进行右旋
在这里插入图片描述

加在右子树的过程和这个相反，希望大家可以自己去推导…

知道了大概的过程，我们现在来写代码：
和单旋一样，我们定义变量来协助我们旋转

void RotateRL(Node* parent) {//双旋（先左单旋，再右单旋）
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		//..
}

这里需要注意：新增节点所加的位置有三种情况
（1） 加在拆分后的左子树上
（2） 加在拆分后的右子树上
（3） 上图的60这个位置本身是空的
在这里插入图片描述
那么我们如何区分这三种情况呢，
我们可以用subLR的平衡因子来区分，subLR的因子为-1时，说明左高，则加在了左子树上，为1时，说明右高，则加在了右子树，为0时说明这个位置原来是空的。

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

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

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

右左双旋
右左双旋和左右双旋相反，各位老铁可以参考左右双旋来自己去画出图来理解

在这里插入图片描述

代码：

void RotateRL(Node* parent) {//双旋（先右单旋，再左单旋）
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	int bf = subRL->_bf;//以subRL的因子为标准判断所加的子树的位置
	RotateR(subR);
	RotateL(parent);

	//修改平衡因子
	//增加节点后有三种情况
	subRL->_bf = 0;
	if (bf == -1) {//加在左子树上
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 1) {
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == 0) {
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else {
		assert(false);
	}
}

3. AVL树的验证

AVL的插入讲完了，我们来看看如何证明咋们模拟实现的就是AVL树
一棵树如果是AVL树，那么首先它是一个二叉搜索树，其次他的每个子树的高度差不能超过1

这里我们做了一点小优化，我们在判断时先传入高度，判断高度差时类似于后序遍历的方式，从下往上去计算高度差

代码如下：

bool IsBalance() {
	int height = 0;
	return _IsBalance(_root, height);
}


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;

}

四，总结

我们今天终于讲完了AVL树，我们的C++部分也开始上了难度，希望大家可以跟上我们的讲解，下一节我们要来开始手撕红黑树！！！
在此之前我们要熟悉前面的二叉搜索树和AVL树的内容，希望大家都能学好C++。

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

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

相关文章

C++实验 面向对象编程

C++实验 面向对象编程

一、实验目的&#xff1a; 掌握类中静态成员的定义方法&#xff0c;初始化方法&#xff0c;使用方法&#xff1b; 掌握类的友元说明方法&#xff0c;理解友元的使用特点 二、实验内容&#xff1a; 1、编写程序&#xff0c;统计某旅馆住宿客人的总数&#xff0c;要求输入客人…
阅读更多...
计算机二级（Python）真题讲解每日一题：《绘制雪花》

计算机二级（Python）真题讲解每日一题：《绘制雪花》

在横线处填写代码&#xff0c;完成如下功能‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬…
阅读更多...
Vue.js 应用实现监控可观测性最佳实践

Vue.js 应用实现监控可观测性最佳实践

前言 Vue 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建&#xff0c;并提供了一套声明式的、组件化的编程模型&#xff0c;帮助你高效地开发用户界面。无论是简单还是复杂的界面&#xff0c;Vue 都可以胜任。 TinyPro 是一套使用 Vue …
阅读更多...
SQL Server错误：15404

SQL Server错误：15404

执行维护计划失败&#xff0c;提示SQL Server Error 15404 无法获取有关... 异常如下图&#xff1a; 原因&#xff1a;数据库用户名与计算机名称不一致 解决办法&#xff1a;1.重名称数据库用户名 将前缀改成计算机名 2.重启SQL Server代理
阅读更多...
JAVA基础—JVM内存结构基础需知

JAVA基础—JVM内存结构基础需知

1.JVM内存结构 JVM内存结构分为5个区域&#xff1a;方法区&#xff0c;虚拟机栈&#xff0c;本地方法栈、堆、程序计数器。 1.方法区&#xff08;Method Area&#xff09;&#xff1a;用于存储类的结构信息、常量、静态变量、即使编译器编译后的代码等数据。方法区也是所有线…
阅读更多...
Ansys Lumerical | 激光雷达天线仿真

Ansys Lumerical | 激光雷达天线仿真

附件下载 联系工作人员获取附件 在本文中&#xff0c;我们将了解如何根据激光雷达应用需求设计和优化相控阵光栅天线。 概述 激光雷达&#xff08;LIDAR&#xff09;是“light detection and ranging”的简称&#xff0c;近年来由于在机器人、自动驾驶汽车、高精度测绘等领域…
阅读更多...
自动写作软件哪个好？分享7款独家推荐

自动写作软件哪个好？分享7款独家推荐

随着人工智能技术的不断发展&#xff0c;自动写作软件正逐渐成为现代写作的利器。这些AI写作工具能够帮助用户高效地生成文章、报告、新闻稿等内容&#xff0c;为写作工作带来了极大的便利。然而&#xff0c;市面上的自动写作软件琳琅满目&#xff0c;让人眼花缭乱。为了帮助读…
阅读更多...
Java多线程学习（一）

Java多线程学习（一）

1、什么是多线程 进程的执行需要依赖线程。线程是进程的最小执行单位&#xff0c;每一个进程中最少有一个线程。 例如&#xff1a;使用某网盘下载时&#xff0c;当我们同时进行下载和上传操作时&#xff08;同一时间同时进行&#xff09;&#xff0c;就使用到了多线程&#x…
阅读更多...
德国法兰克福交易所股票清单列表数据API接口

德国法兰克福交易所股票清单列表数据API接口

# Restful API https://tsanghi.com/api/fin/stock/XFRA/list?token{token}更新时间&#xff1a;收盘后3~4小时。 更新周期&#xff1a;每天。 请求方式&#xff1a;GET。 # 测试&#xff1a;返回不超过10条数据&#xff08;2年历史&#xff09; https://tsanghi.com/api/fin/…
阅读更多...
【Java,Redis】Redis 数据库存取字符串数据以及类数据

【Java,Redis】Redis 数据库存取字符串数据以及类数据

1、 字符串存取数据 Resource private StringRedisTemplate stringRedisTemplate;//从Redis中获取string字符串 stringRedisTemplate.opsForValue().get("cache:shop:"id); //Json -> class Shop shop JSONUtil.toBean(ShopJson,Shop.class); //字符串写入redis…
阅读更多...
基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的自动驾驶目标检测系统详解（深度学习+Python代码+PySide6界面+训练数据集）

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的自动驾驶目标检测系统详解（深度学习+Python代码+PySide6界面+训练数据集）

摘要&#xff1a;开发自动驾驶目标检测系统对于提高车辆的安全性和智能化水平具有至关重要的作用。本篇博客详细介绍了如何运用深度学习构建一个自动驾驶目标检测系统&#xff0c;并提供了完整的实现代码。该系统基于强大的YOLOv8算法&#xff0c;并对比了YOLOv7、YOLOv6、YOLO…
阅读更多...
什么是VR应急预案演练虚拟化|VR体验馆加盟|元宇宙文旅

什么是VR应急预案演练虚拟化|VR体验馆加盟|元宇宙文旅

VR 应急预案演练虚拟化指的是利用虚拟现实&#xff08;Virtual Reality&#xff0c;VR&#xff09;技术进行应急预案演练的过程。在传统的应急预案演练中&#xff0c;人们通常需要在实际场地或模拟环境中进行演练&#xff0c;这可能存在一些限制&#xff0c;如成本高昂、场地受…
阅读更多...
解析KafkaConsumer类的神奇之道

解析KafkaConsumer类的神奇之道

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 解析KafkaConsumer类的神奇之道 前言KafkaConsumer双线程设计主线程&#xff08;消费线程&#xff09;&#xff1a;心跳线程&#xff1a;示例代码&#xff1a; KafkaConsumer线程不安全线程安全的替代…
阅读更多...
PHP爬虫技术：利用simple_html_dom库分析汽车之家电动车参数

PHP爬虫技术：利用simple_html_dom库分析汽车之家电动车参数

摘要/导言 本文旨在介绍如何利用PHP中的simple_html_dom库结合爬虫代理IP技术来高效采集和分析汽车之家网站的电动车参数。通过实际示例和详细说明&#xff0c;读者将了解如何实现数据分析和爬虫技术的结合应用&#xff0c;从而更好地理解和应用相关技术。 背景/引言 随着电…
阅读更多...
非空约束

非空约束

oracle从入门到总裁:​​​​​​https://blog.csdn.net/weixin_67859959/article/details/135209645 非空约束 所谓的非空约束&#xff0c;指的是表中的某一个字段的内容不允许为空。如果要使用非空约束&#xff0c;只需要在每个列的后面利用“NOT NULL”声明即可 -- 删除数…
阅读更多...
Java习题中 哈希表的理论 有效的字母异位词 快乐数 两数之和

Java习题中 哈希表的理论 有效的字母异位词 快乐数 两数之和

关于 哈希表的理论 今天最大的疑惑好像就是map的复杂度怎么算哈哈,一般n个元素map的复杂度就是On哦,不需要想得太复杂了,冲突的空间并不会造成一个量级,改变n前面的常数不会影响空间复杂度哈提醒&#xff01;熟悉好map,set的API哦 关于 有效的字母异位词 为什么遍历第二个字符…
阅读更多...
Linux异步通知实验：应用程序对异步通知的处理

Linux异步通知实验：应用程序对异步通知的处理

一. 简介 前面文章学习了 应用程序对异步通知的处理方法&#xff0c;另一篇文章实现了Linux驱动对异步通知的处理&#xff1a; Linux应用程序对异步通知的处理-CSDN博客 Linux异步通知实验&#xff1a;驱动中异步通知的处理-CSDN博客 本文继续Linux异步通知实验&#xff0c…
阅读更多...
想进阿里？先搞懂Spring Bean作用域！

想进阿里？先搞懂Spring Bean作用域！

大家好，我是小米！今天我来和大家分享一下 Java 开发中一项非常重要的技术——参数校验。参数校验在我们的代码中起着至关重要的作用，它能够确保我们的应用程序接收到正确的数据，并且保证了系统的安全性和稳定性。在过去，我们可能会通过繁琐的 if-else 来进行参数校验，但是…
阅读更多...
AI视频矩阵混剪系统|罐头鱼AI批量混剪定时发送

AI视频矩阵混剪系统|罐头鱼AI批量混剪定时发送

AI视频矩阵混剪系统&#xff1a;智能创作与发布的完美结合 随着社交媒体平台的快速发展&#xff0c;视频已成为各行业推广和传播的热门方式。然而&#xff0c;对于许多人来说&#xff0c;制作高质量的视频仍然是一项挑战。Q:290615413但现在&#xff0c;有了AI视频矩阵混剪系统…
阅读更多...
lftp服务与http服务(包含scp服务)详解

lftp服务与http服务(包含scp服务)详解

目录 前言: 1.lftp服务 1.1lftp服务的介绍以及应用场景 1.2安装lftp服务 1.2进行配置 1.3实际操作 2.http服务 2.1http服务介绍以及应用场景 2.1安装httpd服务 2.2进行配置 2.3实际操作 3.scp服务 3.1scp服务的介绍以及应用场景 致谢: 前言: 在当今互联网…
阅读更多...
最新文章

Copyright @ 2022~2023