初知C++：AVL树

文章目录

  • 初知C++：AVL树
  • 1.AVL树的概念
  • 2.AVL树的是实现
    • 2.1.AVL树的结构
    • 2.2.AVL树的插入
    • 2.3.旋转
    • 2.4.AVL树的查找
    • 2.5.AVL树平衡检测

在这里插入图片描述

初知C++：AVL树

1.AVL树的概念

• AVL树是最先发明的自平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的左右子树都是AV树，且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索⼆叉树，通过控制⾼度差去控制平衡。

• AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家，他们在1962年的论⽂《Analgorithmfortheorganizationofinformation》中发表了它。

• AVL树实现这⾥我们引⼊⼀个平衡因⼦(balancefactor)的概念，每个结点都有⼀个平衡因⼦，任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1，AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡，就像⼀个⻛向标⼀样。

• 思考⼀下为什么AVL树是⾼度平衡搜索⼆叉树，要求⾼度差不超过1，⽽不是⾼度差是0呢？0不是更好的平衡吗？画画图分析我们发现，不是不想这样设计，⽽是有些情况是做不到⾼度差是0的。⽐如⼀棵树是2个结点，4个结点等情况下，⾼度差最好就是1，⽆法作为⾼度差是0 。

• AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在 logN，那么增删查改的效率也可以控制在O(logN)，相⽐⼆叉搜索树有了本质的提升。在这里插入图片描述

2.AVL树的是实现

2.1.AVL树的结构

在下图我们可以看到_parent指针，后续更新平衡因子，有很大的作用。
在这里插入图片描述

2.2.AVL树的插入

2.2.1 AVL树插⼊⼀个值的⼤概过程

  1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。

  2. 新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新
    从新增结点->根结点路径上的平衡因⼦    ，实际中最坏情况下要更新到根，有些情况更新到中间就可
    以停⽌了，具体情况我们下⾯再详细分析。

  3. 更新平衡因⼦过程中没有出现问题，则插⼊结束

  4. 更新平衡因⼦过程中出现不平衡，对不平衡⼦树旋转，旋转后本质调平衡的同时，本质降低了⼦树
    的⾼度，不会再影响上⼀层，所以插⼊结束。

2.2.2 平衡因⼦更新
更新原则：
•
平衡因⼦=右⼦树⾼度-左⼦树⾼度(也可以变为左子树的高度-右子树的高度)
•
只有⼦树⾼度变化才会影响当前结点平衡因⼦。
•
插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在
parent的左⼦树，parent平衡因⼦–
•
parent所在⼦树的⾼度是否变化决定了是否会继续往上更新
更新停⽌条件：
•
更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0或者1->0，说明更新前
parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会
影响parent的⽗亲结点的平衡因⼦，更新结束。
•
更新后parent的平衡因⼦等于1或-1，更新前更新中parent的平衡因⼦变化为0->1或者0->-1，说
明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所
在的⼦树符合平衡要求，但是⾼度增加了1，会影响arent的⽗亲结点的平衡因⼦，所以要继续向上
更新。
•
更新后parent的平衡因⼦等于2或-2，更新前更新中parent的平衡因⼦变化为1->2或者-1->-2，说
明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼
了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：1、把
parent⼦树旋转平衡。2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不
需要继续往上更新，插⼊结束。

更新到10结点，平衡因⼦为2，10所在的⼦树已经不平衡，需要旋转处理
在这里插入图片描述
更新到中间结点，3为根的⼦树⾼度不变，不会影响上⼀层，更新结束
在这里插入图片描述
最坏更新到根停⽌
在这里插入图片描述
2.2.3插⼊结点及更新平衡因⼦的代码实现
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2.3.旋转

2.3.1 旋转的原则

  1. 保持搜索树的规则
  2. 让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度
    旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
    说明：下⾯的图中，有些结点我们给的是具体值，如10和5等结点，这⾥是为了⽅便讲解，实际中是什
    么值都可以，只要⼤⼩关系符合搜索树的规则即可。

2.3.2 右单旋
•
本图1展⽰的是10为根的树，有a/b/c抽象为三棵⾼度为h的⼦树(h>=0)，a/b/c均符合AVL树的要
求。10可能是整棵树的根，也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树，
是⼀种概括抽象表⽰，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体图2/图3/图4/
图5进⾏了详细描述。
•
在a⼦树中插⼊⼀个新结点，导致a⼦树的⾼度从h变成h+1，不断向上更新平衡因⼦，导致10的平
衡因⼦从-1变成-2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树左边太⾼了，需要
往右边旋转，控制两棵树的平衡。
•
旋转核⼼步骤，因为5<b⼦树的值<10，将b变成10的左⼦树，10变成5的右⼦树，5变成这棵树新
的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原
则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了。

下面五张图分别为右旋的各种情况！！！！！（请仔细观看有利于理解哦）
图1：
在这里插入图片描述
图2：
在这里插入图片描述
图3：
在这里插入图片描述
图4：
在这里插入图片描述
图5：
在这里插入图片描述

2.3.3 右单旋代码实现
这里传过去的parent是平衡因子为2或者-2的节点！在这里插入图片描述
2.3.4左单旋
•本图6展⽰的是10为根的树，有a/b/c抽象为三棵⾼度为h的⼦树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树，是⼀种概括抽象表⽰，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体跟上⾯左旋类似。

•在a⼦树中插⼊⼀个新结点，导致a⼦树的⾼度从h变成h+1，不断向上更新平衡因⼦，导致10的平衡因⼦从1变成2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树右边太⾼了，需要往左边旋转，控制两棵树的平衡。

•旋转核⼼步骤，因为10<b⼦树的值<15，将b变成10的右⼦树，10变成15的左⼦树，15变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了。
在这里插入图片描述
2.3.5左单旋代码实现
在这里插入图片描述

2.3.6左右双旋
通过图7和图8可以看到，左边⾼时，如果插⼊位置不是在a⼦树，⽽是插⼊在b⼦树，b⼦树⾼度从h变成h+1，引发旋转，右单旋⽆法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的纯粹的左边⾼，但是插⼊在b⼦树中，10为跟的⼦树不再是单纯的左边⾼，对于10是左边⾼，但是对于5是右边⾼，需要⽤两次旋转才能解决，以5为旋转点进⾏⼀个左单旋，以10为旋转点进⾏⼀个右单旋，这棵树这棵树就平衡了。
图7：
在这里插入图片描述
图8：
在这里插入图片描述
• 图7和图8分别为左右双旋中h0和h1具体场景分析，下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析，另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树，因为我们要对b的⽗亲5为旋转点进⾏左单旋，左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置不同，平衡因⼦更新的细节也不同，通过观察8的平衡因⼦不同，这⾥我们要分三个场景讨论。

• 场景1：h>=1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1并为h并不断更新8->5->10平衡因⼦，引发旋转，其中8的平衡因⼦为-1，旋转后8和5平衡因⼦为0，10平衡因⼦为1。

• 场景2：h>=1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新8->5->10平衡因⼦，引发旋转，其中8的平衡因⼦为1，旋转后8和10平衡因⼦为0，5平衡因⼦为-1。

• 场景3：h==0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新5->10平衡因⼦，引发旋转，其中8的平衡因⼦为0，旋转后8和10和5平衡因⼦均为0。
在这里插入图片描述

2.3.7 左右双旋代码实现
在这里插入图片描述
2.3.8右左双旋
•跟左右双旋类似，下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析，另外我们需要把b⼦树的细节进⼀步展开为12和左⼦树⾼度为h-1的e和f⼦树，因为我们要对b的⽗亲15为旋转点进⾏右单旋，右单旋需要动b树中的右⼦树。b⼦树中新增结点的位置不同，平衡因⼦更新的细节也不同，通过观察12的平衡因⼦不同，这⾥我们要分三个场景讨论。

•场景1：h>=1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为-1，旋转后10和12平衡因⼦为0，15平衡因⼦为1。

•场景2：h>=1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为1，旋转后15和12平衡因⼦为0，10平衡因⼦为-1。

• 场景3：h==0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新15->10平衡因⼦，引发旋转，其中12的平衡因⼦为0，旋转后10和12和15平衡因⼦均为0。
在这里插入图片描述
2.3.9右左双旋代码实现
在这里插入图片描述

2.4.AVL树的查找

在这里插入图片描述

2.5.AVL树平衡检测

我们实现的AVL树是否合格，我们通过检查左右⼦树⾼度差的的程序进⾏反向验证，同时检查⼀下结点的平衡因⼦更新是否出现了问题。（空树也是AVL树哦！！！！）

在这里插入图片描述
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

python如何对变量赋值

python如何对变量赋值

Python 中的变量赋值不需要类型声明。 每个变量在内存中创建&#xff0c;都包括变量的标识&#xff0c;名称和数据这些信息。 每个变量在使用前都必须赋值&#xff0c;变量赋值以后该变量才会被创建。 等号&#xff08;&#xff09;用来给变量赋值。 等号&#xff08;&…
阅读更多...
SpringBoot 整合 阿里云 OSS图片上传

SpringBoot 整合 阿里云 OSS图片上传

一、OOS 简介 ‌阿里云OSS&#xff08;Object Storage Service&#xff09;是一种基于云存储的产品&#xff0c;适用于存储和管理各种类型的文件&#xff0c;包括图片、视频、文档等。‌ 阿里云OSS具有高可靠性、高可用性和低成本等优点&#xff0c;因此被广泛应用于各种场景&…
阅读更多...
2013年国赛高教杯数学建模A题车道被占用对城市道路通行能力的影响解题全过程文档及程序

2013年国赛高教杯数学建模A题车道被占用对城市道路通行能力的影响解题全过程文档及程序

2013年国赛高教杯数学建模 A题 车道被占用对城市道路通行能力的影响 车道被占用是指因交通事故、路边停车、占道施工等因素&#xff0c;导致车道或道路横断面通行能力在单位时间内降低的现象。由于城市道路具有交通流密度大、连续性强等特点&#xff0c;一条车道被占用&#x…
阅读更多...
el-image预览时和el-table边框出现样式穿透问题处理

el-image预览时和el-table边框出现样式穿透问题处理

el-image预览时和el-table边框出现样式穿透问题处理 如图所示 我们只需要在当前组件加一个css即可解决问题 <style lang"scss" scoped> :deep(.el-table__cell) {position: static !important; } </style>
阅读更多...
【Golang】关于Go语言中的定时器原理与实战应用

【Golang】关于Go语言中的定时器原理与实战应用

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…
阅读更多...
结构体 超详解

结构体 超详解

目录 1. 结构体的声明与创建 1.1 结构体类型的定义声明&#xff08;类型&#xff09; 1.2 结构体变量的创建和初始化&#xff08;变量&#xff09; 1.3 结构体变量的特殊声明&#xff08;类型和变量&#xff09; 1.3.1 定义时创建变量 1.3.2 结构体的不完全声明&#xff…
阅读更多...
解决重写QSilder::sliderPress后点击位置与滑块显示位置不一样的问题

解决重写QSilder::sliderPress后点击位置与滑块显示位置不一样的问题

如下代码所示&#xff0c;我是用的是事件过滤器&#xff0c;也可以重写QSlider。 bool KuGouApp::eventFilter(QObject *watched, QEvent *event) {if(watched ui->progressSlider) {if (event->type()QEvent::MouseButtonPress) //判断类型{auto mouseEvent…
阅读更多...
XILINX MIG驱动

XILINX MIG驱动

简介 框架图 本章节主要针对MIG读写做详细介绍，首先创建BLOCK DESIGN，工程连接如下图所示： MIG IP介绍 DATAMOVER的配置这里不再做介绍，结合上篇文章讲到DATAMOVER对BRAM进行读写操作，这里通过AXI桥再加一个MIG模块，MIG模块的配置和说明如下： 1、Clock Period：…
阅读更多...
FPAG学习(5)-三种方法实现LED流水灯

FPAG学习(5)-三种方法实现LED流水灯

目录 1.移位实现LED流水灯 1.1创建工程及源文件代码 1.1.1源代码 1.1.2仿真代码 1.1.3仿真 1.2实验结果 1.2.1总结 2.循环移位实现LED流水灯 3.38译码器实现LED流水灯 3.1原理 3.2源程序 1.移位实现LED流水灯 1.1创建工程及源文件代码 1.1.1源代码 利用计数器计数到…
阅读更多...
Mybatis Plus连接使用ClickHouse也如此简单

Mybatis Plus连接使用ClickHouse也如此简单

通过阅读列式数据库ClickHouse官网&#xff0c;不难看出它有支持JDBC规范的驱动jar包&#xff0c;可以直接集成到Object Relational Mapping框架等&#xff0c;下面我用SpringBootMybatisPlus环境连接ClickHouse来演示一下 集成步骤 1.Maven引入ClickHouse提供的JDBC依赖 <…
阅读更多...
手写mybatis之返回Insert操作自增索引值

手写mybatis之返回Insert操作自增索引值

前言 技术的把控&#xff0c;往往都是体现在细节上&#xff01; 如果说能用行&#xff0c;复制粘贴就能完成需求&#xff0c;出错了就手忙脚乱。那你一定不是一个高级开发&#xff0c;对很多的技术细节也都不了解。 目标 在前面所有的章节内容对 ORM 框架的实现中&#xff0c;其…
阅读更多...
水库抽样算法（大数据算法作业）

水库抽样算法（大数据算法作业）

时隔一个多月&#xff0c;终于想起来写大数据算法基础的实验报告&#xff0c;主要是快截止了&#xff0c;hh 这两天加急把这个报告写完了~ 接下来&#xff0c;写一写证明过程&#xff08;参考书籍&#xff1a;高等教育出版社《数据科学与工程算法基础》&#xff09;主要代码以…
阅读更多...
如何优雅的通过Spring Boot+Redission对订单实现定时关闭

如何优雅的通过Spring Boot+Redission对订单实现定时关闭

简介 在电子商务及支付相关平台中&#xff0c;常规流程是首先生成订单或支付请求&#xff0c;用户随后会在规定时间内完成支付。如果用户未能在预设时限内完成支付动作&#xff0c;系统通常会执行相应的过期处理机制&#xff0c;即自动取消未支付的订单。 此外&#xff0c;这…
阅读更多...
圈子系统APP小程序H5该如何设置IM？

圈子系统APP小程序H5该如何设置IM？

搭建圈子系统的常见问题,以及圈子论坛系统的功能特点 社交圈子论坛系统的概念 圈子小程序源码 多客圈子系统 圈子是什么软件 跟进圈一个系统的软件 为圈子系统APP小程序H5设置IM&#xff08;即时通讯&#xff09;&#xff0c;需要遵循一系列步骤来确保通讯功能的稳定、安全和高…
阅读更多...
Centos基线自动化检查脚本

Centos基线自动化检查脚本

此脚本是一个用于检查Linux系统安全配置的Bash脚本。它通过多项安全标准对系统进行评估&#xff0c;主要检查以下内容&#xff1a; IP地址获取&#xff1a;脚本首先获取主机的IP地址&#xff0c;确保其以10.115开头。 密码策略检查&#xff1a; 检查最小密码长度&#xff08;P…
阅读更多...
yum仓库安装rabbitmq

yum仓库安装rabbitmq

yum仓库安装rabbitmq 1、配置yum仓库 vim /etc/yum.repos.d/rabbitmq.repo # In /etc/yum.repos.d/rabbitmq.repo## ## Zero dependency Erlang ##[rabbitmq_erlang] namerabbitmq_erlang baseurlhttps://packagecloud.io/rabbitmq/erlang/el/7/$basearch repo_gpgcheck1 gpg…
阅读更多...
甲方安全和乙方安全的区别

甲方安全和乙方安全的区别

信息安全工作&#xff0c;总会被人分成甲方和乙方&#xff0c;甲乙方原本只是商务层面需方和供方的代称&#xff0c;在安全领域&#xff0c;成了做公司内部安全和为客户提供安全的区别。 通常意义上&#xff0c;什么是甲方安全人员呢&#xff1f;就是在非安全业务的公司从事信…
阅读更多...
从秒级到小时级：TikTok等发布首篇面向长视频理解的多模态大语言模型全面综述

从秒级到小时级：TikTok等发布首篇面向长视频理解的多模态大语言模型全面综述

文章链接&#xff1a;https://arxiv.org/pdf/2409.18938 亮点直击 追踪并总结从图像理解到长视频理解的MM-LLMs的进展;回顾了各种视觉理解任务之间的差异&#xff0c;并强调了长视频理解中的挑战&#xff0c;包括更细粒度的时空细节、动态事件和长期依赖性;详细总结了MM-LLMs在…
阅读更多...
基于Raspberry Pi人脸识别自动门

基于Raspberry Pi人脸识别自动门

人脸识别自动门 简介 在当今数字化时代&#xff0c;智能家居安全变得越来越重要。今天&#xff0c;我要向大家介绍一个结合了安全性与便利性的项目——人脸识别自动门。这个项目通过在门上实施基于面部识别的高级安全系统&#xff0c;使用摄像头验证房主的面部&#xff0c;自…
阅读更多...
非线性降维方法与概率图模型

非线性降维方法与概率图模型

文章目录 摘要Abstract1.降维的动机1.1 线性方法方法1.1.1 主成分分析&#xff08;PCA)1.1.2 线性判别分析(LDA)1.1.3 线性降维方法中的不足 2.基于流形学习的非线性降维2.1 ISOMAP(Isometric feature mapping)2.2 LLE(locally linear embedding)2.3 LE(Laplacian Eigenmap)拉普…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023