每日学习一个数据结构-AVL树
文章目录
- 概述
- 一、定义与特性
- 二、平衡因子
- 三、基本操作
- 四、旋转操作
- 五、应用场景
- Java代码实现
概述
AVL树是一种自平衡的二叉查找树,由两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明。想了解树的相关概念,请点击这里。以下是对AVL树的详细说明:
一、定义与特性
- 定义:AVL树是一种二叉查找树,其中每个节点的左右子树的高度差的绝对值(即平衡因子)不超过1。
- 特性:
- 左右子树都是AVL树。
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1、0、1)。
- 任意节点的左右子树的高度差不会超过1,这保证了树的高度相对较低,从而提高了搜索、插入和删除操作的效率。
二、平衡因子
平衡因子(Balance Factor,BF)是AVL树中的一个重要概念,用于衡量节点的左右子树的高度差。平衡因子的值只能是-1、0或1。具体计算方式为:节点的右子树高度减去左子树高度。
三、基本操作
AVL树的基本操作包括插入、删除和查找,这些操作都需要在保持树平衡的前提下进行。
-
插入:
- 按照二叉查找树的方式插入新节点。
- 插入后,从插入点向上回溯,更新每个节点的平衡因子。
- 如果发现某个节点的平衡因子绝对值超过1,则进行旋转操作以恢复平衡。
-
删除:
- 找到要删除的节点,并将其向下旋转成一个叶子节点。
- 直接删除该叶子节点。
- 从删除点向上回溯,更新每个节点的平衡因子。
- 如果发现某个节点的平衡因子绝对值超过1,则进行旋转操作以恢复平衡。
-
查找:
- 在AVL树中查找元素的过程与在二叉查找树中相同。
- 由于AVL树总是保持平衡的,所以查找操作的时间复杂度为O(log n)。
四、旋转操作
旋转操作是AVL树保持平衡的关键。根据节点插入或删除后不平衡的具体情况,AVL树的旋转可以分为四种类型:
- 单向右旋(LL):当在节点的左子树的左子树上插入新节点导致节点不平衡(平衡因子为2)时,进行右旋转操作。
- 单向左旋(RR):当在节点的右子树的右子树上插入新节点导致节点不平衡(平衡因子为-2)时,进行左旋转操作。
- 双向旋转(先左后右,LR):当在节点的左子树的右子树上插入新节点导致节点不平衡(平衡因子为2)时,先进行左旋转再进行右旋转。
- 双向旋转(先右后左,RL):当在节点的右子树的左子树上插入新节点导致节点不平衡(平衡因子为-2)时,先进行右旋转再进行左旋转。
五、应用场景
AVL树适用于插入删除次数较少但查找频繁的场景。例如,Windows进程地址空间管理就采用了AVL树来实现高效的查找操作。然而,由于AVL树在插入和删除操作后需要进行复杂的旋转操作来保持平衡,所以其性能在插入和删除操作频繁的场景下可能不如其他数据结构(如红黑树)。
综上所述,AVL树是一种高效的自平衡二叉查找树,通过引入平衡因子和旋转操作来保持树的平衡性,从而提高了搜索、插入和删除操作的效率。
Java代码实现
下面是一个简单的AVL树在Java中的实现。这个实现包括了插入、删除和查找操作,以及必要的旋转操作来维持树的平衡。
class AVLTree {private class Node {int key, height;Node left, right;Node(int d) {key = d;height = 1;}}private Node root;// Utility function to get the height of the treeint height(Node N) {if (N == null)return 0;return N.height;}// Utility function to get the maximum of two integersint max(int a, int b) {return (a > b) ? a : b;}// Right rotate subtree rooted with yNode rightRotate(Node y) {Node x = y.left;Node T2 = x.right;// Perform rotationx.right = y;y.left = T2;// Update heightsy.height = max(height(y.left), height(y.right)) + 1;x.height = max(height(x.left), height(x.right)) + 1;// Return new rootreturn x;}// Left rotate subtree rooted with xNode leftRotate(Node x) {Node y = x.right;Node T2 = y.left;// Perform rotationy.left = x;x.right = T2;// Update heightsx.height = max(height(x.left), height(x.right)) + 1;y.height = max(height(y.left), height(y.right)) + 1;// Return new rootreturn y;}// Get Balance factor of node Nint getBalance(Node N) {if (N == null)return 0;return height(N.left) - height(N.right);}// Insert a node with given key in the subtree rooted with node and returns the new root of the subtreeNode insert(Node node, int key) {// Perform the normal BST insertionif (node == null)return (new Node(key));if (key < node.key)node.left = insert(node.left, key);else if (key > node.key)node.right = insert(node.right, key);else // Duplicate keys are not allowed in BSTreturn node;// Update height of this ancestor nodenode.height = 1 + max(height(node.left), height(node.right));// Get the balance factor of this ancestor node to check whether this node became unbalancedint balance = getBalance(node);// If this node becomes unbalanced, then there are 4 cases// Left Left Caseif (balance > 1 && key < node.left.key)return rightRotate(node);// Right Right Caseif (balance < -1 && key > node.right.key)return leftRotate(node);// Left Right Caseif (balance > 1 && key > node.left.key) {node.left = leftRotate(node.left);return rightRotate(node);}// Right Left Caseif (balance < -1 && key < node.right.key) {node.right = rightRotate(node.right);return leftRotate(node);}// Return the (unchanged) node pointerreturn node;}// Delete a node with given key in the subtree rooted with node and returns the new root of the subtreeNode deleteNode(Node root, int key) {// Perform standard BST deleteif (root == null)return root;if (key < root.key)root.left = deleteNode(root.left, key);else if (key > root.key)root.right = deleteNode(root.right, key);else {// node with only one child or no childif ((root.left == null) || (root.right == null)) {Node temp = null;if (temp == root.left)temp = root.right;elsetemp = root.left;// No child caseif (temp == null) {temp = root;root = null;} else // One child caseroot = temp; // Copy the contents of the non-empty child} else {// node with two children: Get the inorder successor (smallest in the right subtree)Node temp = minValueNode(root.right);// Copy the inorder successor's data to this noderoot.key = temp.key;// Delete the inorder successorroot.right = deleteNode(root.right, temp.key);}}// If the tree had only one node then returnif (root == null)return root;// Update height of the current noderoot.height = max(height(root.left), height(root.right)) + 1;// Get the balance factor of this node (to check whether this node became unbalanced)int balance = getBalance(root);// If this node becomes unbalanced, then there are 4 cases// Left Left Caseif (balance > 1 && getBalance(root.left) >= 0)return rightRotate(root);// Left Right Caseif (balance > 1 && getBalance(root.left) < 0) {root.left = leftRotate(root.left);return rightRotate(root);}// Right Right Caseif (balance < -1 && getBalance(root.right) <= 0)return leftRotate(root);// Right Left Caseif (balance < -1 && getBalance(root.right) > 0) {root.right = rightRotate(root.right);return leftRotate(root);}return root;}Node minValueNode(Node node) {Node current = node;// Loop down to find the leftmost leafwhile (current.left != null)current = current.left;return current;}// A utility function to do inorder traversal of BSTvoid inorder(Node root) {if (root != null) {inorder(root.left);System.out.print(root.key + " ");inorder(root.right);}}// Main functionpublic static void main(String[] args) {AVLTree tree = new AVLTree();/* Constructing tree given in the above figure */tree.root = tree.insert(tree.root, 10);tree.root = tree.insert(tree.root, 20);tree.root = tree.insert(tree.root, 30);tree.root = tree.insert(tree.root, 40);tree.root = tree.insert(tree.root, 50);tree.root = tree.insert(tree.root, 25);/* The constructed AVL Tree would be30/ \20 40/ \ \10 25 50*/System.out.println("Inorder traversal of the constructed AVL tree is:");tree.inorder(tree.root);System.out.println("\n\nDelete 20");tree.root = tree.deleteNode(tree.root, 20);System.out.println("Inorder traversal of the modified tree is:");tree.inorder(tree.root);System.out.println("\n\nDelete 30");tree.root = tree.deleteNode(tree.root, 30);System.out.println("Inorder traversal of the modified tree is:");tree.inorder(tree.root);System.out.println("\n\nDelete 50");tree.root = tree.deleteNode(tree.root, 50);System.out.println("Inorder traversal of the modified tree is:");tree.inorder(tree
相关文章:
每日学习一个数据结构-AVL树
文章目录 概述一、定义与特性二、平衡因子三、基本操作四、旋转操作五、应用场景 Java代码实现 概述 AVL树是一种自平衡的二叉查找树,由两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明。想了解树的相关概念,请点击这里。以下是对AVL树的…...

课堂点名系统小程序的设计
管理员账户功能包括:系统首页,个人中心,管理员管理,论坛信息管理,基础数据管理,课程信息管理,课程考勤管理,轮播图信息 微信端账号功能包括:系统首页,论坛信…...

使用Python查找WeChat和QQ的安装路径和文档路径
在日常工作和生活中,我们经常需要查找某些应用程序的安装位置或者它们存储文件的位置。特别是对于像WeChat(微信)和QQ这样的即时通讯软件,了解它们的文件存储位置可以帮助我们更好地管理我们的聊天记录和共享文件。今天࿰…...

【AI大模型】深入Transformer架构:编码器部分的实现与解析(下)
目录 🍔 编码器介绍 🍔 前馈全连接层 2.1 前馈全连接层 2.2 前馈全连接层的代码分析 2.3 前馈全连接层总结 🍔 规范化层 3.1 规范化层的作用 3.2 规范化层的代码实现 3.3 规范化层总结 🍔 子层连接结构 4.1 子层连接结…...
【数据结构】【栈】算法汇总
一、顺序栈的操作 1.准备工作 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{SElemType*base;SElemType*top;int stacksize; }SqStack; 2.栈的初始化 Status InitStack(SqStack &S){S.base(SElemType*)malloc(MAXSIZE*sizeof(SElemType));if(…...

如何训练自己的大模型,答案就在这里。
训练自己的AI大模型是一个复杂且资源密集型的任务,涉及多个详细步骤、数据集需求以及计算资源要求。以下是根据搜索结果提供的概述: 详细步骤 \1. 设定目标: - 首先需要明确模型的应用场景和目标,比如是进行分类、回归、生成文本…...
React18新特性
React 18新特性详解如下: 并发渲染(Concurrent Rendering): React 18引入了并发渲染特性,允许React在等待异步操作(如数据获取)时暂停和恢复渲染,从而提供更平滑的用户体验。 通过时…...
汽车发动机系统EMS详细解析
汽车发动机系统EMS,全称Engine-Management-System(发动机管理系统),是现代汽车电子控制技术的重要组成部分。以下是对汽车发动机系统EMS的详细解析,涵盖其定义、工作原理、主要组成、功能特点、技术发展以及市场应用等…...

【社保通-注册安全分析报告-滑动验证加载不正常导致安全隐患】
前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 暴力破解密码,造成用户信息泄露短信盗刷的安全问题,影响业务及导致用户投诉带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞…...

初学Vue(2)
文章目录 监视属性 watch深度监视computed 和 watch 之间的区别 绑定样式(class style)条件渲染列表渲染基本列表key的原理列表过滤列表排序收集表单中的数据 v-model过滤器(Vue3已移除) 监视属性 watch 当被监视的属性变化时&am…...
ThinkPHP5基础入门
文章目录 ThinkPHP5基础入门一、引言二、环境搭建1、前期准备2、目录结构 三、快速上手1、创建模块2、编写控制器3、编写视图4、编写模型 四、调试与部署1、调试模式2、关闭调试模式3、隐藏入口文件 五、总结 ThinkPHP5基础入门 一、引言 ThinkPHP5 是一个基于 MVC 和面向对象…...
Metal 之旅之MTLLibrary
什么是MSL? MSL是Metal Shading Language 的简称,为了更好的在GPU执行程序,苹果公司定义了一套类C的语言(Metal Shading Language ),在GPU运行的程序都是用这个语言来编写的。 什么是MTLLibrary? .metal后缀的文件…...
第十二章 Redis短信登录实战(基于Session)
目录 一、User类 二、ThreadLocal类 三、用户业务逻辑接口 四、用户业务逻辑接口实现类 五、用户控制层 六、用户登录拦截器 七、拦截器配置类 八、隐藏敏感信息的代码调整 完整的项目资源共享地址,当中包含了代码、资源文件以及Nginx(Wi…...

华为OD机试 - 九宫格游戏(Python/JS/C/C++ 2024 E卷 100分)
华为OD机试 2024E卷题库疯狂收录中,刷题点这里 专栏导读 本专栏收录于《华为OD机试真题(Python/JS/C/C)》。 刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,…...
Pytorch库中torch.normal()详解
torch.normal()用法 torch.normal()函数,用于生成符合正态分布(高斯分布)的随机数。在 PyTorch 中,这个函数通常用于生成 Tensor。 该函数共有四个方法: overload def normal(mean: Tensor, std: Tensor, *, generat…...

atcoder-374(a-e)
atcoder-374 文章目录 atcoder-374ABC简洁的写法正解 D正解 E A #include<bits/stdc.h>using namespace std;signed main() {string s;cin>>s;string strs.substr(s.size()-3);if(str "san") puts("Yes");else puts("No");return 0…...

idea2024设置中文
今天下载idea2024.2版本,发现已经装过中文插件,但是还是不显示中文,找了半天原来还需要设置中文选项 方案一 点击文件 -> 关闭项目 点击自定义 -> 选择语言 方案二 点击文件 -> 设置 外观与行为 -> 系统设置 -> 语言和地区…...
跨境电商独立站轮询收款问题
想必做跨境电商独立站的小伙伴,对于PayPal是再熟悉不过了,PayPal是一个跨国际贸易的支付平台,对于做独立站的朋友来说跨境收款绝大部分都是依赖PayPal以及Stripe条纹了。简单来说PayPal跟国内的支付宝有点类似,但是PayPal它是跨国…...
[OS] 3.Insert and Remove Kernel Module
Insert and Remove Kernel Module 1. 切换到 root 账户 $ sudo su作用:Linux 内核模块的加载和卸载需要超级用户权限,因此你必须以 root 用户身份进行操作。sudo su 命令允许你从普通用户切换到 root 账户,从而获得系统的最高权限ÿ…...
updatedb命令:更新locate数据库
一、命令简介 updatedb 命令用于更新 locate 命令使用的文件数据库,以便 locate 命令能够快速定位文件。 二、命令参数 命令格式 updatedb [选项]选项 -l: 仅更新本地文件系统(默认行为)-U: 更新所有文件系统-o D…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...

什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...

04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...

自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...