AVL树 -- C++实现

AVL树 – C++实现

1. AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。这个树就是用它们两个的名字AVL命名的。

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

  • 它的左右子树都是AVL树

  • 左右子树高度之差(简称平衡因子)的绝对值不超过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)。 **

2. AVL树节点的定义

AVL树节点的定义：

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	pair<K, V> _kv;
	//平衡因子 balance factor
	int _bf;

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

3. AVL树的插入

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

  1. 按照二叉搜索树的方式插入新节点
  2. **调整节点的平衡因子 **
bool insert(const pair<K,V>& kv)
	{
	// 1. 先按照二叉搜索树的规则将节点插入到AVL树中
	// ...
	// 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树的平衡性
	
	/*
	cur插入后，parent的平衡因子一定需要调整，在插入之前，parent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
	1. 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可
	2. 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可
	此时：parent的平衡因子可能有三种情况：0，正负1， 正负2
	1. 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功
	2. 如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新
	3. 如果parent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理
	*/
		if (_root == nullptr)
		{
			Node* newnode = new Node(kv);
			_root = newnode;
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		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);//新节点
		cur->_parent = parent;
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
	
		while (parent)
		{
			//修改平衡因子
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			//判断平衡因子
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == -1 || parent->_bf == 1)//之前是0,高度发生变化
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if(parent->_bf == -2 || parent->_bf == 2)//之前是-1 或者 1
			{
				//旋转
				//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)
				{
					RotateRL(parent);//右左双旋
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);//左右双旋
				}
				//1.旋转让这棵子树平衡了
				//2.旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
		
	}

4. AVL树的旋转

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

  1. 新节点插入较高右子树的右侧—右右：左单旋
    在这里插入图片描述

代码示例：

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

		parent->_right = subL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		
		parent->_parent = subR;
		if (subL)
		{
			subL->_parent = parent;
		}

		if (_root == parent)//根节点
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
		//改平衡因子
		parent->_bf = subR->_bf = 0;
	}
  1. 新节点插入较高左子树的左侧—左左：右单旋

在这里插入图片描述

代码示例：

void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentParent = parent->_parent;//根节点可能是空
		
		parent->_left = subLR;
		subL->_right = parent;

		parent->_parent = subL;
		if(subLR)
		subLR->_parent = parent;

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

		//改平衡因子
		subL->_bf = parent->_bf = 0;
	}
  1. 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

在这里插入图片描述

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

代码示例：

void RotateLR(Node* parent)//左右双旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		int bf = subLR->_bf;//保存一下平衡因子
		
		//先对30进行左单旋，然后再对90进行右单旋
		RotateL(subL);
		RotateR(parent);

		if (bf == 0)//插入的是60本身
		{
			parent->_bf = subL->_bf = subLR->_bf = 0;
		}
		else if (bf == 1)//在60右子树插入
		{
			parent->_bf = subLR->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)//在60左子树插入
		{
			subL->_bf = subLR->_bf = 0;
			parent->_bf = 1;
		}
		else
		{
			assert(false);
		}
	}
  1. 新节点插入较高右子树的左侧—右左：先右单旋再左单旋

在这里插入图片描述

代码示例：

	void RotateRL(Node* parent)//右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		int bf = subRL->_bf;
		RotateR(subR);
		RotateL(parent);

		if (bf == 0)
		{
			//subRL 自己新增
			parent->_bf = subRL->_bf = subR->_bf = 0;
		}
		else if (bf == -1)
		{
			//subRL的左子树新增
			parent->_bf = subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			//subRL的右子树新增
			subRL->_bf = subRL->_bf = 0;
			parent->_bf = -1;
		}
		else
		{
			assert(false);
		}
	}

总结：

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

  1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
  • 当pSubR的平衡因子为1时，执行左单旋
  • 当pSubR的平衡因子为-1时，执行右左双旋
  1. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
  • 当pSubL的平衡因子为-1是，执行右单旋
  • 当pSubL的平衡因子为1时，执行左右双旋

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

5. AVL树的验证

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

  1. 验证其为二叉搜索树
    • 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
  2. 验证其为平衡树
    • 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
    • 节点的平衡因子是否计算正确

代码示例：

	int Height()//树的高度
	{
		return _Height(_root);
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	
	bool IsBlance()
	{
		return _IsBlance(_root);
	}

	bool _IsBlance(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;
		}

		//if (rightHeight - leftHeight <= 1 && rightHeight - leftHeight >= -1)
		return (abs(rightHeight - leftHeight) <= 1)//求绝对值
			&&_IsBlance(root->_right)
			&& _IsBlance(root->_left);
		
	}

6. AVL树的删除(了解)

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

7. AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 l o g 2 ( N ) log_2 (N) log2​(N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。 下篇文章我们来讲解红黑树！

本篇结束！

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

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

相关文章

组件v-model（.sync）记录使用（vue3）

组件v-model（.sync）记录使用（vue3）

示例&#xff08;演示地址&#xff09; 以下是Vue3中使用v-model实现组件的双向数据绑定的示例代码&#xff1a; 首先&#xff0c;让我们来了解一下Vue3中v-model的用法。在Vue3中&#xff0c;v-model 指令可以用于自定义组件上&#xff0c;用于实现组件的双向数据绑定。与Vue2…
阅读更多...
为什么选择HelpLook而不是Document360：知识库工具分析

为什么选择HelpLook而不是Document360：知识库工具分析

在现今的信息化时代&#xff0c;企业们越来越倾向于使用知识库工具来收集、组织和分享他们的知识资源。HelpLook和Document360是市面上两款不错的知识库管理工具。那如果非要在他们之中选一个&#xff0c;还是建议HelpLook。以下是一些对比分析&#xff0c;希望可以给大家提供参…
阅读更多...
Python通过HTTP代理进行数据传输

Python通过HTTP代理进行数据传输

在Python中&#xff0c;HTTP代理是一种常用的技术&#xff0c;用于控制和修改HTTP请求和响应。通过使用HTTP代理&#xff0c;我们可以更好地控制网络请求的行为&#xff0c;提高安全性、隐私性和效率。下面我们将详细介绍如何在Python中使用HTTP代理进行数据传输。 一、设置HT…
阅读更多...
tinyxml2

tinyxml2

使用tinyxml2&#xff0c;得知道一些xml基础 xml tutorial--菜鸟 tinyxml2类对象 链接 结构 XMLNode 什么是节点 节点&#xff1a;元素、声明、文本、注释等。 XMLDocument xml文档(文件)对象。 作用&#xff1a; 加载xml文件&#xff0c; tinyxml2作用 先定义两个宏 …
阅读更多...
Elasticsearch各种高级文档操作

Elasticsearch各种高级文档操作

本文来记录下Elasticsearch各种文档操作 文章目录 初始化文档数据查询所有文档匹配查询文档关键字精确查询文档多关键字精确查询文档字段匹配查询文档指定查询字段查询文档过滤字段查询文档概述指定想要显示的字段示例指定不想要显示的字段示例 组合查询文档范围查询文档概述使…
阅读更多...
Redis+lua 解决秒杀超卖问题

Redis+lua 解决秒杀超卖问题

商品超卖的原因是在高并发场景下,业务层面扣库存和库存的判断会出现并发情况&#xff0c;但是使用lua 脚本&#xff0c;就会避免超卖的发生。 1.在项目resources文件夹创建一个名为 stock.lua的脚本 if (redis.call(hexists, KEYS[1], KEYS[2]) 1) thenlocal stock tonumber…
阅读更多...
HarmonyOS—构建第一个ArkTS应用（Stage模型）

HarmonyOS—构建第一个ArkTS应用（Stage模型）

创建ArkTS工程 构建第一个页面 若首次打开DevEco Studio&#xff0c;请点击Create Project创建工程。如果已经打开了一个工程&#xff0c;请在菜单栏选择File > New > Create Project来创建一个新工程。选择Application应用开发&#xff0c;选择模板“Empty Ability”&am…
阅读更多...
Intel Quartus II IP之DP1.4 工程的创建与使用

Intel Quartus II IP之DP1.4 工程的创建与使用

前述&#xff1a; Win10电脑安装了Quartus 21.4&#xff0c;这可以满足绝大多数工程&#xff0c;特别是对于简单调用fifo/ram等的工程&#xff0c;但是想要学习Quartus的HDMI/DP等高速接口类IP&#xff0c;首先需要创建HDMI/DP IP的设计demo工程&#xff0c;此时还需要安装Ecl…
阅读更多...
android studio从空白开始

android studio从空白开始

对我来说&#xff0c;真正的第一步是清理电脑C盘。从剩余8G清理到25G&#xff0c;把原来看不顺眼又不敢删的文件夹和软件全删了&#xff0c;删爽了的后果就是&#xff0c;用两天的时间在把一些环境配置慢慢装回来&#xff0c;node.js&#xff0c;jdk&#xff0c;npm。努力把它们…
阅读更多...
SG3225HBN(晶体振荡器)

SG3225HBN(晶体振荡器)

SG3225HBN晶体振荡器是一款低抖动、HCSL输出晶振&#xff0c;频率范围100MHz ~ 325MHz&#xff0c;3.2 2.5 1.05mm封装常规有源晶振&#xff0c;具有小尺寸&#xff0c;高稳定性&#xff0c;可以在G&#xff1a;-40℃至 85℃&#xff0c;H&#xff1a;-40℃至 105℃ 的温度内…
阅读更多...
网页版短信平台主要功能有哪些|短信系统开发搭建源码

网页版短信平台主要功能有哪些|短信系统开发搭建源码

网页版短信平台主要功能有哪些|短信系统开发搭建源码 网页版短信平台是一种方便用户进行在线短信管理和发送的工具。它具有多项实用的功能&#xff0c;使用户能够更高效地进行短信通讯。以下是网页版短信平台的主要功能&#xff1a; 1. **短信发送和接收&#xff1a;** 用户可…
阅读更多...
linux第一个小程序 --- 进度条【简洁】

linux第一个小程序 --- 进度条【简洁】

行缓冲区的概念 结果&#xff1a;先输入hello world然后休眠三秒后结束 当去掉’\n“ 后&#xff0c;结果就变成了先休眠三秒&#xff0c;然后打印hello world后结束。 该现象就证明了缓冲区的存在。 当缓冲区中遇到’‘\n’或者缓冲区被写满后才会被打印出来&#xff0c;在第…
阅读更多...
vue2项目导入高德地图

vue2项目导入高德地图

1、看官网新手入门链接导入原生高德地图&#xff1a; 展示地图-入门教程-地图 JS API 2.0 | 高德地图API 2、uniapp开发h5&#xff0c;使用map组件&#xff0c;使用高德地图&#xff1a; 在配置文件中配置地图为高德&#xff0c;&#xff08;默认使用的是腾讯&#xff09;&am…
阅读更多...
港科夜闻｜香港科大团队研发多功能,可重构和抗破坏单线感测器阵列

港科夜闻｜香港科大团队研发多功能,可重构和抗破坏单线感测器阵列

关注并星标 每周阅读港科夜闻 建立新视野 开启新思维 1、香港科大团队研发多功能、可重构和抗破坏单线感测器阵列。研究人员开发出一种受人类听觉系统启发的感测器阵列设计技术。透过模仿人耳根据音位分布来区分声音的能力&#xff0c;这种新型感测器阵列方法可能优化感测器阵列…
阅读更多...
SpringBoot-基础篇

SpringBoot-基础篇

学了好久springBoot但是每一次使用都没有一个固定的方法或者是代码的模版&#xff0c;于是乎使用的时候吗&#xff0c;每次都会遇到很多的问题&#xff0c;所以&#xff0c;总结一篇博客用于日后方便自己开发使用&#xff0c;其中包含项目创建&#xff0c;坐标导入&#xff0c;…
阅读更多...
一篇综述洞悉医学大型语言模型的原理，应用和挑战

一篇综述洞悉医学大型语言模型的原理，应用和挑战

在过去的一年中&#xff0c;随着 GPT-4、LLaMA、Mistral&#xff0c;PaLM 等先进技术的突飞猛进&#xff0c;大型语言模型&#xff08;Large Language Models&#xff09;已经引领全球人工智能进入了一个全新的基础模型时代&#xff0c;这一时代不仅开启了技术创新的新篇章&…
阅读更多...
[足式机器人]Part2 Dr. CAN学习笔记- Kalman Filter卡尔曼滤波器Ch05-5+6

[足式机器人]Part2 Dr. CAN学习笔记- Kalman Filter卡尔曼滤波器Ch05-5+6

本文仅供学习使用 本文参考&#xff1a; B站&#xff1a;DR_CAN Dr. CAN学习笔记 - Kalman Filter卡尔曼滤波器 Ch05-56 5. An Example 2D例子6. Extended Kalman Filter扩展卡尔曼滤波器&#xff08;EKF&#xff09; 5. An Example 2D例子 6. Extended Kalman Filter扩展卡尔曼…
阅读更多...
postman测试文件上传接口设置说明

postman测试文件上传接口设置说明

Postman介绍及下载链接地址 Download Postman | Get Started for Free 打开postman 选择POST方法&#xff0c;然后设置goform 设置Header参数 设置Body参数&#xff0c;选择数据form-data 添加文件&#xff0c; 选择为文件属性 添加需要上传的文件
阅读更多...
Electron Apple SignIn 登录

Electron Apple SignIn 登录

本人写博客&#xff0c;向来主张&#xff1a;代码要完整&#xff0c;代码可运行&#xff0c;文中不留下任何疑惑。 最讨厌写博客&#xff0c;代码只留下片段&#xff0c;文中关键的东西没写清楚。之前看了那么多文章&#xff0c;就是不告诉我clientId从哪来的。 官方资料地址&…
阅读更多...
c++学习笔记-STL案例-机房预约系统4-管理员模块

c++学习笔记-STL案例-机房预约系统4-管理员模块

前言 衔接上一篇“c学习笔记-STL案例-机房预约系统3-登录模块”&#xff0c;本文主要设计管理员模块&#xff0c;从管理员登录和注销、添加账号、显示账号、查看机房、清空预约五个功能进行分析和实现。 目录 7 管理员模块 7.1 管理员登录和注销 7.1.1 构造函数 ​编辑7.1.2…
阅读更多...
最新文章

Copyright @ 2022~2023