C++数据结构之平衡二叉搜索树(一)——AVL的实现(zig-zag/左右双旋/3+4重构)

目录

  • 00.BBST——平衡二叉搜索树
  • 01.AVL树
  • 02.AVL的插入
      • 2.1单旋——zig 与 zag
      • 2.2插入节点后的单旋实例
      • 2.3手玩小样例
      • 2.4双旋实例
      • 2.5小结
  • 03.AVL的删除
      • 3.1单旋删除
      • 3.2双旋删除
      • 3.3小结
  • 04.3+4重构
  • 05.综合评价AVL
      • 5.1优点
      • 5.2缺点

00.BBST——平衡二叉搜索树

本文是介绍众多平衡二叉搜索树(BBST)的第一篇——介绍AVL树。故先来引入BBST的概念。由于上一篇介绍的二叉搜索树(BST)在极度退化的情况下,十分不平衡,不平衡到只朝一侧偏,成为一条链表,复杂度可达 O ( n ) O(n) O(n),所以我们要在“平衡”方面做一些约束,以防我们的树结构退化得那么严重。

具体来说,含 n n n个节点,高度为 h h h的BST,若满足 h = O ( l o g 2 n ) h=O(log_2 n) h=O(log2n),则称为称为平衡二叉搜索树。

01.AVL树

AVL树是一种BBST(稍后会证明)。它约束自己是否平衡,主要靠一个指标——平衡因子。定义:平衡因子=左子树高度-右子树高度。如果满足 − 2 < 全部平衡因子 < 2 -2<全部平衡因子<2 2<全部平衡因子<2,则该AVL树处于平衡状态;否则,需要靠一系列措施,将其恢复平衡。

首先先证明AVL树满足BBST的要求,即 h = O ( l o g 2 n ) h=O(log_2 n) h=O(log2n)(下式)。我们可转而证明n=Ω(Φh)(即,AVL的节点数不会太少)
在这里插入图片描述

结论:高度为h的AVL Tree 至少有 fib((h+3)-1 个节点
证明:
在这里插入图片描述

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

02.AVL的插入

插入一个节点会导致一串祖先的失衡,删除一个节点至多导致一个祖先失衡。但是,通过后续代码就可发现,删除节点比插入节点复杂的多。原因是,插入节点只要调整好了一处,这条路径上的所有祖先都可平衡,复杂度是O(1)。而删除节点是,调整好了一处平衡,另一处就会不平衡,自下而上层层调整,复杂度是O(n)

2.1单旋——zig 与 zag

zig 与 zag 分别对应右单旋和左单旋。单旋的操作改变的是两个节点的相对位置。改变的是三条线:一上一下一子树。新树根上行指向原根,新树根原子树给到原根。如下图,V到Y那去,Y到C那去。

在这里插入图片描述

2.2插入节点后的单旋实例

在下图处添加一个节点,自上而下更新高度(或平衡因子),g会率先进入不平衡状态。观察g,p,v呈一条线,而非“之”字,所以用单旋调整(之字形对应双旋)。具体来说,对g左单旋。
在这里插入图片描述

2.3手玩小样例

例题:将1,2,3,4,5,6依次插入空的AVL Tree,最终AVL Tree长成什么样?

过程:
首先正常插入1,2;插入3时,1是第一个发现不平衡的节点,zag(1),即对1进行左单旋,成功解决;正常插入4
在这里插入图片描述

插入5时,3是第一个发现不平衡的节点,zag(3),即对3进行左单旋,成功解决
在这里插入图片描述
插入6时,2是第一个发现不平衡的节点,zag(2),即对2进行左单旋,成功解决
在这里插入图片描述

2.4双旋实例

双旋的操作改变的是三个节点的相对位置。分为两种情况——zig-zag与zag-zig。

在下图处添加一个节点,自上而下更新高度(或平衡因子),g会率先进入不平衡状态。观察g,p,v呈“之”字,所以用双旋。具体来说,先zig§,再zag(g).
在这里插入图片描述

2.5小结

AVL树中插入节点引发失衡,经旋转调整后重新平衡,此时包含节点g,p,v的子树高度是不变的子树高度复原,更高祖先也必平衡,全树复衡。故在AVL树中修正插入节点引发的失衡不会出现失衡传播。

03.AVL的删除

删除一个节点至多导致一个祖先失衡。

3.1单旋删除

在这里插入图片描述

3.2双旋删除

在这里插入图片描述

3.3小结

AVL树中删除节点引发失衡,经旋转调整后重新平衡,此时包含节点g,p,v的子树高度有可能不变也有可能减小1,故在AVL树中修正删除节点引发的失衡有可能出现失衡传播。

04.3+4重构

通过观察以上插入和删除的结果示意图,发现结构是一样的——三个节点按顺序呈三角形,四个子树按原来的顺序分别挂在两个孩子节点的下边。(如下图)
在这里插入图片描述

那我们就不必关注具体的技巧了,而是将三个节点和四个子树拆开,像暴力组装魔方那样(先拆散)拼上。

05.综合评价AVL

5.1优点

  1. 查找、插入、删除,最坏时间复杂度为 O ( l o g n ) O(logn) O(logn)
  2. O ( n ) O(n) O(n)的存储空间

5.2缺点

  1. 需要额外维护高度或平衡因子这一指标(后续Splay Tree可改善这一问题)
  2. 删除操作后,最多需旋转 Ω ( l o g n ) \Omega(logn) Ω(logn)
  3. 单次动态调整后,全树拓扑结构的变化量可能高达 Ω ( l o g n ) \Omega(logn) Ω(logn) (RedBlack Tree可缩到 O ( 1 ) O(1) O(1)

谢谢观看~

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

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

相关文章

C语言 函数指针详解

一、函数指针 1.1、概念 函数指针&#xff1a;首先它是一个指针&#xff0c;一个指向函数的指针&#xff0c;在内存空间中存放的是函数的地址&#xff1b; 示例&#xff1a; int Add(int x&#xff0c;int y) {return xy;} int main() {printf("%p\n",&Add);…

2023年电赛---运动目标控制与自动追踪系统(E题)OpenMV方案

前言 &#xff08;1&#xff09;废话少说&#xff0c;很多人可能无法访问GitHub&#xff0c;所以我直接贴出可能要用的代码。此博客还会进行更新&#xff0c;先贴教程和代码 &#xff08;2&#xff09; <1>视频教程&#xff1a; https://singtown.com/learn/49603/ <2…

linuxARM裸机学习笔记(3)----主频和时钟配置实验

引言&#xff1a;本文主要学习当前linux该如何去配置时钟频率&#xff0c;这也是重中之重。 系统时钟来源&#xff1a; 32.768KHz 晶振是 I.MX6U 的 RTC 时钟源&#xff0c; 24MHz 晶振是 I.MX6U 内核 和其它外设的时钟源 1. 7路PLL时钟源【都是从24MHZ的晶振PLL而来…

开源Blazor UI组件库精选:让你的Blazor项目焕然一新!

今天给大家推荐一些开源、美观的Blazor UI组件库&#xff0c;这些优秀的开源框架和项目不仅能够帮助开发者们提高开发效率&#xff0c;还能够为他们的项目带来更加丰富的用户体验。 注&#xff1a;排名不分先后&#xff0c;都是十分优秀的开源框架和项目 ​Ant Design Blazor…

SpringBoot实现数据库读写分离

SpringBoot实现数据库读写分离 参考博客https://blog.csdn.net/qq_31708899/article/details/121577253 实现原理&#xff1a;翻看AbstractRoutingDataSource源码我们可以看到其中的targetDataSource可以维护一组目标数据源(采用map数据结构)&#xff0c;并且做了路由key与目标…

小红书2023“家生活”趋势白皮书

关于报告的所有内容&#xff0c;公众【营销人星球】获取下载查看 核心观点 近年来&#xff0c;年轻人与家的关系愈发紧密。 在小红书上&#xff0c;我们观察到了家居家装内容的蓬勃生长&#xff0c;3 年来相关内容的笔记规模增长了6倍&#xff0c;相关品类的搜索量增加的 3.…

大数据_Hadoop_Parquet数据格式详解

之前有面试官问到了parquet的数据格式&#xff0c;下面对这种格式做一个详细的解读。 参考链接 &#xff1a; 列存储格式Parquet浅析 - 简书 Parquet 文件结构与优势_parquet文件_KK架构的博客-CSDN博客 Parquet文件格式解析_parquet.block.size_davidfantasy的博客-CSDN博…

爆肝整理,性能测试-Jmeter测试+性能测试报告生成(超细整理)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 Jmeter执行原理 …

《吐血整理》进阶系列教程-拿捏Fiddler抓包教程(16)-Fiddler如何充当第三者再识AutoResponder标签-上

1.简介 Fiddler充当第三者&#xff0c;主要是通过AutoResponder标签在客户端和服务端之间&#xff0c;Fiddler抓包&#xff0c;然后改包&#xff0c;最后发送。AutoResponder这个功能可以算的上是Fiddler最实用的功能&#xff0c;可以让我们修改服务器端返回的数据&#xff0c…

ES6 - generator和async函数

一、前言 ES6 诞生以前&#xff0c;异步编程的方法&#xff0c;大概有下面四种。 回调函数事件监听发布/订阅Promise 对象 回调函数本身并没有问题&#xff0c;它的问题出现在多个回调函数嵌套会造成回调地狱&#xff0c;非常不利于代码的维护和逻辑混乱等问题&#xff1b; …

java linq多字段排序时间比较

public static void main(String[] args) {//100万条数据List<CrmInvestSaleUserCount> waitAssignUserList new ArrayList<>();for (int i 0; i < 1000000; i) {waitAssignUserList.add(new CrmInvestSaleUserCount().setSales_username("test" i…

C++stack_queue

stack_queue 容器适配器stack详解栈适配器栈模拟实现 队列详解队列适配器queue模拟实现 容器适配器 除了顺序容器外&#xff0c;标准库还定义了三个顺序容器适配器:stack(栈),queue(队列),priority_queue(优先队列)。适配器是标准库中的一个通用概念。容器&#xff0c;迭代器和…

非凸科技受邀参加中科大线上量化分享

7月30日&#xff0c;非凸科技受邀参加由中国科学技术大学管理学院学生会、超级量化共同组织的“打开量化私募的黑箱”线上活动&#xff0c;分享量化前沿以及求职经验&#xff0c;助力同学们拿到心仪的offer。 活动上&#xff0c;非凸科技量化策略负责人陆一洲从多个角度分享了如…

Vue基本语法

1. 官网&#xff1a; Vue.js - 渐进式 JavaScript 框架 | Vue.js (vuejs.org) 一、示例代码 如下代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible&q…

骨传导耳机什么牌子好?盘点最受欢迎的几款骨传导耳机

骨传导耳机最近一两年越来越受欢迎&#xff0c;市场上不同形态的非入耳式耳机都有&#xff0c;从骨传导&#xff0c;夹耳式到气传导等等都有。骨传导耳机的好处有很多&#xff0c;非入耳式&#xff0c;不伤耳朵&#xff0c;佩戴更舒适更安全。但是一直以来&#xff0c;骨传导耳…

Qt 中引入ffmpeg 动态库

1、前期准备 在qt引入ffmpeg动态库的时候&#xff0c;需要准备ffmpeg的动态库和头文件。 2、打开qt项目 在qt项目的.pro文件中添加以下几行代码 INCLUDEPATH $$PWD/thirtLib/ffmpeg4.2/include win32: LIBS -L$$PWD/thirtLib/ffmpeg4.2/lib/ -lavcodec -lavdevice -lavf…

【SQL应知应会】表分区(三)• Oracle版

欢迎来到爱书不爱输的程序猿的博客, 本博客致力于知识分享&#xff0c;与更多的人进行学习交流 本文收录于SQL应知应会专栏,本专栏主要用于记录对于数据库的一些学习&#xff0c;有基础也有进阶&#xff0c;有MySQL也有Oracle 分区表 • Oracle版 前言一、分区表1.什么是表分区…

搞个个人博客,纯学习想找个纯html模板咋就这难

以前做毕业设计的时候老想找一些不掺杂后端代码的前端模板。 可是下载下来&#xff0c;不是php就是python后台的。看又看不懂&#xff0c;想换语言就必须先把里面的后台代码拿掉。 就很像买了个精装的二手房&#xff0c;白白多花了砸墙钱。 就比如&#xff0c;想做个带菜单的…

Spring Boot集成Swagger3.0,Knife4j导出文档

文章目录 Spring Boot集成Swagger3.0,Knife4j导出文档效果展示如何使用简要说明添加依赖添加配置类测试接口token配置位置 官网 说明情况 demo Spring Boot集成Swagger3.0,Knife4j导出文档 效果展示 如何使用 简要说明 Knife4j的前身是swagger-bootstrap-ui,前身swagger-boo…

区块链实验室(14) - 编译FISCO-BCOS

FISCO-BCOS是一种区块链平台&#xff0c;与Hyperledger和Ethereum有些不同&#xff0c;详见FISCO BCOS 区块链 编译FISCO BCOS源码的目的是修改或者新增其中功能模块&#xff0c;进行对比实验&#xff0c;验证新想法、新创意的效果。编译的步骤很简单&#xff0c;按技术文档一…