【数据结构-树】AVL树

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。
img

  • 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
  • 导航
    • 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
    • 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
    • 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
    • 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
    • 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

    • 一.简介
      • 1.AVL 历史
      • 2.如何判断失衡?
      • 3.节点的高度
      • 4.何时触发失衡判断?
    • 二.自平衡
      • 1.失衡的四种情况
      • 2.LL
      • 3.LR
      • 4.RL
      • 5.RR
      • 6.解决失衡
      • 7.右旋
      • 8.左旋
      • 9.左右旋
      • 10.右左旋
    • 三.新增与删除
      • 1.新增
      • 2.删除
      • 3.完整代码
      • 4.小结

一.简介

1.AVL 历史

AVL 树是一种自平衡二叉搜索树,由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字:Adelson-Velsky 和 Landis,他们是苏联数学家,于 1962 年发表了一篇论文,详细介绍了 AVL 树的概念和性质。

在二叉搜索树中,如果插入的元素按照特定的顺序排列,可能会导致树变得非常不平衡,从而降低搜索、插入和删除的效率。为了解决这个问题,AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2,则通过旋转操作来重新平衡树。

AVL 树是用于存储有序数据的一种重要数据结构,它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率,而且还能够确保树的深度始终保持在 O(log n) 的水平。随着计算机技术的不断发展,AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。

如果一棵二叉搜索树长的不平衡,那么查询的效率会受到影响,如下图

image-20230313090500760

通过旋转可以让树重新变得平衡,并且不会改变二叉搜索树的性质(即左边仍然小,右边仍然大)

image-20230313090817485

2.如何判断失衡?

如果一个节点的左右孩子,高度差超过 1,则此节点失衡,才需要旋转

叶子节点的高度默认为 1

网上遍历,高度越高

3.节点的高度

如何得到节点高度?一种方式之前做过的一道题目:E05. 求二叉树的最大深度(高度),但由于求高度是一个非常频繁的操作,因此将高度作为节点的一个属性,将来新增或删除时及时更新,默认为 1(按力扣说法)

static class AVLNode {int height = 1;int key;Object value;AVLNode left;AVLNode right;// ...
}

求高度代码

这里加入了 height 函数方便求节点为 null 时的高度

private int height(AVLNode node) {return node == null ? 0 : node.height;
}

更新高度代码

将来新增、删除、旋转时,高度都可能发生变化,需要更新。下面是更新高度的代码

private void updateHeight(AVLNode node) {node.height = Integer.max(height(node.left), height(node.right)) + 1;
}

4.何时触发失衡判断?

定义平衡因子(balance factor)如下

平衡因子 = 左子树高度 − 右子树高度 平衡因子 = 左子树高度 - 右子树高度 平衡因子=左子树高度右子树高度

当平衡因子

  • bf = 0,1,-1 时,表示左右平衡
  • bf > 1 时,表示左边太高
  • bf < -1 时,表示右边太高

对应代码

private int bf(AVLNode node) {return height(node.left) - height(node.right);
}

当插入新节点,或删除节点时,引起高度变化时,例如

image-20230310153645397

目前此树平衡,当再插入一个 4 时,节点们的高度都产生了相应的变化,8 节点失衡了

image-20230310153803661

在比如说,下面这棵树一开始也是平衡的

image-20230310154155728

当删除节点 8 时,节点们的高度都产生了相应的变化,6 节点失衡了

image-20230310154232729

二.自平衡

1.失衡的四种情况

  • LL
  • LR
  • RL
  • RR

2.LL

image-20230310154459709

  • 失衡节点(图中 8 红色)的 bf > 1,即左边更高
  • 失衡节点的左孩子(图中 6)的 bf >= 0 即左孩子这边也是左边更高或等高

3.LR

image-20230310154858754

  • 失衡节点(图中 8)的 bf > 1,即左边更高
  • 失衡节点的左孩子(图中 6 红色)的 bf < 0 即左孩子这边是右边更高

对称的还有两种情况

4.RL

image-20230310155048187

  • 失衡节点(图中 3)的 bf <-1,即右边更高
  • 失衡节点的右孩子(图中 6 红色)的 bf > 0,即右孩子这边左边更高

5.RR

image-20230310155347349

  • 失衡节点(图中 3)的 bf <-1,即右边更高
  • 失衡节点的右孩子(图中 6 红色)的 bf <= 0,即右孩子这边右边更高或等高

6.解决失衡

失衡可以通过树的旋转解决。什么是树的旋转呢?它是在不干扰元素顺序的情况下更改结构,通常用来让树的高度变得平衡。

观察下面一棵二叉搜索树,可以看到,旋转后,并未改变树的左小右大特性,但根、父、孩子节点都发生了变化

      4                                   2/ \             4 right             / \2   5      -------------------->    1   4/ \         <--------------------       / \1   3              2 left               3   5

7.右旋

旋转前

image-20230310162158692

  • 红色节点,旧根(失衡节点)
  • 黄色节点,旧根的左孩子,将来作为新根,旧根是它右孩子
  • 绿色节点,新根的右孩子,将来要换爹作为旧根的左孩子

旋转后

image-20230310162442932

代码

private AVLNode rightRotate(AVLNode red) {AVLNode yellow = red.left;AVLNode green = yellow.right;yellow.right = red;red.left = green;return yellow;
}

8.左旋

旋转前

image-20230310162945078

  • 红色节点,旧根(失衡节点)
  • 黄色节点,旧根的右孩子,将来作为新根,旧根是它左孩子
  • 绿色节点,新根的左孩子,将来要换爹作为旧根的右孩子

旋转后

image-20230310163019508

代码

private AVLNode leftRotate(AVLNode red) {AVLNode yellow = red.right;AVLNode green = yellow.left;yellow.left = red;red.right = green;return yellow;
}

9.左右旋

指先左旋左子树,再右旋根节点(失衡),这时一次旋转并不能解决失衡

image-20230310171424362

左子树旋转后

image-20230310171636904

根右旋前

image-20230310171821578

根右旋后

image-20230310171903417

代码

private AVLNode leftRightRotate(AVLNode root) {root.left = leftRotate(root.left);return rightRotate(root);
}

10.右左旋

指先右旋右子树,再左旋根节点(失衡)

image-20230310172212302

右子树右旋后

image-20230310172234154

根左旋前

image-20230310172303012

根左旋后

image-20230310172317379

代码

private AVLNode rightLeftRotate(AVLNode root) {root.right = rightRotate(root.right);return leftRotate(root);
}

判断及调整平衡代码

private AVLNode balance(AVLNode node) {if (node == null) {return null;}int bf = bf(node);if (bf > 1 && bf(node.left) >= 0) {return rightRotate(node);} else if (bf > 1 && bf(node.left) < 0) {return rightLeftRotate(node);} else if (bf < -1 && bf(node.right) > 0) {return leftRightRotate(node);} else if (bf < -1 && bf(node.right) <= 0) {return rightRotate(node);}return node;
}

以上四种旋转代码里,都需要更新高度,需要更新的节点是红色、黄色,而绿色节点高度不变

三.新增与删除

1.新增

public void put(int key, Object value) {root = doPut(root, key, value);
}private AVLNode doPut(AVLNode node, int key, Object value) {if (node == null) {return new AVLNode(key, value);}if (key == node.key) {node.value = value;return node;}if (key < node.key) {node.left = doPut(node.left, key, value);} else {node.right = doPut(node.right, key, value);}updateHeight(node);return balance(node);
}

2.删除

public void remove(int key) {root = doRemove(root, key);
}private AVLNode doRemove(AVLNode node, int key) {if (node == null) {return null;}if (key < node.key) {node.left = doRemove(node.left, key);} else if (node.key < key) {node.right = doRemove(node.right, key);} else {if (node.left == null) {node = node.right;} else if (node.right == null) {node = node.left;} else {AVLNode s = node.right;while (s.left != null) {s = s.left;}s.right = doRemove(node.right, s.key);s.left = node.left;node = s;}}if (node == null) {return null;}updateHeight(node);return balance(node);
}

3.完整代码

public class AVLTree {static class AVLNode {int height = 1;int key;Object value;AVLNode left;AVLNode right;public AVLNode(int key) {this.key = key;}public AVLNode(int key, Object value) {this.key = key;this.value = value;}public AVLNode(int key, Object value, AVLNode left, AVLNode right) {this.key = key;this.value = value;this.left = left;this.right = right;}}AVLNode root;private AVLNode leftRotate(AVLNode p) {AVLNode r = p.right;AVLNode b = r.left;r.left = p;p.right = b;updateHeight(p);updateHeight(r);return r;}private void updateHeight(AVLNode node) {node.height = Integer.max(height(node.left), height(node.right)) + 1;}private AVLNode rightRotate(AVLNode r) {AVLNode a = r.left;AVLNode b = a.right;a.right = r;r.left = b;updateHeight(r);updateHeight(a);return a;}private AVLNode leftRightRotate(AVLNode p) {AVLNode r = p.left;p.left = leftRotate(r);return rightRotate(p);}private AVLNode rightLeftRotate(AVLNode p) {AVLNode r = p.right;p.right = rightRotate(r);return leftRotate(p);}private int height(AVLNode node) {return node == null ? 0 : node.height;}public void remove(int key) {root = doRemove(root, key);}private AVLNode doRemove(AVLNode node, int key) {if (node == null) {return null;}if (key < node.key) {node.left = doRemove(node.left, key);} else if (node.key < key) {node.right = doRemove(node.right, key);} else {if (node.left == null) {node = node.right;} else if (node.right == null) {node = node.left;} else {AVLNode s = node.right;while (s.left != null) {s = s.left;}s.right = doRemove(node.right, s.key);s.left = node.left;node = s;}}if (node == null) {return null;}updateHeight(node);return balance(node);}public void put(int key, Object value) {root = doPut(root, key, value);}private AVLNode doPut(AVLNode node, int key, Object value) {if (node == null) {return new AVLNode(key, value);}if (key == node.key) {node.value = value;return node;}if (key < node.key) {node.left = doPut(node.left, key, value);} else {node.right = doPut(node.right, key, value);}updateHeight(node);return balance(node);}private int bf(AVLNode node) {return height(node.left) - height(node.right);}private AVLNode balance(AVLNode node) {if (node == null) {return null;}int bf = bf(node);if (bf > 1 && bf(node.left) >= 0) {return rightRotate(node);} else if (bf > 1 && bf(node.left) < 0) {return rightLeftRotate(node);} else if (bf < -1 && bf(node.right) > 0) {return leftRightRotate(node);} else if (bf < -1 && bf(node.right) <= 0) {return rightRotate(node);}return node;}
}

4.小结

AVL 树的优点:

  1. AVL 树是一种自平衡树,保证了树的高度平衡,从而保证了树的查询和插入操作的时间复杂度均为 O(logn)。
  2. 相比于一般二叉搜索树,AVL 树对查询效率的提升更为显著,因为其左右子树高度的差值不会超过 1,避免了二叉搜索树退化为链表的情况,使得整棵树的高度更低。
  3. AVL 树的删除操作比较简单,只需要像插入一样旋转即可,在旋转过程中树的平衡性可以得到维护。

AVL 树的缺点:

  1. AVL 树每次插入或删除节点时需要进行旋转操作,这个操作比较耗时,因此在一些应用中不太适用。
  2. 在 AVL 树进行插入或删除操作时,为保持树的平衡需要不断进行旋转操作,在一些高并发环节和大数据量环境下,这可能会导致多余的写锁导致性能瓶颈。
  3. AVL 树的旋转操作相对较多,因此在一些应用中可能会造成较大的空间浪费。

觉得有用的话点个赞 👍🏻 呗。
❤️❤️❤️本人水平有限,如有纰漏,欢迎各位大佬评论批评指正!😄😄😄

💘💘💘如果觉得这篇文对你有帮助的话,也请给个点赞、收藏下吧,非常感谢!👍 👍 👍

🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧!🌙🌙🌙

img

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

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

相关文章

MFC中嵌入显示opencv窗口

在MFC窗体中建立一个Picture Control控件,用于显示opencv窗口 在属性中设置图片控件的资源ID为IDC_PIC1 主要的思路: 使用GetWindowRect可以获取图片控件的区域 使用cv::resizeWindow可以设置opencv窗口的大小,适合图片控件的大小 使用cvGetWindowHandle函数可以获取到ope…

Flutter 通过BottomSheetDialog实现抖音打开评论区,内容自动上推、缩放效果

一、先来看下实现的效果 实现上面的效果需要解决俩个问题 当列表进行向下滑动到顶部的时候&#xff0c;继续滑动可以让弹窗向下收起来弹出上下拖动的时候&#xff0c;视图内容跟着上下移动、缩放大小 二、实现弹窗上下滑动的时候&#xff0c;动态改变内容区的位置和大小 通过…

PPT 生成整数序列字典序的r-组合算法

生成整数序列字典序的r-组合算法 一、PPT效果展示二、问题2.1 简述2.2 算法简述2.3 例子 三、PPT实现 一、PPT效果展示 二、问题 2.1 简述 给定一个整数序列 (1&#xff0c;2&#xff0c;3&#xff0c;…n)&#xff0c;输出其所有字典序的r-组合&#xff0c;注意事项&#xf…

前端html原生页面兼容多端H5和移动端适配方案

目录 图片代码最后 图片 是一个注册页面 代码 自己查看效果 注意: 单位全部用rem这样才能保证兼容性适配多端&#xff0c;px转rem转换公式 1px 1/37.5rem 所以想要20px应该对应20/37.5 0.53rem <!DOCTYPE html> <html lang"en"><head><met…

关于时空数据的培训 GAN:实用指南(第 01/3 部分)

第 1 部分&#xff1a;深入了解 GAN 训练中最臭名昭著的不稳定性。 一、说明 GAN 是迄今为止最受欢迎的深度生成模型&#xff0c;主要是因为它们最近在图像生成任务上产生了令人难以置信的结果。然而&#xff0c;GAN并不容易训练&#xff0c;因为它们的基本设计引入了无数的不稳…

可变参数JAVA

public class Main {public static void main(String[] args) {//方法形参的个数是可以变化的//格式&#xff1a;属性类型...名字System.out.println(getSum(1,2,3,4,5,6,7,8));}//通过键值对对象来遍历&#xff1b;public static int getSum(int a,int...args){//可变参数;int…

ArcGIS 10.7安装教程!

软件介绍&#xff1a;ArcGIS是一款专业的电子地图信息编辑和开发软件&#xff0c;提供一种快速并且使用简单的方式浏览地理信息&#xff0c;无论是2D还是3D的信息。软件内置多种编辑工具&#xff0c;可以轻松的完成地图生产全过程&#xff0c;为地图分析和处理提供了新的解决方…

【蓝桥杯选拔赛真题60】Scratch旋转风车 少儿编程scratch图形化编程 蓝桥杯选拔赛真题解析

目录 scratch旋转风车 一、题目要求 编程实现 二、案例分析 1、角色分析

Linux自动化构建项目工具——Makefile/makefile

目录 一&#xff0c;背景知识 二&#xff0c;makefile/Makefile的编写 1.创建makefile/Makefile文件 2.在Makefile文件里写编译代码 3.伪目标——.PHONY 1.伪目标的特点 2.怎样实现总是被执行 4.Makefile/makefile文件的不同编写风格 1.背景知识 2.改写 一&#xff0c;背…

goaccess 日志分析 nginx

分析命令&#xff1a; goaccess -a -d -f /mnt/winshare/access-2023070112.log -p goaccess.conf -o /mydata/nginx/html/2023070112_new.html分析日志时的参数 goaccess使用参数详解-a 开启 UserAgent 列表。开启后会降低解析速度 -c 在程序开始运行时显示 日志/日期 配…

nbcio-boot移植到若依ruoyi-nbcio平台里一formdesigner部分(三)

因为这个版本的若依plus不支持本地文件上传&#xff0c;所以需要增加这些本地上传文件的后端代码 和前端代码修改。 1、后端部分 先配置跳过测试吧&#xff0c;平时编译也不需要这个 <!--添加配置跳过测试--><plugin><groupId>org.apache.maven.plugins<…

新增动态排序图、桑基图、AntV组合图,DataEase开源数据可视化分析平台v1.18.10发布

2023年9月14日&#xff0c;DataEase开源数据可视化分析平台正式发布v1.18.10版本。 这一版本的功能升级包括&#xff1a;数据集方面&#xff0c;对字段管理的后台保存做了相关优化&#xff0c;降低了资源消耗&#xff1b;仪表板方面&#xff0c;对联动、查询结果以及过滤组件等…

分享!JetBrains IDE中的GitLab支持

GitLab是流行的基于git的软件开发和部署平台之一&#xff0c;虽然很长一段时间以来&#xff0c;所有基本git操作都已经可以通过GitLab实现&#xff0c;但GitLab集成仍是JetBrains社区的一大最热门请求。为此&#xff0c;JetBrains团队今年与GitLab联手提供了这种类型的集成。 …

PWA及小程序在系统生态方面的支持对比

PWA代表“渐进式网络应用”&#xff08;Progressive Web Application&#xff09;。它是一种结合了网页和移动应用程序功能的技术概念。PWA旨在提供类似于原生应用程序的用户体验&#xff0c;包括离线访问、推送通知、后台同步等功能&#xff0c;同时又具有网页的优势&#xff…

SQL SERVER 中无法删除table ‘biao’,因为它不存在或者您不具备相应的权限

删除table表 1.删除表示提示&#xff1a;SQL SERVER 中无法删除table ‘biao’&#xff0c;因为它不存在或者您不具备相应的权限。2.原因3.解决方法3.1 图3.2 图3.3 图3.4 图 1.删除表示提示&#xff1a;SQL SERVER 中无法删除table ‘biao’&#xff0c;因为它不存在或者您不具…

Linux基础入门

一、操作系统安装方法 1、使用u盘安装 工具&#xff08;前提条件&#xff09;&#xff1a; <1>u盘 <2>镜像文件iso/msdn.itellyou.cn <3>把u盘做成PE&#xff1a;大白菜/老毛桃/winPE/软碟通/ultralSO 设置BIOS&#xff1a;通过u盘启动 安装系统&…

go 包的引入

本文介绍下下go包的管理&#xff0c;以linux平台为例。 先看下目录结构&#xff1a; test目录下的test.go test2目录下的test.go 主函数的调用 此时执行会报错&#xff0c;需要用mod进行包的管理,执行下面命令 go mod init godir 生成go.mod文件 执行结果&#xff1a;

【Spring Boot】数据缓存Redis实现高并发 —— Redis入门

&#x1f33f;欢迎来到衍生星球的CSDN博文&#x1f33f; &#x1f341;本文主要学习Redis的入门 &#x1f341; &#x1f331;我是衍生星球&#xff0c;一个从事集成开发的打工人&#x1f331; ⭐️喜欢的朋友可以关注一下&#x1faf0;&#x1faf0;&#x1faf0;&#xff0c;…

【Redis】深入探索 Redis 的数据类型 —— 列表 List

文章目录 一、List 类型介绍二、List 类型相关命令2.1 LPUSH 和 RPUSH、LPUSHX 和 RPUSHX2.2 LPOP 和 RPOP、BLPOP 和 BRPOP2.3 LRANGE、LINDEX、LINSERT、LLEN2.4 列表相关命令总结 三、List 类型内部编码3.1 压缩列表&#xff08;ziplist&#xff09;3.2 链表&#xff08;lin…

1-5 AUTOSAR数据交换文件ARXML

总目录——AUTOSAR入门详解AUTOSAR入门详解目录汇总&#xff1a;待续中。。。https://xianfan.blog.csdn.net/article/details/132818463 目录 一、Arxml文件 二、各类ARXML文件 一、Arxml文件 arxml文件是AUTOSAR&#xff08;Automotive Open System Architecture&#xff0…