c++AVL树的模拟实现

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

目录

1. AVL树

1.1 概念

1.2 AVL树节点的定义

1.3 AVL树的插入（健康版） 

1.4 AVL树的旋转（非健康版）

1. 右旋图解

右旋代码 

 2. 左旋图解

左旋代码 

3. 右左双旋图解

右左双旋代码 

4. 左右双旋图解

左右双旋代码

总结 

1.5 AVL树的验证 

1.5.1 二叉搜索树的验证

1.5.2 AVL树的验证 

验证代码

1.6 AVL树的删除 

1.7 AVL树的性能

 

1. AVL树

1.1 概念

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

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树。
 它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）

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

1.2 AVL树节点的定义

AVL与红黑树中存放的数据都是pair<k,v>结构。 

struct AVLTreeNode
{AVLTreeNode<K, V>* _left;//左孩子AVLTreeNode<K, V>* _right;//右孩子AVLTreeNode<K, V>* _parent;//父亲pair<K, V> _kv;int _bf;//平衡因子，健康的平衡因子绝对值不大于1AVLTreeNode(const pair<K, V>& kv):_bf(0),_kv(kv), _left(nullptr), _right(nullptr),_parent(nullptr){}
};

这里可以看到，AVL树的节点与平衡二叉树的节点区别在于AVL树节点有一个平衡因子的存在，也即1.1概念中所述。同时AVL树采用了三叉链结构，好处在于在对树进行操作时，不必额外存储节点的父亲。

1.3 AVL树的插入（健康版） 

AVL树的插入规则与平衡二叉树一样，不过在插入时要兼顾平衡因子绝对值不大于1的规则，如果某节点的平衡因子绝对值大于1，则需要进行处理。

与平衡二叉树一样，在插入节点时需要先找到插入的位置，这里我们可以复刻平衡二叉树的代码。

插入之后需要对其平衡因子（后面简称bf）进行判断。

那么插入一个节点其bf应该怎么判断呢？

很简单，bf是以该节点为根的树左右子树高度差，我们可以规定，左边插入节点bf--，右边插入节点bf++，新增的节点bf当然是为0的。

 

请看上图，上图只是AVL树的具象图之一，但我们所讲的特性已经足够展示。

左边插入，bf--；右边插入，bf++。我们发现当bf等于0时，对树的影响终止，当bf等于1或-1时，影响会继续向上扩散。那么为什么没有bf==2||bf==-2呢？因为如果发生这种状况，说明树有了问题，需要进行处理（在后面的非健康版讲解）。

根据这个逻辑我们先来实现一段代码。

bool insert(const pair<K, V>& kv)
{if (_root == nullptr)//如果树为空，建立根节点_root = new Node(kv);else//插入{Node* cur = _root,*parent=nullptr;//虽然是三叉链结构，但这里的parent仍需要，因为我们找到的位置是nullptrwhile (cur)//找到需要插入位置的父亲{if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}	else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}	elsereturn false;}cur = new Node(kv);if (kv.first < parent->_kv.first)//判断插入的位置是父亲的左还是右{parent->_left = cur;parent->_bf--;}	else{parent->_right = cur;parent->_bf++;}while (parent)//进行bf的处理{if (parent->_bf == 0)//如果父亲bf==0，终止影响break;else if (parent->_bf == 1 || parent->_bf == -1)//父bf 1 or-1{//继续向上影响，更新父子节点的位置cur = parent;parent = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//需旋转{//树结构已经发生问题，不满足AVL树的特性，需要进行处理} }}return true;
}

1.4 AVL树的旋转（非健康版）

前面的插入是插入后树中节点bf绝对值都不大于1的情况，那么如果有节点的bf绝对值大于1怎么办呢？

这时就需要对其进行处理，所谓处理就是将树的部分进行旋转，使其满足AVL树的特性。

我们来看看。

这里是右旋转。可以看到，右旋转的发生是当cur->bf==-1&&parent->bf==-2时。

1. 右旋图解

右旋代码 

void RotateR(Node* parent)//右单旋
{//记录会进行迁移的节点Node* cur = parent->left;Node* CR = cur->_right;parent->_left = CR;if (CR)CR->_parent = parent;cur->_right = parent;Node* grandfather = parent->_parent;//记录parent的父亲parent->_parent = cur;if (parent == _root)//parent为根{_root = cur;cur->_parent = nullptr;}else//不为根{if (parent == grandfather->_left)//判断parent的位置grandfather->_left = cur;elsegrandfather->_right = cur;cur->parent=grandfather;}cur->_bf = 0;//更新bfparent->_bf = 0;}

 2. 左旋图解

这里是左旋转，左旋转的发生是当cur->bf==1&&parent->bf==2时的。

左旋代码 

void RotateL(Node* parent)//左单旋{//记录会进行迁移的节点Node* cur = parent->_right;//cur节点Node* CL = cur->_left;//cur的左孩子parent->_right = CL;//cur->_left变成parent->_rightif (CL)//如果CL存在，更新其父亲，以免触发空指针的解引用CL->_parent = parent;cur->_left = parent;//parent给cur->_leftNode* grandfather = parent->_parent;//先记录parent的父亲parent->_parent = cur;//更新parent的父亲if (parent == _root)//parent为根，将cur置为_root，其父亲为空{_root = cur;cur->_parent = nullptr;}else//不为根，更新其父亲{if (parent == grandfather->_left)grandfather->_left = cur;elsegrandfather->_right = cur;cur->parent=grandfather;}cur->_bf = 0;parent->_bf = 0;}

难道就仅限于此了吗？当然不是，我们接着看。

当类似以下结构就需要双旋转了，即parent->bf绝对值为2，cur->bf绝对值为1，且二者一正一负时就需要双旋转。

下图为parent==2&&cur->bf==-1，需要右左双旋。

也就是说当parent==-2&&cur->bf==1需要左右双旋。

3. 右左双旋图解

cur->left->bf==1时

而图中cl即cur->left的bf不同，会产生不同的效果，因为cur->left的子树最终会分别成为parent与cur的子树 .

cur->left->bf==1时

右左双旋代码 

void RotateRL(Node* parent)//右左双旋
{Node* cur = parent->_right;Node* CL = cur->_left;int bf = CL->_bf;RotateR(cur);RotateL(parent);CL->_bf = 0;if (bf == -1){cur->_bf = -1;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;parent->_bf = 1;}else{cur->_bf = 0;parent->_bf = 0;}
}

4. 左右双旋图解

cur->right->bf==1时

cur->right->bf==-1时 

左右双旋代码
void RotateLR(Node* parent)//左右双旋
{Node* cur = parent->_left;Node* CR = cur->_right;int bf = CR->_bf;RotateL(cur);RotateR(parent);CR->bf = 0;if (bf == -1){cur->_bf = 0;parent->bf = 1;}else if (bf == 1){cur->_bf = -1;parent->_bf = 0;}else{cur->_bf = 0;parent->_bf = 0;}

总结 

假如以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.5 AVL树的验证 

1.5.1 二叉搜索树的验证

只要中序遍历可以得到一个有序序列，就说明是二叉搜索树。

1.5.2 AVL树的验证 

AVL树的验证：

每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
节点的平衡因子是否计算正确

验证代码
bool _IsBanlance(Node* cur, int& height)
{if (cur == nullptr){return true;height = 0;}int leftheight = 0, rightheight = 0;//记录每棵树的左树与右树高度if (!_IsBanlance(cur->_left, leftheight) || !_IsBanlance(cur->_right, rightheight))//有任何一棵子树不满足条件return false;int SubHeight = rightheight - leftheight;//每个节点其下树的高度差都是他的平衡因子if (abs(SubHeight) > 1)//高度差{cout << cur->_kv.first <<":"<<cur->_bf<< endl;cout << "高度差错误，不平衡" << endl;return false;}height = leftheight > rightheight ? leftheight + 1 : rightheight + 1;//更新高度return true;
}

1.6 AVL树的删除 

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置

1.7 AVL树的性能

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

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

meshlab: pymeshlab沿着椭圆赤道投影展开当前网格的几何图形并保存（geometric cylindrical unwrapping）

meshlab: pymeshlab沿着椭圆赤道投影展开当前网格的几何图形并保存（geometric cylindrical unwrapping）

一、关于环境 请参考&#xff1a;pymeshlab遍历文件夹中模型、缩放并导出指定格式-CSDN博客 二、关于代码 本文所给出代码仅为参考&#xff0c;禁止转载和引用&#xff0c;仅供个人学习。 本文所给出的例子是https://download.csdn.net/download/weixin_42605076/89233917中的…
阅读更多...
爬虫界的“闪电侠”：异步爬虫与分布式系统的实战秘籍

爬虫界的“闪电侠”：异步爬虫与分布式系统的实战秘籍

Hi&#xff0c;我是阿佑&#xff0c;前文给大家讲了&#xff0c;如何做一个合法“采蜜”的蜜蜂&#xff0c;有了这么个自保的能力后&#xff0c;阿佑今天就将和大家踏入 —— 异步爬虫 的大门&#xff01; 异步爬虫大法 1. 引言1.1 爬虫框架的价值&#xff1a;效率与复杂度管理…
阅读更多...
贷款借钱平台 贷款源码 小额贷款系统 卡卡贷源码 小额贷款源码 贷款平台

贷款借钱平台 贷款源码 小额贷款系统 卡卡贷源码 小额贷款源码 贷款平台

贷款平台源码/卡卡贷源码/小贷源码/完美版 &#xff0c; 数据库替换application/database.php 源码下载&#xff1a;https://download.csdn.net/download/m0_66047725/89268533 更多资源下载&#xff1a;关注我。
阅读更多...
Vue原理学习:vdom 和 diff算法(基于snabbdom)

Vue原理学习:vdom 和 diff算法(基于snabbdom)

vdom 和 diff 背景 基于组件化&#xff0c;数据驱动视图。只需关心数据&#xff0c;无需关系 DOM &#xff0c;好事儿。 但是&#xff0c;JS 运行非常快&#xff0c;DOM 操作却非常慢&#xff0c;如何让“数据驱动视图”能快速响应&#xff1f; 引入 vdom 用 vnode 表示真实…
阅读更多...
代购系统搭建，淘宝、1688海外代购系统建设以及部分前端源码展示

代购系统搭建，淘宝、1688海外代购系统建设以及部分前端源码展示

客户登录主界面&#xff0c;可以根据个人需求更换。 可支持个人定制模块化&#xff0c;也有一些模块可供选择 系统演示站测试 部分源码展示&#xff1a; <!DOCTYPE html> <html><head><meta charset"utf-8"> <title>会员中心 – 淘…
阅读更多...
2024生日快乐祝福HTML源码

2024生日快乐祝福HTML源码

源码介绍 2024生日快乐祝福HTML源码&#xff0c;源码由HTMLCSSJS组成&#xff0c;记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面&#xff0c; 源码截图 源码下载 2024生日快乐祝福HTML源码
阅读更多...
Shopline和Shopify哪个更好？Shopline和Shopify的区别

Shopline和Shopify哪个更好？Shopline和Shopify的区别

Shopline和Shopify哪个更好取决于用户面向的市场&#xff0c;面向亚洲市场就更适合有本地化支持的Shopline&#xff0c;而如果希望拓展全球业务&#xff0c;Shopify可能更好。 Shopline和Shopify都是知名的电子商务平台&#xff0c;可以很好的帮助商家搭建和管理在线商店&…
阅读更多...
【C语言】指针（二）

【C语言】指针（二）

目录 一、传值调用和传址调用 二、数组名的理解 三、通过指针访问数组 四、一维数组传参的本质 五、指针数组 六、指针数组模拟实现二维数组 一、传值调用和传址调用 指针可以用在哪里呢&#xff1f;我们看下面一段代码&#xff1a; #include <stdio.h>void Swap(i…
阅读更多...
计算机毕业设计hadoop+hive+hbase学情分析 在线教育大数据 课程推荐系统 机器学习 深度学习 人工智能 大数据毕业设计 知识图谱

计算机毕业设计hadoop+hive+hbase学情分析 在线教育大数据 课程推荐系统 机器学习 深度学习 人工智能 大数据毕业设计 知识图谱

毕 业 设 计&#xff08;论 文&#xff09;开 题 报 告 1&#xff0e;结合毕业设计&#xff08;论文&#xff09;课题情况&#xff0c;根据所查阅的文献资料&#xff0c;每人撰写不少于1000字的文献综述&#xff1a; 一、研究背景和意义 “互联网”和大数据带来了网络教育的蓬…
阅读更多...
Linux查看进程命令ps和top

Linux查看进程命令ps和top

Linux 是一种自由和开放源代码的操作系统&#xff0c;它的使用在全球范围内非常广泛。在 Linux 中&#xff0c;进程是操作系统中最重要的组成部分之一&#xff0c;它代表了正在运行的程序。了解如何查看正在运行的进程是非常重要的&#xff0c;因为它可以帮助你了解系统的运行状…
阅读更多...
付费解锁隐藏动力和续航，订阅制又被特斯拉玩出花了

付费解锁隐藏动力和续航，订阅制又被特斯拉玩出花了

我们知道&#xff0c;「订阅制」早已成互联网领域各路大厂玩烂的操作。 上到程序订阅付费使用&#xff08;例如 Offics、Adobe&#xff09;&#xff0c;下到各类功能服务订阅&#xff08;如影视会员、网盘会员等&#xff09;。 甚至于某东、某宝等网购平台也整出了 VIP 订阅服…
阅读更多...
网络爬虫安全：90后小伙，用软件非法搬运他人原创视频被判刑

网络爬虫安全：90后小伙，用软件非法搬运他人原创视频被判刑

目录 违法视频搬运软件是网络爬虫 如何发现偷盗视频的爬虫&#xff1f; 拦截违法网络爬虫 央视《今日说法》栏目近日报道了一名程序员开发非法视频搬运软件获利超700多万&#xff0c;最终获刑的案例。 国内某知名短视频平台报警称&#xff0c;有人在网络上售卖一款视频搬运…
阅读更多...
声纹识别在无人机探测上的应用

声纹识别在无人机探测上的应用

无人机在民用和军事领域的应用越来越广泛。然而&#xff0c;随着无人机数量的增加&#xff0c;"黑飞"现象也日益严重&#xff0c;对公共安全和隐私构成了威胁。因此&#xff0c;开发有效的无人机探测与识别技术变得尤为重要。及时发现黑飞无人机的存在进而对其型号进…
阅读更多...
专“蜀”盛会！CGT Asia 2024 第六届亚洲细胞与基因治疗创新峰会（成都站）7月火热相邀

专“蜀”盛会！CGT Asia 2024 第六届亚洲细胞与基因治疗创新峰会（成都站）7月火热相邀

在细胞与基因治疗领域&#xff0c;我们正站在一个科技革命的风口上。中国的CGT市场预计将持续快速增长。根据相关分析&#xff0c;预计到2025年整体市场规模将达到25.9亿美元&#xff0c;显示出276%的复合年增长率。这一增长趋势预计将持续到2030年&#xff0c;细胞与基因治疗领…
阅读更多...
视觉SLAM14精讲——三维空间刚体运动1.2

视觉SLAM14精讲——三维空间刚体运动1.2

三维空间刚体运动 欧拉角 欧拉角可以说是零理解成本的表示形式&#xff0c;由于有万向锁的问题被绝大部分项目所抛弃。欧拉角的每个轴旋转都有固定好的名称&#xff0c;这些名称十分直观&#xff1a; Z轴旋转&#xff0c;相当于左右旋转&#xff0c;叫航角&#xff0c;或偏航…
阅读更多...
Latex问题1

Latex问题1

问题 添加bib文件的引用后 \bibliographystyle{IEEEtran} \bibliography{IEEEabrv}之后&#xff0c;出现莫名其妙的错误&#xff0c;如下 IEEEabrv.bib是我的参考文献的bib文件&#xff0c;CCS_1.tex是我的tex文件&#xff0c;bib文件中的内容为 ARTICLE{1,author{Capponi,…
阅读更多...
ElastiCache Serverless for Redis应用场景和性能成本分析

ElastiCache Serverless for Redis应用场景和性能成本分析

一. 前言 传统基于实例节点的 Redis 缓存架构中&#xff0c;扩展性是一个重要影响因素。在很多场景中&#xff0c;例如广告投放、电商交易、游戏对战&#xff0c;流量是经常变化的。无论是主从还是集群模式&#xff0c;当大流量进入时&#xff0c;Redis 处理能力达到上限&…
阅读更多...
2024红帽全球峰会：CEO行业洞察分享

2024红帽全球峰会：CEO行业洞察分享

作为全球IT领域一年一度的行业盛宴&#xff0c;2024红帽全球峰会于近日盛大召开。生成式AI与大模型是当前IT行业最受关注的热点话题&#xff0c;而红帽在生成式AI与大模型领域的最新动作&#xff0c;也理所当然地成为了本届峰会观众目光聚集的焦点。 作为世界领先的开源解决方案…
阅读更多...
MT3035 逆波兰式

MT3035 逆波兰式

思路&#xff1a; 两个栈str1和sr2&#xff0c;分别存放运算符和结果。 如果是数字&#xff0c;直接放入str2中。 如果是运算符&#xff1a; 1. ( &#xff1a;直接放入 str1 2. /-/*// 看栈顶元素&#xff0c;若当前字符优先级比栈顶大&#xff0c;则压到str1中&#x…
阅读更多...
大模型学习笔记九：模型微调

大模型学习笔记九：模型微调

文章目录 一、什么时候需要Fine-Tuning二、用Hugging Face根据电影评论输出来对电影进行情感分类1）安装依赖2）操作流程3）名字解释4）代码导入库和加载模型、加载数据库、加载tokenlizer5）其他相关公共变量赋值（随机种子、标签集评价、标签转token_Id）6）处理数据集：转成…
阅读更多...
最新文章

Copyright @ 2022~2023