JavaDS —— AVL树

前言

本文章将介绍 AVL 树的概念,重点介绍AVL 树的插入代码是如何实现的,如果大家对 AVL 树的删除(还是和二叉搜索树一样使用的是替换删除法,然后需要判断是否进行旋转调整)感兴趣的话,可以自行去翻阅其他资料~~

概念

回顾二叉搜索树

之前我们就了解到二叉搜索树中序遍历的时候数据是有序的,这是由于二分搜索树具有以下性质:
若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

最好的搜索时间复杂度为 O(logN),但是如果插入的数据是有序或者逆序的时候,二叉搜索树就会变成一颗单分支的二叉树,搜索的时间复杂度也最差,为 O(N)

那么能不能让二叉搜索树在插入结点的时候就能始终保持平衡,也就是保持一颗饱满的二叉树形态呢?

这就是我们要学习的 AVL 树

AVL 树

两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述二叉搜索树存在的问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。

一棵AVL树具有以下性质:
AVL 树同时具有二叉搜索树的性质
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过 1 (-1、0、1),即始终保持高度平衡
在这里插入图片描述

如果一棵二叉搜索树是高度平衡的,它就是AVL树。

平衡因子

平衡因子就是左右子树高度之差

这里我定义平衡因子等于右子树高度减去左子树的高度

以下图为例:
在这里插入图片描述
A 结点右子树高度等于左子树高度,平衡因子为0
B 结点右子树高度减左子树高度等于 -1,平衡因子为 -1
C 结点右子树高度减左子树高度等于 1,平衡因子为 1
D 结点右子树高度等于左子树高度,平衡因子为0
E 结点右子树高度等于左子树高度,平衡因子为0

结点定义

和普通的树结点一样,具有左引用,右引用,数据val,以及构造方法
但是 AVL 树还要再加一个平衡因子(Balance Factor)简写为 bf
还有一个双亲结点的引用(和平衡因子一样,插入的时候要用到)

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode parent;int bf; //平衡因子 右子树高度减去左子树高度public TreeNode(int val) {this.val = val;}
}

插入实现

首先完成结点的插入工作,这里的插入和之前我们在二叉搜索树已经学习过,这里就直接上代码,如果不了解的可以点开这个连接:JavaDS —— 二叉搜索树、哈希表、Map 与 Set

    public boolean insert(int val) {TreeNode node = new TreeNode(val);//如果根节点本身为空就直接赋值if(root == null) {root = node;return true;}TreeNode prev = null;TreeNode cur = root;//找到新结点的位置while(cur != null) {if(cur.val == val) {//相同的数据无法再次插入return false;} else if(cur.val < val) {prev = cur;cur = cur.right;} else {prev = cur;cur = cur.left;}}//插入结点if(prev.val > val) {prev.left = node;} else {prev.right = node;}node.parent = prev;}

现在就是调整平衡因子(这里我设定为右子树高度减左子树高度),如果你是插入到左子树的话,那平衡因子就要自减,如果是插入到右子树的话,那平衡因子就要自增。

首先就要先拿到 node 的位置,将cur 重置为 node

cur = node;
			//左子树-- 右子树++if(prev.left == cur) {prev.bf--;} else {prev.bf++;}

调节完平衡因子之后,此时调节过的平衡因子有五种情况:0 、1 、-1 、2 、-2

如下图所示:红色的结点为新插入的结点,灰色的结点则是已经存在的
在这里插入图片描述
在这里插入图片描述


如果调节过后,平衡因子依旧为 0 ,则说明该树本身就已经平衡了,不需要进行旋转调整.

如果调节过后的平衡因子为 1 或者 -1,说明该结点的兄弟结点为空,这个结点的插入可能会导致不平衡,需要我们继续向上调整平衡因子,这时候我们会使用 parent 引用,让prev 和 cur 一起向上移动,大家就会想到使用循环来调整平衡因子。

循环的部分代码如下:

        cur = node;//调整平衡因子与AVL树while(prev != null) {//左子树-- 右子树++if(prev.left == cur) {prev.bf--;} else {prev.bf++;}//检查是否需要旋转if(prev.bf == 0) {//平衡因子为0,说明树已经平衡,不用调整break;} else if(prev.bf == -1 || prev.bf == 1) {//如果出现 -1 或者 1 则说明树的平衡性已经被新结点影响到,需要继续调整cur = prev;prev = prev.parent;}}

如果调节过后的平衡因子为 2 或者 -2,说明该树出现不平衡,需要进行旋转调整

大家可以记一下旋转的口诀,旋转内容会在下面继续讲解:

左左型:右单旋
右右型:左单旋
左右型:左右双旋
右左型:右左双选

 		else {//此时怕平衡因子有两种情况2 或者 -2,需要旋转重新建立平衡树if(prev.bf == 2) {//说明右子树过高if(cur.bf == 1) {//右右型 左单旋rotateLeft(prev);} else if(cur.bf == -1) {//右左型 右左双旋rotateRL(prev);}} else {//此时 prev.bf == -2 说明左子树过高if(cur.bf == 1) {//左右型,左右双旋rotateLR(prev);} else if(cur.bf == -1) {//左左型, 右单旋rotateRight(prev);}}//旋转完成后,树已经平衡,直接退出循环break;}

经过旋转过后,树就会平衡,就无需继续调整平衡因子,直接跳出循环即可。

旋转实现

下面所有的实例图绿色的数字表示经过旋转后平衡因子变为多少

左单旋

当新插入的结点插在某个结点的右孩子的右子树时(这个简称为右右型),那么这个某个结点采用左单旋:

简单情况:
在这里插入图片描述
我们需要让 prev 成为 cur 的左孩子,这时候我们需要修改 prev 的 parent 引用, cur 的左孩子引用以及parent 引用,并且cur 结点的 parent 引用需要改成原来 prev 的parent引用(记为 pParent),所以我们事先就要保存好pParent,最后我们要将pParent 的左引用或者右引用 来连接cur (这里需要判断一下),最后的最后这两个结点的平衡因子置为 0

特殊情况:如果prev 本身就是 根节点的话,那么根节点的引用要变成 cur 的。

如果 cur 的左孩子本身就存在呢?
在这里插入图片描述
那么我们需要将 cur 左孩子结点先保存起来,让 prev.right = cur 的左孩子结点,并且左孩子结点的 parent 的引用要修改为 prev,所以这里引申出我们需要判断 cur 的左孩子结点存不存在,如果不存在则不需要修改其 parent 引用,避免发生空指针异常

    //左单旋private void rotateLeft(TreeNode prev) {TreeNode pParent = prev.parent;TreeNode cur = prev.right;TreeNode curL = cur.left;prev.right = curL;if(curL != null) {curL.parent = prev;}cur.left = prev;prev.parent = cur;cur.parent = pParent;if(prev == root) {root = cur;} else if(pParent.left == prev) {pParent.left = cur;} else {pParent.right = cur;}//调整平衡因子cur.bf = prev.bf = 0;}

右单旋

当新插入的结点插在某个结点的左孩子的左子树时(这个简称为左左型),那么这个某个结点采用右单旋:

简单情况:
在这里插入图片描述
这个和左单旋很相似,大家可以类比左单旋。

特殊情况:如果 prev 本身就是根节点的话就要修改根结点的引用。

还有,如果 cur 自身就有右孩子:让 prev.left = cur 的右孩子结点,并且判断右孩子结点是否为空,不为空的话将 parent 的引用要修改为 prev,
在这里插入图片描述

    //右单旋private void rotateRight(TreeNode prev) {TreeNode pParent = prev.parent;TreeNode cur = prev.left;TreeNode curR = cur.right;prev.left = curR;if(curR != null) {curR.parent = prev;}cur.right = prev;prev.parent = cur;cur.parent = pParent;if(prev == root) {root = cur;} else if(pParent.left == prev) {pParent.left = cur;} else {pParent.right = cur;}//调整平衡因子cur.bf = prev.bf = 0;}

左右双旋

当新插入的结点插在某个结点的左孩子的右子树时(这个简称为左右型),那么这个某个结点采用左右双旋:

简单情况:
在这里插入图片描述

左右双旋是指先进行左单旋,再进行右单旋,当然你也可以一步到位,我这里采用分步
所以左右双旋需要先对 cur 调用左单旋,再对 prev 调用右单旋

特殊情况:由于在单旋代码中我们已经处理好根节点和prev 的parent 结点了,但是这三个结点的平衡因子最后一定是 0 吗???
这次我们讨论的是如果是下面两种复杂的情况时,我们就需要修改一下某些结点的平衡因子:
在这里插入图片描述
在这里插入图片描述
进行完两个单旋转后,最后这三个结点的平衡因子都为0,但是看到上面的情况之后,其实并不是都为0,所以我们在进行旋转的时候就要先保存好cur 的右孩子的平衡因子,等到旋转结束后,就要调整平衡因子。

当 cur.right.bf = -1 时,prev.bf = 1;
当 cur.right.bf = 1 时,cur.bf = -1

    //左右双旋private void rotateLR(TreeNode prev) {TreeNode cur = prev.left;TreeNode curR = cur.right;int bf = curR.bf;rotateLeft(cur);rotateRight(prev);//调整平衡因子if(bf == 1) {cur.bf = -1;} else if(bf == -1) {prev.bf = 1;}//bf 为 0 的时候,不需要调整}

右左双旋

当新插入的结点插在某个结点的右孩子的左子树时(这个简称为右左型),那么这个某个结点采用右左双旋:

和左右双旋是类似的,这里就给出三种情况的图片给大家参考:
简单情况:
在这里插入图片描述
特殊情况:
当 cur.left.bf = -1 时,cur.bf = 1;
在这里插入图片描述


当 cur.left.bf = 1 时,prev.bf = -1;

在这里插入图片描述

    //右左双旋private void rotateRL(TreeNode prev) {TreeNode cur = prev.right;TreeNode curL = cur.left;int bf = curL.bf;rotateRight(cur);rotateLeft(prev);//调整平衡因子if(bf == 1) {prev.bf = -1;} else if(bf == -1) {cur.bf = 1;}//bf 为 0 的时候,不需要调整}

测试

写好AVL 树,记得测试自己的代码有没有错误,这里要测试两个东西,第一个是中序遍历的时候是否有序(检测是否为二叉搜索树),第二个东西就是平衡因子有没有错误以及是否是一个高度平衡的二叉树(因为都与高度有关,所以可以放在同一个方法里去写测试代码)。

最终代码

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode parent;int bf; //平衡因子 右子树高度减去左子树高度public TreeNode(int val) {this.val = val;}
}public class AVLTree {public TreeNode root;public boolean insert(int val) {TreeNode node = new TreeNode(val);//如果根节点本身为空就直接赋值if(root == null) {root = node;return true;}TreeNode prev = null;TreeNode cur = root;//找到新结点的位置while(cur != null) {if(cur.val == val) {//相同的数据无法再次插入return false;} else if(cur.val < val) {prev = cur;cur = cur.right;} else {prev = cur;cur = cur.left;}}//插入结点if(prev.val > val) {prev.left = node;} else {prev.right = node;}node.parent = prev;cur = node;//调整平衡因子与AVL树while(prev != null) {//左子树-- 右子树++if(prev.left == cur) {prev.bf--;} else {prev.bf++;}//检查是否需要旋转if(prev.bf == 0) {//平衡因子为0,说明树已经平衡,不用调整break;} else if(prev.bf == -1 || prev.bf == 1) {//如果出现 -1 或者 1 则说明树的平衡性已经被新结点影响到,需要继续调整cur = prev;prev = prev.parent;} else {//此时怕平衡因子有两种情况2 或者 -2,需要旋转重新建立平衡树if(prev.bf == 2) {//说明右子树过高if(cur.bf == 1) {//右右型 左单旋rotateLeft(prev);} else if(cur.bf == -1) {//右左型 右左双旋rotateRL(prev);}} else {//此时 prev.bf == -2 说明左子树过高if(cur.bf == 1) {//左右型,左右双旋rotateLR(prev);} else if(cur.bf == -1) {//左左型, 右单旋rotateRight(prev);}}//旋转完成后,树已经平衡,直接退出循环break;}}return true;}//左右双旋private void rotateLR(TreeNode prev) {TreeNode cur = prev.left;TreeNode curR = cur.right;int bf = curR.bf;rotateLeft(cur);rotateRight(prev);//调整平衡因子if(bf == 1) {cur.bf = -1;} else if(bf == -1) {prev.bf = 1;}//bf 为 0 的时候,不需要调整}//右左双旋private void rotateRL(TreeNode prev) {TreeNode cur = prev.right;TreeNode curL = cur.left;int bf = curL.bf;rotateRight(cur);rotateLeft(prev);//调整平衡因子if(bf == 1) {prev.bf = -1;} else if(bf == -1) {cur.bf = 1;}//bf 为 0 的时候,不需要调整}//右单旋private void rotateRight(TreeNode prev) {TreeNode pParent = prev.parent;TreeNode cur = prev.left;TreeNode curR = cur.right;prev.left = curR;if(curR != null) {curR.parent = prev;}cur.right = prev;prev.parent = cur;cur.parent = pParent;if(prev == root) {root = cur;} else if(pParent.left == prev) {pParent.left = cur;} else {pParent.right = cur;}//调整平衡因子cur.bf = prev.bf = 0;}//左单旋private void rotateLeft(TreeNode prev) {TreeNode pParent = prev.parent;TreeNode cur = prev.right;TreeNode curL = cur.left;prev.right = curL;if(curL != null) {curL.parent = prev;}cur.left = prev;prev.parent = cur;cur.parent = pParent;if(prev == root) {root = cur;} else if(pParent.left == prev) {pParent.left = cur;} else {pParent.right = cur;}//调整平衡因子cur.bf = prev.bf = 0;}
}

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

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

相关文章

关于Unity转微信小程序的流程记录

1.准备工作 1.unity微信小程序转换工具&#xff0c;minigame插件&#xff0c;导入后工具栏出现“微信小游戏" 2.微信开发者工具稳定版 3.MP微信公众平台申请微信小游戏&#xff0c;获得游戏appid 4.unity转webgl开发平台&#xff0c;Player Setting->Other Setting…

市场主流 AI 视频生成技术的迭代路径

AI视频生成技术的迭代路径经历了从GANVAE、Transformer、Diffusion Model到Sora采用的DiT架构&#xff08;TransformerDiffusion&#xff09;等多个阶段&#xff0c;每个阶段的技术升级都在视频处理质量上带来了飞跃性的提升。这些技术进步不仅推动了AI视频生成领域的快速发展&…

评估生成分子/对接分子的物理合理性工具 PoseBusters 评测

最近在一些分子生成或者对接模型中&#xff0c;出现了新的评估方法 PoseBusters&#xff0c;用于评估生成的分子或者对接的分子是否符合化学有效性和物理合理性。以往的分子生成&#xff0c;经常以生成分子的有效性、新颖性、化学空间分布&#xff0c;与口袋的结合力等方面进行…

微软蓝屏事件揭示的网络安全深层问题与未来应对策略

目录 微软蓝屏事件揭示的网络安全深层问题与未来应对策略 一、事件背景 二、事件影响 2.1、跨行业连锁反应 2.2、经济损失和社会混乱 三、揭示的网络安全问题 3.2、软件更新管理与风险评估 3.2、系统复杂性与依赖关系 3.3、网络安全意识与培训 四、未来的网络安全方向…

网络云相册实现--nodejs后端+vue3前端

目录 主页面 功能简介 系统简介 api 数据库表结构 代码目录 运行命令 主要代码 server apis.js encry.js mysql.js upload.js client3 index.js 完整代码 主页面 功能简介 多用户系统&#xff0c;用户可以在系统中注册、登录及管理自己的账号、相册及照片。 每…

众人帮蚂蚁帮任务平台修复版源码,含搭建教程。

全修复运营版本的任务平台&#xff0c;支持垂直领域细分&#xff0c;定向导流&#xff0c;带有排行榜功能&#xff0c;任务发布上传审核&#xff0c;用户信用等级&#xff0c;充值接口等等均完美可用。支付对接Z支付免签接口&#xff0c;环境配置及安装教程都已经打包。 搭建环…

C语言调试宏全面总结(六大板块)

C语言调试宏进阶篇&#xff1a;实用指南与案例解析C语言调试宏高级技巧与最佳实践C语言调试宏的深度探索与性能考量C语言调试宏在嵌入式系统中的应用与挑战C语言调试宏在多线程环境中的应用与策略C语言调试宏在并发编程中的高级应用 C语言调试宏进阶篇&#xff1a;实用指南与案…

【Linux】网络基础_4

文章目录 十、网络基础5. socket编程网络翻译服务 未完待续 十、网络基础 5. socket编程 网络翻译服务 基于UDP&#xff0c;我们实现一个简单的翻译。 我们导入之前写的代码&#xff1a; InetAddr.hpp&#xff1a; #pragma once#include <iostream> #include <sys…

开源智能低代码自动化助手:Obsei

**Obsei&#xff1a;**低代码&#xff0c;高效率&#xff0c;Obsei让AI自动化触手可及。- 精选真开源&#xff0c;释放新价值。 概览 Obsei是一款开源的低代码人工智能自动化工具&#xff0c;它为企业提供了一套灵活的解决方案&#xff0c;以应对日益增长的数据处理需求。该工…

uvm_config_db 和 uvm_resource_db :

uvm_config_db class my_driver extends uvm_driver;int my_param;function new(string name, uvm_component parent);super.new(name, parent);endfunctionvirtual task run_phase(uvm_phase phase);// 在组件内部获取配置值if (!uvm_config_db#(int)::get(this, ""…

[Git][远程操作]详细讲解

1.理解分布式版本控制系统 形象理解&#xff1a;每个⼈的电脑上都是⼀个完整的版本库 这样⼯作的时候&#xff0c;就不需要联⽹了&#xff0c; 因为版本库就在⾃⼰的电脑上 既然每个⼈电脑上都有⼀个完整的版本库&#xff0c;那多个⼈如何协作呢&#xff1f; 例如&#xff1a;…

ajax图书管理项目

bootstrap弹框 不离开当前页面&#xff0c;显示单独内容&#xff0c;让用户操作 功能&#xff1a;不离开当前页面&#xff0c;显示单独内容&#xff0c;供用户操作步骤&#xff1a; 1.引入bootstrap.css和bootstrap.js …

Stegdetect教程:如何用Stegdetect检测和破解JPG图像隐写信息

一、Stegdetect简介 Stegdetect 是一个开源工具&#xff0c;专门设计用于检测图像文件&#xff08;JPG格式&#xff09;中的隐写信息。Stegdetect 可以检测多种常见的隐写方法&#xff0c;比如 JSteg、JPHide 和 OutGuess 等。 二、使用Stegdetect检测图像隐写 官方描述&#…

NSS [SWPUCTF 2022 新生赛]file_master

NSS [SWPUCTF 2022 新生赛]file_master 开题&#xff0c;一眼文件上传。 network看看返回包。后端语言是PHP。 除了文件上传还有个查看文件功能。 起手式查询/etc/passwd&#xff0c;发现查询方法是GET提交参数&#xff0c;后端使用file_get_contents()函数包含文件。同时有op…

企业级业务架构设计探讨

引言 在数字化转型的浪潮中&#xff0c;企业业务架构的设计成为了连接企业战略与技术实现的桥梁&#xff0c;其重要性日益凸显。本文探讨企业级业务架构的设计原则、流程、工具和技术实现&#xff0c;并结合具体案例&#xff0c;为读者提供参考。 一、设计原则&#xff1a;奠…

KubeSphere 部署的 Kubernetes 集群使用 GlusterFS 存储实战入门

转载&#xff1a;KubeSphere 部署的 Kubernetes 集群使用 GlusterFS 存储实战入门 知识点 定级&#xff1a;入门级 GlusterFS 和 Heketi 简介 GlusterFS 安装部署 Heketi 安装部署 Kubernetes 命令行对接 GlusterFS 实战服务器配置(架构1:1复刻小规模生产环境&#xff0c;…

新手学习Gazebo+ros仿真控制小车-----易错和自己理解

赵虚左老师讲的很详细&#xff0c;这里只是理一下思路&#xff0c;说下突然出现“新”概念之间的关系。 urdf文件:里面是配置模型的&#xff0c;既有模型的位置、尺寸、颜色&#xff0c;也包含复杂的物理模型信息比如&#xff1a;转动惯量&#xff0c;碰撞box大小等等&#xff…

黑马Java零基础视频教程精华部分_11_面向对象进阶(3)_抽象类、接口、适配器

《黑马Java零基础视频教程精华部分》系列文章目录 黑马Java零基础视频教程精华部分_1_JDK、JRE、字面量、JAVA运算符 黑马Java零基础视频教程精华部分_2_顺序结构、分支结构、循环结构 黑马Java零基础视频教程精华部分_3_无限循环、跳转控制语句、数组、方法 黑马Java零基础视…

书生大模型基础岛-第二关:8G 显存玩转书生大模型 Demo

1.来源 https://github.com/InternLM/Tutorial/blob/camp3/docs/L1/Demo/task.md 2.过程 在 /root/share/pre_envs 中配置好了预置环境 icamp3_demo conda activate /root/share/pre_envs/icamp3_demo创建一个目录&#xff0c;用于存放我们的代码。并创建一个 cli_demo.py …

【hive】HiveSQL中两个json解析函数的使用json路径定位小工具

文章目录 1.HiveSQL中两个json解析函数1&#xff09;get_json_object2&#xff09;json_tuple 2.json中key所在层级路径定位小工具 关于json&#xff1a; https://blog.csdn.net/atwdy/article/details/124668815 1.HiveSQL中两个json解析函数 1&#xff09;get_json_object …