平衡有序二叉树的构建（AVL树，一步一步讲解，看完不会来砍我）

序

纸上得来终觉浅，觉知此事要躬行

读者只有自己一步一步的跟着做，才能真正学会，看是看不会的

平衡有序二叉树的构建

平衡二叉树

整棵树任意一个节点的左右子树高度差值的绝对值<=1（高度相等或相差1）

demo1

在这里插入图片描述
根节点3不平衡，左子树高度为2，右子树高度为0，相差2>1

demo2

在这里插入图片描述
平衡，所有结点都满足左右子树高度差<=1的特性

有序二叉树

整个树的所有结点满足左孩子结点数值<根节点<右孩子结点数值，有序二叉树的中序遍历就恰好是数值从小到大的排列顺序

demo

在这里插入图片描述

所有结点都满足，左孩子比自己小，右孩子比自己大的特性

中序遍历（左根右）

3，7，21，34，78，322（从小到大）

平衡有序二叉树

上述两者的特性都满足的二叉树

为什么会出现平衡有序二叉树，有序二叉树不就足够了吗

有序二叉树的性质确实是非常好
①构建完成之后自动就是排好序的状态，不需要我们额外的操作进行排序（哪怕是最快的排序时间复杂度也得至少O(nlogn))
②查询可以使用折半查找，仅需要O(logn)的时间复杂度即可
③增删改都不复杂（O(logn)级别），不需要额外的申请空间

但是以上情况只出现在有序二叉树比较完美的情况下

如果是这种有序二叉树
在这里插入图片描述
有序二叉树就会退化为有序链表，CURD的效率都会退化为O(n)级别

所以我们才需要平衡有序二叉树

构建

平衡有序二叉树的结点的插入，如果导致不满足平衡二叉树的特性，就要进行树的旋转

我在这里非常不建议读者去乱搞什么左旋右旋，很容易旋晕，我们只需要记住怎么转变即可

通用的方法论（LL型，RR型，LR型，RL型）

4个步骤，2点注意

4个步骤

  1. 插入后，不平衡的结点向造成不平衡的结点走两步，根据这两步确定不平衡的类型
  2. 把无关结点（需要改变的三个结点当中的中间结点的兄弟结点）去掉，这些结点等待后续重新插入
  3. 三个结点的改变
  4. 最后重新插入刚才去掉的结点

2点注意

  1. 若一个结点的插入，同时导致了两个结点的不平衡，优先解决离叶子节点近的结点
    在这里插入图片描述
  2. 若两步走之后，不平衡结点与造成不平衡的结点不能完全相连，那么将造成不平衡的结点与其父节点看成一个整体
    在这里插入图片描述
    将18和19看成一个整体

看不懂？我们直接实战

LL型
demo1

在这里插入图片描述

直接套我们的方法论

  1. 插入后，不平衡的结点向造成不平衡的结点走两步，根据这两步确定不平衡的类型
    3是造成不平衡的结点，5是不平衡结点（左子树高度2-右子树高度0 = 2>1），不平衡的结点 向造成不平衡的结点走两步，我们发现都是向左走，确定类型：LL型

  2. 把无关结点（需要改变的三个结点当中的中间结点的兄弟结点）去掉，这些结点等待后续重新插入
    这里比较幸运，没有那么多其他结点，我们不需要去除结点，当然第四步也不需要重新插入

  3. 三个结点的改变
    不平衡结点5顺时针旋转，成为4的右孩子
    在这里插入图片描述

  4. 最后重新插入剩余结点

这里不涉及复杂情况，我们现在看一种比较复杂的LL型

demo2

在这里插入图片描述

11的插入同时导致了13和15的不平衡，我们优先解决13（注意点1）

  1. 插入后，不平衡的结点向造成不平衡的结点走两步，根据这两步确定不平衡的类型
    11是造成不平衡的结点，13是不平衡结点（左子树高度2-右子树高度0 = 2>1），不平衡的结点向造成不平衡的结点走两步，我们发现都是向左走，确定类型：LL型
    在这里插入图片描述

  2. 把无关结点（需要改变的三个结点之中的后两个结点的左右子树）去掉，这些结点等待后续重新插入
    后两个结点指的是11和12，这两个结点都没有左右孩子，所以没有结点需要暂时删除
    在这里插入图片描述

  3. 三个结点的改变
    不平衡结点13顺时针旋转，成为12的右孩子

在这里插入图片描述

  1. 最后重新插入剩余结点
RR型
demo1

在这里插入图片描述

直接套我们的方法论

  1. 插入后，不平衡的结点向造成不平衡的结点走两步，根据这两步确定不平衡的类型
    19是造成不平衡的结点，15是不平衡结点（右子树高度3-左子树高度1 = 2>1），不平衡的结点向造成不平衡的结点走两步，我们发现都是向右走，确定类型：RR型
    在这里插入图片描述

  2. 把无关结点（需要改变的三个结点当中的中间结点的兄弟结点）去掉，这些结点等待后续重新插入
    去掉16，同时18和19看成一个整体
    在这里插入图片描述

  3. 三个结点的改变
    不平衡结点15逆时针旋转，成为17的左孩子
    在这里插入图片描述

  4. 最后重新插入刚才去掉的结点

在这里插入图片描述

LR型
demo1

在这里插入图片描述
直接套我们的方法论

  1. 插入后，不平衡的结点向造成不平衡的结点走两步，根据这两步确定不平衡的类型

    15是造成不平衡的结点，16,17是不平衡结点，优先16，不平衡的结点向造成不平衡的结点走两步，先左后右，确定类型：LR型
    在这里插入图片描述

  2. 把无关结点（需要改变的三个结点当中的中间结点的兄弟结点）去掉，这些结点等待后续重新插入
    这里比较幸运，没有那么多其他结点，我们不需要去除结点，当然第四步也不需要重新插入

  3. 三个结点的改变
    15和13互换位置，变成LL型；然后16顺时针旋转，成为15的右孩子
    在这里插入图片描述
    在这里插入图片描述
    其实就是后两个结点互换位置变成LL，然后中间节点顶上去变成父节点，非常简单

  4. 最后重新插入刚才去掉的结点

RL型

在这里插入图片描述

直接套我们的方法论

  1. 插入后，不平衡的结点向造成不平衡的结点走两步，根据这两步确定不平衡的类型
    16是造成不平衡的结点，15是不平衡结点（左子树高度3-右子树高度1 = 2>1），不平衡的结点向造成不平衡的结点走两步，我们发现先向右后向左，确定类型：RL型
    在这里插入图片描述

  2. 把无关结点（需要改变的三个结点当中的中间结点的兄弟结点）去掉，这些结点等待后续重新插入
    去掉19，同时16，17看成一个整体
    在这里插入图片描述

  3. 三个结点的改变

17，18互换位置变成RR型，然后17成为新的父节点，15是17的左子树
在这里插入图片描述
在这里插入图片描述
4. 最后重新插入刚才去掉的结点
在这里插入图片描述

终极demo

画出关键字序列{25,27,30,12,11,18,14,20,15,22,50,16,74,60,43,16,90,46,31}构造的一课平衡二叉树

这里推荐一个网站，可以动态展现这个过程

AVL Tree

我们一步一步来

在这里插入图片描述
这个明显是RR型，让27成为新的父节点
在这里插入图片描述
在这里插入图片描述
11的插入同时造成了25和27的不平衡，优先25；明显LL型，让12成为新的父节点

在这里插入图片描述

在这里插入图片描述

18的插入导致了27的不平衡，25和18看成一个整体；显然是LR型，首先12和25互换位置变成LL型，然后25成为新的父节点，27成为25的右子树；18重新插入

在这里插入图片描述
在这里插入图片描述
15的插入导致了12和25的不平衡，12优先；

在这里插入图片描述
明显RL型，14和15看成一个整体，去掉20
在这里插入图片描述
14和18互换位置，转成RR型，

在这里插入图片描述
然后14成为新的父节点
在这里插入图片描述
20和15重新插入

在这里插入图片描述
22的插入导致了25的不平衡，LR型
在这里插入图片描述

去掉12，15；18，19，22看成一个整体；

在这里插入图片描述
18，14互换位置变成LL型
在这里插入图片描述
18成为新的父节点
在这里插入图片描述
剩余结点重新插入

在这里插入图片描述
50的插入导致了25的不平衡
在这里插入图片描述
RR型，省略步骤
在这里插入图片描述
60的插入同时导致了50，30，18的不平衡
在这里插入图片描述

RL型，
在这里插入图片描述

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

在这里插入图片描述

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

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

总结

平衡有序二叉树的构建，相当的复杂，非常耗费计算机的cpu资源

我们需要找出一种更为简单的，构建平衡有序二叉树的方式——红黑树

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

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

相关文章

java中的字节流和File类

java中的字节流和File类

目录 正文&#xff1a; 1.File类 1.1概述 1.2常用方法 2.FileInputStream 2.1概述 2.2常用方法 3.FileOutputStream 3.1概述 3.2常用方法 总结&#xff1a; 正文&#xff1a; 1.File类 1.1概述 File类是Java中用来表示文件或目录的类&#xff0c;它提供了一系列方…
阅读更多...
【C++语言】字符串String类的深拷贝与浅拷贝

【C++语言】字符串String类的深拷贝与浅拷贝

深浅拷贝定义 拷贝对象时&#xff0c;需要创建相同的字节序、类型、和资源。 经典的string类问题 // 为了和标准库区分&#xff0c;此处使用String class String { public:/*String():_str(new char[1]){*_str \0;}*///String(const char* str "\0") 错误示范//…
阅读更多...
Dynamic World Training Data动态世界训练和验证数据集（土地分类和土地利用）

Dynamic World Training Data动态世界训练和验证数据集（土地分类和土地利用）

摘要： 动态世界训练数据（Dynamic World Training Data ）是一个由超过 50 亿像素的人工标注欧空局哨兵-2 卫星图像组成的数据集，分布在从世界各地收集的 24000 块瓷砖上。该数据集旨在训练和验证自动土地利用和土地覆被制图算法。分辨率为 10 米的 5.1km x 5.1km 瓦片采用十…
阅读更多...
软件系统安全设计（安全保证措施）

软件系统安全设计（安全保证措施）

软件安全保证措施word 软件所有全套资料获取进主页或者本文末个人名片直接。
阅读更多...
欧拉回路（leetcode 重新安排行程）

欧拉回路（leetcode 重新安排行程）

先学习一下欧拉回路是怎么一回事。 对于图中这七个节点&#xff0c;从节点1出发&#xff0c;最终要到达节点1&#xff0c;并且每条路只能走一次&#xff0c;且每条路都得走过一次。 使用dfs&#xff0c;如果算法按照字典序的排列方式选择下一个节点。 第一部分&#xff1a;那…
阅读更多...
设计模式: 模板模式

设计模式: 模板模式

目录 一&#xff0c;模板模式 二&#xff0c;特点 三&#xff0c;组成部分 四&#xff0c;实现步骤 五&#xff0c;案例 一&#xff0c;模板模式 模板模式&#xff08;Template Pattern&#xff09;是一种行为型设计模式&#xff0c;它在超类中定义了一个算法的骨架&#…
阅读更多...
spring boot 启动流程详解

spring boot 启动流程详解

主启动类 SpringBootApplication MapperScan("com.example.mapper") public class StableBootApplication {public static void main(String[] args) {SpringApplication.run(StableBootApplication.class,args);} }SpringApplication类中有个静态run()方法&#xf…
阅读更多...
ICode国际青少年编程竞赛- Python-1级训练场-for循环练习

ICode国际青少年编程竞赛- Python-1级训练场-for循环练习

ICode国际青少年编程竞赛- Python-1级训练场-for循环练习 1、 for i in range(3):Dev.step(4)Dev.turnLeft()2、 for i in range(3):Dev.step(2)Dev.turnRight()Dev.step(2)Dev.turnLeft()3、 for i in range(3):Dev.step(2)Dev.turnRight()Dev.step(2)Dev.turnLeft()4、 for…
阅读更多...
飞致云开源社区月度动态报告（2024年4月）

飞致云开源社区月度动态报告（2024年4月）

自2023年6月起&#xff0c;中国领先的开源软件公司FIT2CLOUD飞致云以月度为单位发布《飞致云开源社区月度动态报告》&#xff0c;旨在向广大社区用户同步飞致云旗下系列开源软件的发展情况&#xff0c;以及当月主要的产品新版本发布、社区运营成果等相关信息。值得注意的是&…
阅读更多...
VS下编译cuda代码MSB3721，返回代码255

VS下编译cuda代码MSB3721，返回代码255

查了一天才找到问题 将Generate Relocatable Device Code 设置为true
阅读更多...
Kelpa-小型服务器开发框架分享

Kelpa-小型服务器开发框架分享

分享我的服务器开发框架--Kelpa&#xff1a; 这是一个由现代C编写的小型、学习性质的服务器框架&#xff0c;包含压缩&#xff0c;序列化&#xff0c;IO调度&#xff0c;Socket封装&#xff0c;文件配置&#xff0c;日志库等多个完整自研模块&#xff1a; 项目目前仍处于开发阶…
阅读更多...
【银角大王——Django课程——用户表的基本操作】

【银角大王——Django课程——用户表的基本操作】

Django课程——用户表的基本操作 模板的继承用户管理用户列表展示新建用户Django组件原始方法【麻烦&#xff0c;太原始】form组件modelform组件 使用modelsform组件编写添加页面 模板的继承 &#xff08;1&#xff09;先写一个页面模板————这个案例中的模板基本上就是一个…
阅读更多...
无言：破局之道：顿悟+坚持——早读(逆天打工人爬取热门微信文章解读)

无言：破局之道：顿悟+坚持——早读(逆天打工人爬取热门微信文章解读)

致无言 引言Python 代码第一篇 洞见 7年跟踪调查北京28个精英家庭&#xff1a;为什么顶尖大学孩子大多来自有钱家庭&#xff1f;第二篇 人民日报 来了&#xff01;新闻早班车要闻社会政策 结尾 控制你的情绪 否则它将控制你 在紧张的游戏中 控制情绪 避免冲动行为 是每个玩家的…
阅读更多...
学习java的继承

学习java的继承

1.什么是继承 java中提供了一个关键字&#xff0c;extends&#xff0c;可以让一个类与另一个类建立起父子关系。 例如 public class B extends A { --- } 在这里&#xff0c;我们称A类为父类&#xff08;也被称为基类或者超类&#xff09;B类称为子类&#xff08;或者是派生…
阅读更多...
IDEA 申请学生许可证

IDEA 申请学生许可证

如果你有学生账号&#xff0c;并且账号是 EDU 结尾的&#xff0c;可以申请 IDEA 的学生许可证。 有效期一年&#xff0c;完全免费。 在界面上输入邮件地址&#xff0c;然后单击按钮提交。 邮件中单击链接 JetBrains 会把一个带有链接的邮件发送到你的邮箱中。 单击邮箱中的…
阅读更多...
【CTF MISC】XCTF GFSJ0512 give_you_flag Writeup（图像处理+QR Code识别）

【CTF MISC】XCTF GFSJ0512 give_you_flag Writeup（图像处理+QR Code识别）

give_you_flag 菜狗找到了文件中的彩蛋很开心&#xff0c;给菜猫发了个表情包 解法 图片的最后一帧好像闪过了什么东西。 用 Photoshop 打开&#xff0c;检查时间轴。 找到一张二维码&#xff0c;但是缺了三个角&#xff08;定位图案&#xff09;&#xff0c;无法识别。 找一…
阅读更多...
C语言----贪吃蛇（补充）

C语言----贪吃蛇（补充）

各位看官好&#xff0c;我想大家应该已经看过鄙人的上一篇博客贪吃蛇了吧。鄙人在上一篇博客中只是着重的写了贪吃蛇的实现代码&#xff0c;但是前期的一些知识还没有具体的介绍&#xff0c;比如确认光标位置&#xff0c;句柄等。那么我这一篇博客就来补充上一篇博客所留下来的…
阅读更多...
使用 Wireshark 实现 ARP 嗅探监听网络

使用 Wireshark 实现 ARP 嗅探监听网络

前言 Wireshark是一个开源的网络协议分析工具&#xff0c;用于捕获和分析网络数据包。它可以在多个操作系统上运行&#xff0c;并提供了强大的功能和用户友好的界面。 通过Wireshark&#xff0c;用户可以捕获网络流量&#xff0c;并对其进行深入的分析。它支持多种协议的解析…
阅读更多...
计算机网络-408考研

计算机网络-408考研

后续更新发布在B站账号&#xff1a;谭同学很nice http://【计算机408备考-什么是计算机网络&#xff0c;有什么特点&#xff1f;】 https://www.bilibili.com/video/BV1qZ421J7As/?share_sourcecopy_web&vd_source58c2a80f8de74ae56281305624c60b13http://【计算机408备考…
阅读更多...
一文读懂Mysql数据库索引原理

一文读懂Mysql数据库索引原理

MyISAM 存储引擎索引实现&#xff1a; MyISAM 索引文件&#xff08;磁盘上表对应.MYI&#xff09;和数据文件&#xff08;MYD&#xff09;是分离的&#xff08;非聚集&#xff09; InnoDB 存储引擎索引实现&#xff1a; InnoDB 索引实现&#xff08;聚集&#xff09; 表数据文…
阅读更多...
最新文章

Copyright @ 2022~2023