当前位置: 首页 > news >正文

数据结构篇:旋转操作在AVL树中的实现过程

本节课在线学习视频(网盘地址,保存后即可免费观看):

https://pan.quark.cn/s/06d5ed47e33b

AVL树是平衡二叉搜索树的一种,它通过旋转操作来保持树的平衡。AVL树的特点是,任何节点的两个子树的高度最大差别为1。本文将详细介绍AVL树中的旋转操作及其实现过程,并通过多个代码案例来说明这些操作的应用。

1. AVL树的基本概念

AVL树是一种自平衡二叉搜索树,其核心思想是通过旋转操作来维持树的平衡。旋转操作有四种:左旋、右旋、左右旋和右左旋。旋转操作的目的是调整树的结构,使其保持平衡,从而保证二叉搜索树的性能。

平衡因子

平衡因子是指某个节点的左子树高度减去右子树高度的值。AVL树的每个节点的平衡因子只能是-1、0或1。

2. 旋转操作

2.1 右旋(Right Rotation)

右旋是对某个节点进行的单次旋转,使得该节点的左子树成为其父节点。

案例1:右旋操作
class AVLNode {int val;int height;AVLNode left;AVLNode right;AVLNode(int val) {this.val = val;this.height = 1;}
}public class AVLTree {private int height(AVLNode node) {if (node == null) return 0;return node.height;}private AVLNode rightRotate(AVLNode y) {AVLNode x = y.left;AVLNode T2 = x.right;x.right = y;y.left = T2;y.height = Math.max(height(y.left), height(y.right)) + 1;x.height = Math.max(height(x.left), height(x.right)) + 1;return x;}public static void main(String[] args) {AVLTree tree = new AVLTree();AVLNode root = new AVLNode(30);root.left = new AVLNode(20);root.left.left = new AVLNode(10);root = tree.rightRotate(root);System.out.println("After right rotation, root is: " + root.val);}
}

在这个例子中,我们对根节点进行了右旋操作,使其左子树成为新的根节点。

2.2 左旋(Left Rotation)

左旋是对某个节点进行的单次旋转,使得该节点的右子树成为其父节点。

案例2:左旋操作
class AVLTree {// 同上private AVLNode leftRotate(AVLNode x) {AVLNode y = x.right;AVLNode T2 = y.left;y.left = x;x.right = T2;x.height = Math.max(height(x.left), height(x.right)) + 1;y.height = Math.max(height(y.left), height(y.right)) + 1;return y;}public static void main(String[] args) {AVLTree tree = new AVLTree();AVLNode root = new AVLNode(10);root.right = new AVLNode(20);root.right.right = new AVLNode(30);root = tree.leftRotate(root);System.out.println("After left rotation, root is: " + root.val);}
}

在这个例子中,我们对根节点进行了左旋操作,使其右子树成为新的根节点。

2.3 左右旋(Left-Right Rotation)

左右旋是对某个节点进行的两次旋转:先对其左子树进行左旋,再对该节点进行右旋。

案例3:左右旋操作
class AVLTree {// 同上private AVLNode leftRightRotate(AVLNode node) {node.left = leftRotate(node.left);return rightRotate(node);}public static void main(String[] args) {AVLTree tree = new AVLTree();AVLNode root = new AVLNode(30);root.left = new AVLNode(10);root.left.right = new AVLNode(20);root = tree.leftRightRotate(root);System.out.println("After left-right rotation, root is: " + root.val);}
}

在这个例子中,我们对根节点进行了左右旋操作,先对其左子树进行左旋,再对根节点进行右旋。

2.4 右左旋(Right-Left Rotation)

右左旋是对某个节点进行的两次旋转:先对其右子树进行右旋,再对该节点进行左旋。

案例4:右左旋操作
class AVLTree {// 同上private AVLNode rightLeftRotate(AVLNode node) {node.right = rightRotate(node.right);return leftRotate(node);}public static void main(String[] args) {AVLTree tree = new AVLTree();AVLNode root = new AVLNode(10);root.right = new AVLNode(30);root.right.left = new AVLNode(20);root = tree.rightLeftRotate(root);System.out.println("After right-left rotation, root is: " + root.val);}
}

在这个例子中,我们对根节点进行了右左旋操作,先对其右子树进行右旋,再对根节点进行左旋。

3. AVL树的插入操作

AVL树的插入操作需要在插入新节点后,检查节点的平衡因子,并根据平衡因子进行相应的旋转操作,以保持树的平衡。

案例5:AVL树的插入操作
public class AVLTree {// 同上private int balanceFactor(AVLNode node) {if (node == null) return 0;return height(node.left) - height(node.right);}public AVLNode insert(AVLNode node, int val) {if (node == null) return new AVLNode(val);if (val < node.val) node.left = insert(node.left, val);else if (val > node.val) node.right = insert(node.right, val);else return node;node.height = 1 + Math.max(height(node.left), height(node.right));int balance = balanceFactor(node);if (balance > 1 && val < node.left.val) return rightRotate(node);if (balance < -1 && val > node.right.val) return leftRotate(node);if (balance > 1 && val > node.left.val) {node.left = leftRotate(node.left);return rightRotate(node);}if (balance < -1 && val < node.right.val) {node.right = rightRotate(node.right);return leftRotate(node);}return node;}public static void main(String[] args) {AVLTree tree = new AVLTree();AVLNode root = null;int[] values = {10, 20, 30, 40, 50, 25};for (int val : values) {root = tree.insert(root, val);}System.out.println("AVL Tree constructed successfully.");}
}

在这个例子中,我们实现了AVL树的插入操作。每次插入新节点后,我们检查平衡因子,并通过旋转操作保持树的平衡。

4. 注意事项

  • 在进行旋转操作时,需要同时更新节点的高度和子树的高度。
  • 插入和删除操作可能会导致多个节点的平衡因子变化,需要从插入或删除位置向上逐层检查和调整。
  • 在实现AVL树时,确保所有旋转操作的逻辑正确,以避免树的不平衡或错误的结构。

结语

本文详细介绍了AVL树中的旋转操作及其实现过程,包括右旋、左旋、左右旋和右左旋。通过多个代码案例,我们展示了这些旋转操作的应用和效果。在实际开发中,AVL树通过旋转操作保持平衡,从而保证二叉搜索树的高效性能。希望这些示例和注意事项能帮助你更好地理解和应用AVL树中的旋转操作。

相关文章:

数据结构篇:旋转操作在AVL树中的实现过程

本节课在线学习视频&#xff08;网盘地址&#xff0c;保存后即可免费观看&#xff09;&#xff1a; https://pan.quark.cn/s/06d5ed47e33b AVL树是平衡二叉搜索树的一种&#xff0c;它通过旋转操作来保持树的平衡。AVL树的特点是&#xff0c;任何节点的两个子树的高度最大差别…...

为什么Java默认使用UTF-16,Golang默认使用UTF-8呢?

Java 和 Go 语言在默认字符编码上做出了不同的选择&#xff0c;这是由它们的设计目标和使用场景决定的。下面是对 Java 默认使用 UTF-16 和 Go 默认使用 UTF-8 的原因进行的详细解释。 Java 默认使用 UTF-16 的原因 1. 历史背景和兼容性 Unicode 的发展: Java 诞生于 1995 年…...

JavaScript常见面试题(三)

文章目录 1.对原型、原型链的理解2.原型修改、重写3.原型链指向4.对闭包的理解5. 对作用域、作用域链的理解6.对执行上下文的理解7.对this对象的理解8. call() 和 apply() 的区别&#xff1f;9.异步编程的实现方式&#xff1f;10.setTimeout、Promise、Async/Await 的区别11.对…...

【Effective Modern C++】第1章 型别推导

【Effective Modern C】第1章 型别推导 文章目录 【Effective Modern C】第1章 型别推导条款1&#xff1a;理解模板型别推导基础概念模板型别推导的三种情况情景一 ParamType 是一个指针或者引用&#xff0c;但非通用引用情景二 ParamType是一个通过引用情景三 ParamType既不是…...

服装连锁实体店bC一体化运营方案

一、引言 随着互联网的快速发展和消费者购物习惯的变化&#xff0c;传统服装连锁实体店在面对新的市场环境下亟需转型升级。BC&#xff08;Business to Consumer&#xff09;一体化运营方案的实施将成为提升服装连锁实体店竞争力和顾客体验的关键举掖。商淘云详细介绍服装连锁…...

IDEA中SpringMVC的运行环境问题

文章目录 一、IEAD 清理缓存二、用阿里云和spring创建 SpringMVC 项目中 pom.xml 文件的区别 一、IEAD 清理缓存 springMVC 运行时存在一些之前运行过的缓存导致项目不能运行&#xff0c;可以试试清理缓存 二、用阿里云和spring创建 SpringMVC 项目中 pom.xml 文件的区别 以下…...

Python初体验

# Java基础知识学的差不多了&#xff0c;项目上又没什么事&#xff0c;学学py&#xff0c;方便以后对接 1、打包flask应用&#xff08;好痛苦&#xff0c;在什么平台打包就只在那个平台可用想在linux用只能参考方法2了&#xff09; pyinstaller --onefile app.py -n myapp 2…...

从零开始如何学习人工智能?

说说我自己的情况&#xff1a;我接触AI的时候&#xff0c;是在研一。那个时候AlphaGo战胜围棋世界冠军李世石是大新闻&#xff0c;人工智能第一次出现我面前&#xff0c;当时就想搞清楚背后的原理以及这些技术有什么作用。 就开始找资料&#xff0c;看视频。随着了解的深入&am…...

【仿真建模-anylogic】动态生成ConveyorCustomStation

Author&#xff1a;赵志乾 Date&#xff1a;2024-06-18 Declaration&#xff1a;All Right Reserved&#xff01;&#xff01;&#xff01; 0. 背景 直接使用Anylogic组件开发的模型无法动态改变运输网布局&#xff1b;目前需求是要将运输网布局配置化&#xff1b;运输网配置化…...

如何使用idea连接Oracle数据库?

idea版本&#xff1a;2021.3.3 Oracle版本&#xff1a;10.2.0.1.0&#xff08;在虚拟机Windows sever 2003 远程连接数据库&#xff09; 数据库管理系统&#xff1a;PLSQL Developer 在idea里面找到database&#xff0c;在idea侧面 选择左上角加号&#xff0c;新建&#xff…...

谈谈kafaka的并行处理,顺带讲讲rabbitmq

简介 Kafka 是一个分布式流处理平台,它支持高效的并行处理。Kafka 的并行处理能力主要体现在以下几个方面: 分区(Partition)并行 Kafka 将数据存储在称为"分区"的逻辑单元中。每个分区可以独立地并行地进行读写操作。生产者可以根据分区策略,将数据写入到指定的分…...

P3056 [USACO12NOV] Clumsy Cows S

[USACO12NOV] Clumsy Cows S 题目描述 Bessie the cow is trying to type a balanced string of parentheses into her new laptop, but she is sufficiently clumsy (due to her large hooves) that she keeps mis-typing characters. Please help her by computing the min…...

智赢选品,OZON数据分析选品利器丨萌啦OZON数据

在电商行业的激烈竞争中&#xff0c;如何快速准确地把握市场动态、洞察消费者需求、实现精准选品&#xff0c;是每个电商卖家都面临的挑战。而在这个数据驱动的时代&#xff0c;一款强大的数据分析工具无疑是电商卖家们的得力助手。今天&#xff0c;我们就来聊聊这样一款选品利…...

Canal自定义客户端

一、背景 在Canal推送数据变更信息至MQ&#xff08;消息队列&#xff09;时&#xff0c;我们遇到了特定问题&#xff0c;尤其是当消息体的大小超过了MQ所允许的最大限制。这种限制导致数据推送过程受阻&#xff0c;需要相应的调整或处理。 二、解决方法 采用Canal自定义客户…...

20240621将需要自启动的部分放到RK3588平台的Buildroot系统的rcS文件中

20240621将需要自启动的部分放到RK3588平台的Buildroot系统的rcS文件中 2024/6/21 17:15 开发板&#xff1a;飞凌OK3588-C SDK&#xff1a;Rockchip原厂的Buildroot 缘起&#xff1a;在凌OK3588-C的LINUX R4系统启动的时候&#xff0c;需要拉高GPIO4_B5、GPIO3_B7和GPIO3_D0。…...

掌握数据魔方:Xinstall引领ASA全链路数据归因新纪元

一、引言 在数字化时代&#xff0c;数据是App推广和运营的核心驱动力。然而&#xff0c;如何准确获取、分析并应用这些数据&#xff0c;却成为了许多开发者和营销人员面临的痛点。Xinstall作为一款专业的App全渠道统计服务商&#xff0c;致力于提供精准、高效的数据解决方案&a…...

IIS代理配置-反向代理

前后端分离项目&#xff0c;前端在开发中使用proxy代理解决跨域问题&#xff0c;打包之后无效。 未配置前无法访问 部署环境为windows IIS&#xff0c;要在iis设置反向代理 安装代理模块 需要在iis中实现代理&#xff0c;需要安装Application Request Routing Cache和URL重…...

Flutter调用本地web

前言: 在目前Flutter 环境中&#xff0c;使用在线 webview 是一种很常见的行为 而在 app 环境中&#xff0c;离线使用则更有必要 1.环境准备 将依赖导入 2.引入前端代码 前端代码有两种情况 一种是使用打包工具 build 而来的前端代码 另一种情况是直接使用 HTML 文件 …...

AI大模型部署Ubuntu服务器攻略

一、下载Ollama 在线安装&#xff1a; 在linux中输入命令curl -fsSL https://ollama.com/install.sh | sh 由于在linux下载ollama需要经过外网&#xff0c;网络会不稳定&#xff0c;很容易造成连接超时的问题。 离线安装&#xff1a; 步骤一&#xff1a; 下载Ollama离线版本…...

vlan、vxlan、vpc学习

文章目录 前言VLAN (Virtual Local Area Network)定义工作原理优点应用场景限制 VXLAN (Virtual eXtensible Local Area Network)工作原理优点应用场景与VLAN的区别 VPC (Virtual Private Cloud)定义特点优势应用场景与VLAN/VXLAN的关联 总结 前言 VLAN&#xff08;Virtual Lo…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...