【数据结构】AVL树(C++实现)
文章目录
- 前言
- AVL树节点的定义
- AVL树的插入
- AVL树的旋转
- AVL树的验证
- AVL树的删除
- AVL树的性能与源码
前言
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson - Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n),搜索时间复杂度O( l o g 2 n log_2 n log2n)。
AVL树节点的定义
template<class T>struct TreeNode{public:TreeNode(T data):_data(data), _bf(0), _parent(nullptr), _left(nullptr), _right(nullptr){}public:T _data;// Defining balance factorint _bf; // 该节点的平衡因子// 定义成一个三叉链结构,方便后续操作TreeNode* _parent; // 该节点的双亲TreeNode* _left; // 该节点的左孩子TreeNode* _right; // 该节点的右孩子};
AVL树的插入
因为插入逻辑比较复杂,我在这里就写一个大致思路,具体代码我上传到了git上。
AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步:
- 按照二叉搜索树的方式插入新节点
- 调整节点的平衡因子
此处我写一个大致的代码逻辑,并结合图片给大家看一下:
bool Insert(const T& data)
{// 1. 先按照二叉搜索树的规则将节点插入到AVL树中// ...// 2. 新节点插入后,AVL树的平衡性可能会遭到破坏,此时就需要更新平衡因子,// 并检测是否破坏了AVL树的平衡性/*cur插入后,parent的平衡因子一定需要调整,在插入之前,parent的平衡因子分为三种情况:-1,0, 1, 插入时出现以下两种情况:1. 如果cur插入到parent的左侧,只需给parent的平衡因子-1即可2. 如果cur插入到pParent的右侧,只需给parent的平衡因子+1即可此时:parent的平衡因子可能有三种情况:0,正负1, 正负21. 如果parent的平衡因子为0,说明插入之前pParent的平衡因子为正负1,插入后被调整成0,此时满足AVL树的性质,插入成功2. 如果parent的平衡因子为正负1,说明插入前parent的平衡因子一定为0,插入后被更新成正负1,此时以pParent为根的树的高度增加,需要继续向上更新3. 如果parent的平衡因子为正负2,则parent的平衡因子违反平衡树的性质,需要对其进行旋转处理*/while (parent){// 更新双亲的平衡因子if (cur == parent->_pLeft)parent->_bf--;elseparent->_bf++;// 更新后检测双亲的平衡因子if (0 == parent->_bf){break;}else if (1 == pParent->_bf || -1 == pParent->_bf){// 插入前双亲的平衡因子是0,插入后双亲的平衡因为为1 或者 -1 ,说明以双亲为根的二叉树// 的高度增加了一层,因此需要继续向上调整cur = pParent;pParent = pCur->_pParent;}else{// 双亲的平衡因子为正负2,违反了AVL树的平衡性,需要对以parent// 为根的树进行旋转处理if (2 == pParent->_bf){// ...}else{// ...}}}return true;
}
插入节点会影响新增节点的部分祖先,
更新规则:
- c是p的左边,
p->_bf--
- c是p的右边,
p->_bf++
是否要继续更新取决于p的高度是否变化,是否会影响爷爷节点。
在上面这张图的基础上,插入11:
我们可以看到:
- 更新后,
p->_bf == 0
,p所在的高度不会改变,不会影响爷爷节点。说明更新前,p->_bf
是1或者-1,p的矮的那一边插入了新节点,左右高度均衡了,p的高度不变,不会影响爷爷,更新结束。 - 更新后,
p->_bf == 1 / -1
,p所在的子树高度变了,会影响爷爷。说明更新前,p->_bf
是0,p的有一边插入,p变得不均衡,但不违反规则,p的高度变了,会影响爷爷,继续往上更新
在上面这张图的基础上,再插入1:
- 更新后,
p->_bf == 2 / -2
,说明p所在的子树违反了平衡规则,需要进行旋转处理。
AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡化。根据节点插入位置的不同,AVL树的旋转分为四种:
1. 新节点插入较高左子树的左侧—左左:右单旋
/*上图在插入前,AVL树是平衡的,新节点插入到30的左子树(注意:此处不是左孩子)中,30左子树增加了一层,导致以60为根的二叉树不平衡,要让60平衡,只能将60左子树的高度减少一层,右子树增加一层,即将左子树往上提,这样60转下来,因为60比30大,只能将其放在30的右子树,而如果30有右子树,右子树根的值一定大于30,小于60,只能将其放在60的左子树,旋转完成后,更新节点的平衡因子即可。在旋转过程中,有以下几种情况需要考虑:1. 30节点的右孩子可能存在,也可能不存在2. 60可能是根节点,也可能是子树如果是根节点,旋转完成后,要更新根节点如果是子树,可能是某个节点的左子树,也可能是右子树大家在此处可举一些详细的例子进行画图,考虑各种情况,加深旋转的理解
*/
void RotateR(Node* parents)
{// SubL: parents的左孩子// SubLR: parents左孩子的右孩子,注意:该节点可能为空Node* SubL = parents->_left;Node* SubLR = SubL->_right;// 旋转完成之后,30的右孩子作为双亲的左孩子parents->_left = SubLR;// 如果30的左孩子的右孩子存在,更新该节点的双亲if (SubLR != nullptr)SubLR->_parent = parents;// 60 作为 30的右孩子SubL->_right = parents;// 因为60可能是棵子树,因此在更新其双亲前必须先保存60的双亲Node* ppnode = parents->_parent;// 更新60的双亲 parents->_parent = SubL;// 更新30的双亲SubL->_parent = ppnode;// 如果60是根节点,更新指向根节点的指针if (_root == parents){_root = SubL;SubL->_parent = nullptr;}else{ // 如果60是子树,可能是其双亲的左子树,也可能是右子树if (parents == ppnode->_left)ppnode->_left = SubL;elseppnode->_right = SubL;}// Renewal balance factorparents->_bf = 0;SubL->_bf = 0;
}
2. 新节点插入较高右子树的右侧—右右:左单旋
实现及情况考虑可参考右单旋:
void RotateL(Node* parents)
{Node* SubR = parents->_right;Node* SubRL = SubR->_left;parents->_right = SubRL;if (SubRL != nullptr)SubRL->_parent = parents;SubR->_left = parents;Node* ppnode = parents->_parent;parents->_parent = SubR;SubR->_parent = ppnode;if (_root == parents){_root = SubR;SubR->_parent = nullptr;}else{if (parents == ppnode->_left)ppnode->_left = SubR;elseppnode->_right = SubR;}// Renewal balance factorparents->_bf = 0;SubR->_bf = 0;
}
3. 新节点插入较高左子树的右侧—左右:先左单选再右单旋
将双旋变成单旋后再旋转,即:先对30进行左单旋,然后再对90进行右单旋,旋转完成后再考虑平衡因子的更新。
旋转之前先看60的平衡因子是多少,旋转结束以后,根据60的平衡因子更新结果。
这里平衡因子的更新有三种情况:
-
旋转之前,60的平衡因子为-1
-
旋转之前,60的平衡因子为1
-
旋转之前,60的平衡因子为0
从这三张图中,可以发现,不管旋转之前60的平衡因子是多少,最后都会变成0(在单旋中,已经将它置0),所以我们只用观察30,90 的平衡因子。而不管这棵树怎么变,它必定会遵守搜索二叉树的规则,所以在这里我只是用了一个示例向大家展示这三种情况。不管这棵树的形状是什么样的,只要它满足搜索二叉树的规则,那么左右双旋只会有这几种情况。
// 旋转之前,60的平衡因子可能是-1/0/1,旋转完成之后,根据情况对其他节点的平衡因子进行调整
void RotateLR(Node* parents)
{Node* SubL = parents->_left;Node* SubLR = SubL->_right;// 旋转之前,保存pSubLR的平衡因子,旋转完成之后,需要根据该平衡因子来调整其他节点的平衡因子int bf = SubLR->_bf;// 先对30进行左单旋RotateL(SubL);// 再对90进行右单旋RotateR(parents);// Renewal balance factorif (bf == 0){parents->_bf = 0;SubL->_bf = 0;}else if (bf == 1){parents->_bf = 0;SubL->_bf = -1;}else if (bf == -1){parents->_bf = 1;SubL->_bf = 0;}
}
4. 新节点插入较高右子树的左侧—右左:先右单旋再左单旋
这里与左右双旋相似,将双旋变成单旋后再旋转,即:先对90进行右单旋,然后再对30进行左单旋,旋转完成后再考虑平衡因子的更新。
旋转之前先看60的平衡因子是多少,旋转结束以后,根据60的平衡因子更新结果。
这里平衡因子的更新有三种情况:
-
旋转之前,60的平衡因子为1
-
旋转之前,60的平衡因子为-1
-
旋转之前,60的平衡因子为0
void RotateRL(Node* parents)
{Node* SubR = parents->_right;Node* SubRL = SubR->_left;int bf = SubRL->_bf;RotateR(SubR);RotateL(parents);// Renewal balance factorif (bf == 0){parents->_bf = 0;SubR->_bf = 0;}else if (bf == 1){parents->_bf = -1;SubR->_bf = 0;}else if (bf == -1){parents->_bf = 0;SubR->_bf = 1;}
}
总结
假如以parent为根的子树不平衡,即parent的平衡因子为2或者-2,分以下情况考虑
- parent的平衡因子为2,说明parent的右子树高,设parent的右子树的根为SubR
当SubR的平衡因子为1时,执行左单旋
当SubR的平衡因子为-1时,执行右左双旋 - parent的平衡因子为-2,说明parent的左子树高,设parent的左子树的根为SubL
当SubL的平衡因子为-1时,执行右单旋
当SubL的平衡因子为1时,执行左右双旋
旋转完成后,原parent为根的子树个高度降低,已经平衡,不需要再向上更新。
AVL树的旋转只有以上情况,不可能会出现其他情况了。
AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:
- 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列,就说明为二叉搜索树 - 验证其为平衡树
- 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
- 节点的平衡因子是否计算正确
bool Isbalance()
{int Hight = 0;return _Isbalance(_root, Hight);
}
// 为了提高效率,可以走后序来计算每个节点的左子树和右子树的高度差为多少
// 通过Hight来保存每个节点的最高的子树的高度为多少
bool _Isbalance(Node* root, int& Hight)
{if (root == nullptr)return true;int leftHight = 0;int rightHight = 0;if (!_Isbalance(root->_left, leftHight) || !_Isbalance(root->_right, rightHight)){// 如果root的左子树或者右子树不平衡,就直接返回falsereturn false;}// 判断每个节点的左右子树高度差的绝对值不超过1if (abs(rightHight - leftHight) >= 2){std::cout << "balance factor error, the tree is unbalanced\n";return false;}// 判断每个节点的右子树的最大高度与左子树的最大高度的差值是否等于该节点的平衡因子else if (rightHight - leftHight != root->_bf){std::cout << root->_data << " the balance factor is wrong\n";return false;}// 保存左子树和右子树较高的高度Hight = leftHight > rightHight ? leftHight + 1 : rightHight + 1;return true;
}
这段代码是随机生成10000个数,插入到我自己写的一棵AVL树中,插完这10000个树以后,我对这棵树进行了一下判断是否平衡,结果是平衡的,证明我的插入逻辑是没有问题的(我测试了不止这一组数据)。
AVL树的删除
因为插入删除比较复杂,我在这里就写一个大致思路,具体代码我上传到了git上。
因为AVL树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不
过与插入不同的是,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。
这里更新平衡因子的逻辑与插入更新平衡因子的逻辑恰恰是相反的。
删除节点会影响删除节点的部分祖先(如果是删除根节点,也会找一个可以替代的节点交换值再删除,具体可以参考搜索二叉树的删除部分)。
更新原则:
- c是p的左边,
p->_bf++
- c是p的右边,
p->_bf--
是否要继续更新取决于p的高度是否变化,是否会影响爷爷节点。
在上面这张图的基础上,删除7:
在上面这张图的基础上,再删除3:
在上面这张图的基础上,再删除14:
从上面三个动图可以分析出:
- 更新后
p->_bf == 1 / -1
,p所在的子树高度不变,不会影响爷爷。说明更新前,p->_bf
是0,p的两边是均衡的,p的有一边删除了,p变得不均衡,但不违反规则,p的高度不变,不会影响爷爷,更新结束。 - 更新后,
p->_bf == 0
,p所在的子树的高度变了,会影响爷爷。说明更新前,p->_bf == 1 / -1
,p的有一边删除了,p的左右变得均衡,p的高度变了,会影响爷爷,继续往上更新。 - 更新后,
p->_bf == 2 / -2
,说明p所在的子树违反了平衡规则,需要进行旋转处理。
AVL树的性能与源码
AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即 l o g 2 ( N ) log_2(N) log2(N)。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。
源码地址:https://gitee.com/ASL498/data-structure/tree/master/AVLTree
相关文章:

【数据结构】AVL树(C++实现)
文章目录 前言AVL树节点的定义AVL树的插入AVL树的旋转AVL树的验证AVL树的删除AVL树的性能与源码 前言 二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此&…...

AMD新推EPYC与MI325X,挑战英伟达AI市场地位
在人工智能(AI)加速器领域,AMD近日于美国旧金山举办的“推进人工智能”(Advancing AI Event)活动中,宣布了一系列新产品的发布,直接对标英伟达,意图在AI芯片市场占据更大份额。 AMD新…...

电脑桌面文件不见了怎么恢复?8个方法帮你解决问题
电脑桌面文件突然不见了凭空消失了怎么恢复?电脑桌面文件日常使用电脑时,很多用户喜欢将重要文件、快捷方式存放在桌面上,以方便快速访问。然而,有时我们会突然发现桌面上的文件不见了。桌面文件消失可能有多种原因,例…...

如果想转行AI领域却不知如何开始?可以试试这五步,超详细_ai行业怎么入行
我看了计算机科学家大卫格维茨写的一篇博客,里面介绍了如果想从事AI行业,却不知道如何开始的话,可以走下面五步,从而达到转行的目的。因为这是个国外作家写的,跟我们国内的情况有一些出入,但是大思路是没有…...

个人博客搭建 | Hexo框架
文章目录 1.Hexo安装2.创建博客3.将博客通过GitHub来部署4.更换主题 1.Hexo安装 Hexo 是一个快速、简洁且高效的博客框架。Hexo 使用 Markdown(或其他标记语言)解析文章,在几秒内,即可利用靓丽的主题生成静态网页。搭建Hexo首先要…...
[Gtk] layout.ui
播放器layout: # <?xml version"1.0" encoding"UTF-8"?> <!-- Generated with glade 3.38.2 --> <interface> <requires lib"gtk" version"3.20"/> <object class"GtkWindow"…...

Spring MVC:精通JSON数据返回的几种高效方式
前言 在实际开发中,我们在前后端传送数据通常使用Json格式,而在Spring MVC中返回Json格式的方式有多种,接下来我将介绍其中一些。 准备工作 为了演示Json格式的数据,我们准备一个实体类,例如User,这些可以测…...
[LeetCode 题3] 没有重复字符的最长的子字符串
问题描述 输入:一个字符串 s。输出:最长的无重复字符的子串的长度。 示例 输入: s "abcabcbb" 输出: 3 解释: 最长的无重复字符的子串是 "abc",长度为 3。 输入: s "bbbbb" 输出: 1 解释: 最长的无重复字…...
YoloDotNet 在工业检测中的应用详解
文章目录 一、数据收集与标注二、模型选择与训练三、检测流程设计四、结果评估与优化五、与工业生产线集成一、数据收集与标注 在工业检测中,首先需要收集大量的相关工业产品图像数据。这些数据应涵盖不同的产品类型、缺陷种类以及各种可能的生产状态。例如,对于电子产品的检…...

DataFrame增删改数据
目录 准备数据 DataFrame添加列 直接添加列数据 使用insert添加列数据 DataFrame删除行列 准备数据 删除行 删除列 DataFrame数据去重 准备数据 import pandas as pd df pd.read_csv("../data/b_LJdata.csv") df DataFrame添加列 直接添加列数据 1&…...

一站式解决App下载量统计,Xinstall引领新潮流
在移动应用市场中,App下载量是衡量应用受欢迎程度和市场表现的重要指标。然而,对于许多开发者而言,如何精准统计App下载量却是一个不小的挑战。幸运的是,如今有了一款专业的App全渠道统计服务商——Xinstall,它能够帮助…...
ijkMediaPlayer+ TextureView 等比全屏播放视频(避免拉伸)
TextureView默认以fitxy的方式加载surface数据,如果需要等比全屏播放视频,避免拉伸,可以采用Matrix对TextureView进行变换 废话不多说,直接上代码 public class BaseIjkPlayer implements TextureView.SurfaceTextureListener{/…...
【RS】GEE(Python):数据处理
在前面的章节中,我们已经学习了如何加载影像数据。现在,让我们进一步探讨如何在 Google Earth Engine (GEE) 中进行数据处理。数据处理通常包括图像预处理、裁剪、过滤、重采样等操作。 栅格影像的处理 栅格影像处理包括了裁剪、波段选择、重采样、合成…...

非线性磁链观测器推导
<div id"content_views" class"htmledit_views"><p id"main-toc"><strong>目录</strong></p> 电机方程 电压方程 磁链方程 定义状态变量和输出变量 非线性观测器方程 电角度的计算--锁相环 锁相环调参 电机…...
什么时机用mysql,什么时机用redis,什么时机用本地内存
mysql 的 buffer pool 也是存在内存中,redis 的数据也是存在内存中,为什么不直接存在 mysql 里? 1、数据结构和访问方式 Redis 是一个内存数据库,专门为高效的读写性能而设计。它支持多种数据结构(如字符串、列表、哈…...

Redis八股
缓存 缓存穿透 当查询一个不存在的数据,mysql查询不到数据,无法写入缓存,导致每次都请求数据库 解决方法 缓存空数据,当查询结果未空,将结果进行缓存。 简单但是会消耗内存,而且会出现不一致情况。布隆…...

vue3--通用 popover 气泡卡片组件实现
背景 在日常开发中,我们一般都是利用一些诸如:element-ui、element-plus、ant-design等组件库去做我们的页面或者系统 这些对于一些后台管理系统来说是最好的选择,因为后台管理系统其实都是大同小异的,包括功能、布局结构等 但是对于前台项目,比如官网、门户网站这些 …...

Bluetooth Channel Sounding中关于CS Step及Phase Based Ranging相应Mode介绍
目录 BLE CS中Step定义 BLE CS中交互的数据包/波形格式 BLE CS中Step的不同Mode BLE CS中Step的执行过程 Mode0介绍 Mode0 步骤的作用 Mode0步骤的执行过程 Mode0步骤的执行时间 Mode0步骤的时间精度要求 Mode2介绍 Mode2步骤的作用和执行过程 Mode2步骤的执行时间 B…...
简易STL实现 | Queue 的实现
封装: std::queue 在底层容器的基础上 提供了封装。默认情况下,std::queue 使用 std::deque 作为其底层容器,但也可以配置为使用 std::list 或 其他符合要求的容器 时间复杂度: 入队和出队操作 通常是 常数时间复杂度(…...

【hot100-java】LRU 缓存
链表篇 灵神题解 class LRUCache {private static class Node{int key,value;Node prev,next;Node (int k,int v){keyk;valuev;}}private final int capacity;//哨兵节点private final Node dummynew Node(0,0);private final Map<Integer,Node> keyToNode new HashMap&l…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
uniapp 实现腾讯云IM群文件上传下载功能
UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中,群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS,在uniapp中实现: 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

AD学习(3)
1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分: (1)PCB焊盘:表层的铜 ,top层的铜 (2)管脚序号:用来关联原理图中的管脚的序号,原理图的序号需要和PCB封装一一…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001
qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类,直接把源文件拖进VS的项目里,然后VS卡住十秒,然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分,导致编译的时候找不到了。因…...
Easy Excel
Easy Excel 一、依赖引入二、基本使用1. 定义实体类(导入/导出共用)2. 写 Excel3. 读 Excel 三、常用注解说明(完整列表)四、进阶:自定义转换器(Converter) 其它自定义转换器没生效 Easy Excel在…...

Selenium 查找页面元素的方式
Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素,以下是主要的定位方式: 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...

新版NANO下载烧录过程
一、序言 搭建 Jetson 系列产品烧录系统的环境需要在电脑主机上安装 Ubuntu 系统。此处使用 18.04 LTS。 二、环境搭建 1、安装库 $ sudo apt-get install qemu-user-static$ sudo apt-get install python 搭建环境的过程需要这个应用库来将某些 NVIDIA 软件组件安装到 Je…...