AVL树的介绍与学习
目录
1.前言
2.AVL树
3.AVL树的插入
平衡因子的更新
更新停止的条件
旋转
1.前言
在学习了二叉搜索树,set和map之后,我们接下来趁热打铁,继续学习AVL树。
2.AVL树
1.AVL树具有二叉搜索树的性质,但是它的左右子树的高度差不超过1.是一颗高度平衡的二叉搜索树。
2.AVL树中我们引入了平衡因子概念,它的大小等于右子树的高度减去左子树的高度,在AVL树中,任何节点的平衡因子只能为1,-1,0,不是这个值说明这颗树就该调整了,他就像一个风向标一样,告诉我们这颗树是否平衡。
3.思考一下,为什么AVL树的高度差不可以只为0呢?试想一下,如果这颗树只有2个节点,它无论如何根节点的平衡因子都达不到0.
4.AVL树是高度平衡的二叉搜索树,它的搜索效率可以稳定控制在logN,对比二叉搜索树在特殊情况下的N方,有了质的提升。
3.AVL树的插入
1.他按照二叉搜索树的插入规则进行插入。
2.新增节点以后,只会影响祖先节点的平衡因子,所以需要更新祖先的平衡因子。
3.平衡因子未出问题,则插入结束,如果超出了1,-1,0的范围,就需要旋转来平衡树。
平衡因子的更新
1.平衡因子=左子树-右子树。
2.子树高度变化才会影响平衡因子。
3.插入右节点,平衡因子++,插入左节点,平衡因子--。
4.parent所在子树高度是否变化决定了是否向上更新。
更新停止的条件
1.更新后parent平衡因子为0,说明是由1或者-1变化而来。高度不变,平衡因子结束更新。雪中送炭。
2.更新后平衡因子为1或-1,说明原来是0,插入一个节点变为该值,影响了树的高度,需要向上更新。
3.更新后平衡因子为-2或2,更新前parent的平衡因子是1或-1,在高的一侧又再次插入节点变为2或-2,需要旋转处理。
4.不断更新,更新到根,根的平衡因子为0或-1停止了。
旋转
旋转的原则:1.保持搜索树的规则。2.让旋转的树从不满足变平衡,降低树的高度。
旋转由左旋,右旋,左右旋,右左旋。
由于内容比较多我们先介绍这么多,代码实现和旋转代码等下一篇博客再介绍。
相关文章:
AVL树的介绍与学习
目录 1.前言 2.AVL树 3.AVL树的插入 平衡因子的更新 更新停止的条件 旋转 1.前言 在学习了二叉搜索树,set和map之后,我们接下来趁热打铁,继续学习AVL树。 2.AVL树 1.AVL树具有二叉搜索树的性质,但是它的左右子树的高度差不…...
docker部署Mysql8一直密码错误记录
正常流程是这样得: 第一步 #拉镜像 docker pull mysql:8.0 第二步 #运行名为 mysql8 得容器 ,MYSQL_ROOT_PASSWORD123456 设置密码 docker run -p 3307:3306 \ --name mysql8 \ -e MYSQL_ROOT_PASSWORD123456 \ -v /docker/mysql8/data:/var/lib/m…...
智慧水库与AI深度融合的实现方案及典型应用场景
以下是智慧水库与AI深度融合的实现方案及典型应用场景,结合行业前沿案例与技术架构展开: 一、智慧水库AI实现方案 1. 技术架构与核心工具 感知层: 多模态传感器网络:部署毫米波雷达水位计(精度3mm)、光纤光栅渗压计(分辨率0.01%FS)、高清智能球机(支持800万像素+AI分…...
大语言模型架构基础与挑战
大语言模型(Large Language Model, LLM)在近几年引领了自然语言处理领域的革命性进展。这类模型通常拥有极其庞大的参数规模(往往达到数十亿乃至数千亿级别),通过对海量文本数据进行自监督训练,展现出卓越的语言理解和生成能力。自2018年前后第一批大语言模型问世以来,基…...
KAG:通过知识增强生成提升专业领域的大型语言模型(二)
目录 摘要 Abstract 1 实验 1.1 实验设置 1.2 总体结果 1.3 消融研究 1.3.1 知识图谱索引消融 1.3.2 推理与检索消融 1.3.3 实验结果与讨论 2 KAG服务部署 2.1 安装Docker 2.2 安装Doker Compose 2.3 启动服务 2.4 查看状态 2.5 产品访问 3 KAG 0.6使用&#x…...
【Luogu】动态规划六
P1586 四方定理 - 洛谷 思路: 这题其实就是完全背包问题,但是有限制,最多数量只能是 4 所以我们可以定义 dp[i][j] 为 i 用 j 个数拼凑的总方案数 那么转移方程也很明显了,dp[i][j] dp[i - k*k][j - 1] 具体的,我…...
Postman接口测试: postman设置接口关联,实现参数化
🍅 点击文末小卡片,免费获取软件测试全套资料,资料在手,涨薪更快 postman设置接口关联 在实际的接口测试中,后一个接口经常需要用到前一个接口返回的结果, 从而让后一个接口能正常执行,这个…...
docker打开滚动日志
在 Docker 中启用滚动日志(log rotation)可以帮助你管理容器日志的大小,避免日志文件占用过多磁盘空间。以下是具体的操作步骤: 1. 修改 Docker 守护进程配置 Docker 的日志配置是通过 daemon.json 文件管理的。你需要修改此文件…...
单片机-89C51部分:5、点亮LED
飞书文档https://x509p6c8to.feishu.cn/wiki/SlB5wYD1QiPRzWkfijEcIvv8nyc 一、应用场景 二、点灯原理 插件led灯珠长引脚为正极,短引脚为负极。 LED(发光二极管)两端存在电压差,有一定的电流流过时会亮起。电流可以理解为水流,…...
Lua 第10部分 模式匹配
10.1 模式匹配的相关函数 字符串标准库提供了基于模式的 4 个函数。 我们已经初步了解过函数 find 和 gsub,其余两个函数分别是 match 和 gmatch (Global Match 的缩写)。 函数 string.find 用于在指定的目标字符串中搜索指定的模式。最简单的模式就是一…...
Maven 4.0.0 模式-pom.xml配置详解
Maven 4.0.0 模式-pom.xml配置详解 此 pom.xml 文件涵盖了 Maven 4.0.0 模式支持的所有主要标签,包括项目元数据、依赖管理、构建配置、发布管理等。每个标签都配有详细注释,说明其作用、常见用法和可能的值。 此文件旨在展示标签的完整性&#…...
IDEA 连接 Oracle 数据库
IDEA 连接 Oracle 数据库...
机器人快速启动
机器人快速启动 ES机器人开机操作流程 方法一(一体化底座启动) 接通48V电源点击底座“Power”按钮观察电源指示灯亮起,蜂鸣器发出“嘀”声,代表底座启动完成 方法二(控制手柄启动) 长按手柄开关机键2秒后松…...
使用 MediaPipe 和 OpenCV 快速生成人脸掩膜(Face Mask)
在实际项目中,尤其是涉及人脸识别、换脸、图像修复等任务时,我们经常需要生成人脸区域的掩膜(mask)。这篇文章分享一个简单易用的小工具,利用 MediaPipe 和 OpenCV,快速提取人脸轮廓并生成二值掩膜图像。 …...
《全球反空间能力》报告翻译——部分1
全球反空间能力 已进行过破坏性反卫星测试的国家 美国 美国目前拥有世界上最先进的军事太空能力,尽管与中国的相对差距正在缩小。在冷战期间,美国开创了许多现今使用的国家安全太空应用,并在几乎所有类别中保持技术领先地位。美国军方在将…...
云原生课程-Docker
一次镜像,到处运行。 1. Docker详解: 1.1 Docker简介: Docker是一个开源的容器化平台,可以帮助开发者将应用程序和其依赖的环境打包成一个可移植的,可部署的容器。 docker daemon:是一个运行在宿主机(DO…...
组件的基本知识
组件 组件的基本知识 组件概念组成步骤好处全局注册生命周期scoped原理 父子通信步骤子传父 概念 就是将要复用的标签,抽离放在一个独立的vue文件中,以供主vue文件使用 组成 三部分构成 template:HTML 结构 script: JS 逻辑 style: CSS 样…...
空间矩阵的思考
今天又看了些线性代数,引发了许多思考。 矩阵是以长和宽存储数据,那有没有一种新型的矩阵,以长宽高的形式存储数据呢?我不知道有没有,所以暂且称其为空间矩阵。 它肯定是存在的,可以这样抽象&#…...
【数据挖掘】时间序列预测-常用序列预测模型
常用序列预测模型 (1)AR(自回归)模型(2)ARIMA模型(3)Prophet模型(4)LSTM模型(5)Transformer模型(6)模型评估6.…...
将你的本地项目发布到 GitHub (新手指南)
目录 第 1 步:在 GitHub 上创建新的仓库 (Repository)第 2 步:将本地仓库连接到 GitHub 远程仓库第 3 步:(可能需要) 重命名你的默认分支第 4 步:将本地代码推送到 GitHub第 5 步:在 GitHub 上检查结果后续工作流程 你…...
[论文梳理] 足式机器人规划控制流程 - 接触碰撞的控制 - 模型误差 - 自动驾驶车的安全合规(4个课堂讨论问题)
目录 问题 1:足式机器人运动规划 & 控制的典型流程 (pipline) 1.1 问题 1.2 目标 1.3 典型流程(Pipeline) 1.3.1 环境感知(Perception) 1.3.2 高层规划(High-Level Planning) 1.3.3 …...
初中级前端面试全攻略:自我介绍模板、项目讲解套路与常见问答
为了给面试官留下专业而亲切的第一印象,自我介绍要突出与岗位相关的技能和项目经验,同时以自己擅长的领域开放式结尾。通常可以按照以下思路组织自我介绍内容:首先简单介绍个人信息和工作年限,然后列出精通的前端技术栈…...
Android开发中svg转xml工具使用
要使用 svg2vector-cli 工具通过命令行将 SVG 文件转换为 Android 可用的 XML 矢量图标文件,可以单个文件转换或者整个文件夹批量转换,以下是详细的步骤和说明: 1. 准备工作 1.1 下载工具 首先需要下载 svg2vector-cli-1.0.0.jar 或更高版本…...
爬虫技术入门:基本原理、数据抓取与动态页面处理
引言 在当今数据驱动的时代,网络爬虫技术已成为获取和分析互联网数据的重要手段。无论是搜索引擎的网页收录、竞品数据分析,还是学术研究的语料收集,爬虫技术都发挥着关键作用。本文将深入浅出地讲解爬虫的基本原理,分析它能获取…...
AI预测3D新模型百十个定位预测+胆码预测+去和尾2025年4月27日第65弹
从今天开始,咱们还是暂时基于旧的模型进行预测,好了,废话不多说,按照老办法,重点8-9码定位,配合三胆下1或下2,杀1-2个和尾,再杀6-8个和值,可以做到100-300注左右。 (1)定…...
服务器数据备份,服务器怎么备份数据呢?
企业数据量呈指数级增长,服务器数据备份已成为保障业务连续性、抵御勒索攻击与合规审查的核心技术环节。当前,服务器数据备份方案需兼顾数据完整性、恢复时效性、存储经济性三大核心诉求,其实现路径可根据技术架构、数据规模及容灾等级划分为…...
语音识别质量的跟踪
背景 这个项目是用来生成结构化的电子病历的。数据的来源是医生的录音。中间有一大堆的处理,语音识别,关键字匹配,结构化处理,病历编辑......。最多的时候给上百家医院服务。 语音识别质量的跟踪 一、0225医院的训练后的情况分…...
【数据挖掘】时间序列预测-时间序列的平稳性
时间序列的平稳性 (1)平稳性定义(2)平稳性处理方法2.1 差分法2.2 季节调整(Seasonal Adjustment)2.3 趋势移除(Detrending)2.4 对数转换(Logarithmic Transformation&…...
成都蒲江石象湖旅游攻略之石象湖郁金香最佳观赏时间
石象湖坐落于成都蒲江,拥有绝美的郁金香花海,吸引了很多的游客。如果大家想要观赏比较诱惑人的郁金香,那自然就应该知道正确的观赏时间。 心想郁金香合适的时间是每年的3月份到3月底。石象湖会还会举办盛大的郁金香节,在花园内有数…...
大模型、知识图谱和强化学习三者的结合,可以形成哪些研究方向?
大模型(Large Language Models, LLMs)、知识图谱(Knowledge Graph, KG)与强化学习(Reinforcement Learning, RL)作为人工智能领域的三大核心技术,其融合正推动着认知智能迈向新高度。本文结合2023-2025年的最新研究成果,系统梳理三者结合的七大科研方向及其技术路径。 …...
Linux文件操作
在C语言中,我们已经学习了文件相关的知识,那么在Linux中我们为什么还要再来学习文件呢?这是因为C语言中和Linux中,"文件"是2个不同的概念。所以我们要来学习Linux中对文件的操作。 在学习之前,我们先来回顾一…...
PostSwigger Web 安全学习:CSRF漏洞3
CSRF 漏洞学习网站:What is CSRF (Cross-site request forgery)? Tutorial & Examples | Web Security Academy CSRF Token 基本原理 CSRF Token 是服务端生成的唯一、随机且不可预测的字符串,用于验证客户端合法校验。 作用:防止攻击…...
【Node.js 】在Windows 下搭建适配 DPlayer 的轻量(简陋)级弹幕后端服务
一、引言 DPlayer官网:DPlayer 官方弹幕后端服务:DPlayer-node MoePlayer/DPlayer-node:使用 Docker for DPlayer Node.js 后端(https://github.com/DIYgod/DPlayer) 本来想直接使用官网提供的DPlayer-node直接搭建…...
淘宝tb.cn短链接生成
淘宝短链接简介 1. 一键在线生成淘宝短链接tb.cn,m.tb.cn等 2. 支持淘宝优惠券短链接等淘宝系的所有网址 3. 生成的淘宝短链接是官方的,安全稳定有保证 4.适合多种场景下使用,如:网站推广,短信推广 量大提供api接口࿰…...
在web应用后端接入内容审核——以腾讯云音频审核为例(Go语言示例)
腾讯云对象存储数据万象(Cloud Infinite,CI)为用户提供图片、视频、语音、文本等文件的内容安全智能审核服务,帮助用户有效识别涉黄、违法违规和广告审核,规避运营风险。本文以音频审核为例给出go语言示例代码与相应结…...
优化无头浏览器流量:使用Puppeteer进行高效数据抓取的成本降低策略
概述 使用 Puppeteer 进行数据抓取时,流量消耗是一个重要考虑因素。特别是在使用代理服务时,流量成本可能显著增加。为了优化流量使用,我们可以采用以下策略: 资源拦截:通过拦截不必要的资源请求来减少流量消耗。请求…...
【C语言】fprintf与perror对比,两种报错提示的方法
它们的主要区别在于 信息来源 和 自动包含的系统错误详情。 1. fprintf(stderr, "自定义错误信息\n"); 功能: 这是标准库中的一个通用格式化输出函数。你可以用它向任何文件流(包括 stdout 标准输出, stderr 标准错误, 或任何用 fopen 打开的文件&#x…...
C语言复习笔记--内存函数
在复习完字符函数和字符串函数之后,今天让我们复习一下内存函数吧.这一块的东西不太多,并且与之前的字符串函数有一些地方很相似,所以这里应该会比较轻松. memcpy使用和模拟实现 老规矩,先看函数原型 void * memcpy ( void * destination, const void * source, size_t num );…...
前端面试高频算法
前端面试高频算法 1 排序算法;1.1 如何分析一个排序算法1.1.1 执行效率3.1.2 内存消耗1.1.3 稳定性 1.2 冒泡排序(Bubble Sort)1.3 插入排序(Insertion Sort)1.4 选择排序(Selection Sort)1.5 归…...
云原生--核心组件-容器篇-4-认识Dockerfile文件(镜像创建的基础文件和指令介绍)
1、Dockerfile的定义与作用 定义: Dockerfile是一个文本文件,包含一系列Docker指令,用于自动化构建Docker镜像。Docker 在构建镜像时会按照Dockerfile中的指令逐步执行,每一行指令都会生成一个新的镜像层(layer&#x…...
13.组合模式:思考与解读
原文地址:组合模式:思考与解读 更多内容请关注:7.深入思考与解读设计模式 引言 在软件开发中,是否曾经遇到过这样一种情况:你有一个对象,它本身很简单,但是它包含了其他类似的对象。随着系统变得越来越复…...
Pycharm(十七)生成器
一、生成器介绍 1.1 概述 生成器指的是Generator对象,它不再像以往一样,一次性生成所有的数据,而是用一个,再生成一个,基于用户写的规则(条件)来生成数据,如果条件不成立ÿ…...
盛元广通实验材料管理系统-实验室管理系统-LIMS
一、引言 在当下科学研究及各类实验日益频繁的背景下,实验材料管理成为实验室高效运作的核心环节。从“人工低效”到“智能自动化”,盛元广通可覆盖实验材料的采购、存储、使用、追踪等全流程,从功能适配性、技术性能、成本效益、供应商服务…...
检查 NetCDF Fortran的版本
执行 nf-config --all命令后,它会输出一堆信息,大致像这样: This netCDF-Fortran version: 4.6.0 netCDF-Fortran installation dir: /usr/local/netcdf4 Fortran compiler: gfortran Fortran compiler flags: -g -O2 Fortran preprocesso…...
MySQL 存储引擎与服务体系深度解析
一、存储引擎核心概念 基本定义 存储引擎:MySQL服务的核心组件,负责数据的存储、检索和管理版本演进: MySQL 5.0/5.1 默认使用MyISAM引擎MySQL 5.5/5.6+ 默认采用InnoDB引擎关键特性 不同存储引擎采用不同的数据存储结构和处理机制直接影响表的CRUD操作性能和数据安全特性作…...
乐企数电发票分布式发票号码生成重复的问题修复思路分享
文章目录 1.前言2.解决思路2.1错误姿势2.2歪打正着2.3正确姿势 3.总结 1.前言 由于之前接了乐企数电开票,服务上线之后,使用的公司少没有啥问题,后面切换了两家日开票量大的公司上线之后,就发现发票号码生成重复了,后面…...
多级缓存架构设计与实践经验
多级缓存架构设计与实践经验 在互联网大厂Java求职者的面试中,经常会被问到关于多级缓存的架构设计和实践经验。本文通过一个故事场景来展示这些问题的实际解决方案。 第一轮提问 面试官:马架构,欢迎来到我们公司的面试现场。请问您对多级…...
LCD1602液晶显示屏详解(STM32)
目录 一、介绍 二、传感器原理 1.原理图编辑 2.接口说明 三、程序设计 main文件 lcd1602.h文件 lcd1602.c文件 四、实验效果 五、资料获取 项目分享 一、介绍 LCD1602A字符型液晶显示模块是专门用于显示字母、数字元、符号等的点阵型液晶显示模块。分4位和8位数据…...
Golang | 集合求交
文章目录 bitmap求交集2个有序链表多个有序链表跳表 bitmap求交集 2个有序链表 多个有序链表 为什么非最大的所有都要往后移动呢?因为现在已经知道交集即使有,也最小都是这个目前最大的了,其他不是最大的不可能是交集,所有除了最大…...
手机充电进入“秒充“时代:泡面刚下锅,电量已满格
现代人的生活节奏越来越快,手机充电技术也在飞速发展。从最初的"充电一整晚"到如今的"秒充"时代,充电效率的提升正在悄然改变着我们的生活习惯。最新数据显示,目前最快的手机充电技术仅需4分30秒就能充满一部手机的电量&…...