数据结构学习笔记——查找算法中的树形查找(平衡二叉树)
目录
- 一、平衡二叉树的定义
- 二、平衡因子
- 三、平衡二叉树的插入和构造
- (一)LL型旋转
- (二)LR型旋转
- (三)RR型旋转
- (四)RL型旋转
- 四、平衡二叉树的删除
- (一)叶子结点
- (二)只有左/右子树,没有右/左子树
- (三)既有左子树,又有右子树
- 五、平衡二叉树的查找和平均查找长度
一、平衡二叉树的定义
平衡二叉树以二叉排序树为基础,若二叉排序树中左、右子树的高度之差的绝对值不超过1
,则称为平衡二叉树(AVL树),其左、右子树也为一棵平衡二叉树,其平均查找长度为O(log2n),如下:
- 一棵具有 m 层的平衡二叉树(AVL),最多有2m-1个结点,由斐波那契数列(Fibonacci),可得最少有f(m) = f(m-1) + f(m-2) + 1个结点,其中f(1) = 1 、f(2) = 2、f(3) = 4。
例如,具有5层结点的平衡二叉树的结点个数至少为f(5) = f(5-1) + f(5-2) + 1= f(4) + f(3) + 1=[f(3) + f(2) + 1]+[f(2) + f(1) + 1]+1=4+2+1+2+1+1+1=12个结点。
二、平衡因子
二叉树中左子树的深度减去其右子树深度
,称为该结点的平衡因子
,平衡二叉树中结点的平衡因子只可能为1
、-1
或0
三种,其中叶子结点
的平衡因子均为0
,例如下面这个二叉树为平衡二叉树:
叶子结点0、1、6的平衡因子均为0,
结点4的左子树深度为1,右子树深度为0,所以平衡因子为1-0=1,
结点9的左子树深度为1,右子树深度为0,所以平衡因子为1-0=1,
结点2的左子树深度为1,右子树深度为2,所以平衡因子为1-2=-1,
结点5的左子树深度为3,右子树深度为2,所以平衡因子为3-2=1。
而,下图这个二叉树为非平衡二叉树:
叶子结点0、1、4、9的平衡因子均为0,
结点3的左子树深度为1,右子树深度为1,所以平衡因子为1-1=0,
结点2的左子树深度为1,右子树深度为2,所以平衡因子为1-2=-1,
结点5的左子树深度为3,右子树深度为1,所以平衡因子为3-1=2,不满足平衡二叉树的要求。
三、平衡二叉树的插入和构造
平衡二叉树的插入操作性质与二叉排序树一样,也是要在保证一定条件下进行插入操作,若导致不满足条件则需要进行调整。若平衡二叉树中插入一个元素时导致发生了不平衡,则需要调整元素的位置关系,使其达到平衡,调整遵循的原则是每次调整的对象都是最小不平衡子树
,即离插入结点最近的其平衡因子的绝对值大于1的结点作为根的子树。
插入新结点导致不平衡的情况有以下四种:
类别 | 操作 |
---|---|
LL型旋转(右单旋转) | 在结点的左子树的左子树插入新结点导致失衡 |
LR型旋转(先左后右旋转) | 在结点的左子树的右子树插入新结点导致失衡 |
RR型旋转(左单旋转) | 在结点的右子树的右子树插入新结点导致失衡 |
RL型旋转(先右后左旋转) | 在结点的右子树的左子树插入新结点导致失衡 |
(一)LL型旋转
若在结点的左子树的左子树
插入新结点导致平衡二叉树失衡,则进行LL型旋转
,即右单旋转。【向右顺时针旋转】
插入新结点6后导致平衡二叉树失衡,插入位置是结点9的左子树的左子树处,所以进行LL型旋转,如下:
调整后的二叉树即为平衡二叉树。
(二)LR型旋转
若在结点的左子树的右子树
插入新结点导致平衡二叉树失衡,则进行LR型旋转
。【先左旋转后右旋转】
插入新结点7后导致平衡二叉树失衡,插入位置是结点9的左子树的右子树处,所以进行LR型旋转,如下:
调整后的二叉树即为平衡二叉树。
(三)RR型旋转
若在结点的右子树的右子树
插入新结点导致平衡二叉树失衡,则进行RR型旋转
,即左单旋转。【向左逆时针旋转】
插入新结点10后导致平衡二叉树失衡,插入位置是结点7的右子树的右子树处,所以进行RR型旋转,如下:
调整后的二叉树即为平衡二叉树。
(四)RL型旋转
若在结点的右子树的左子树
插入新结点导致平衡二叉树失衡,则进行RL型旋转
。【先右旋转后左旋转】
插入新结点6后导致平衡二叉树失衡,插入位置是结点5的右子树的左子树处,所以进行RL型旋转,如下:
调整后的二叉树即为平衡二叉树。
四、平衡二叉树的删除
(一)叶子结点
平衡二叉树中,若要删除的结点只有叶子结点,则可直接将其删除,不影响平衡二叉树。
例如,删除平衡二叉树中的结点9,由于该结点是叶子结点,所以直接删除,如下:
(二)只有左/右子树,没有右/左子树
平衡二叉树中,若要删除的结点只有左/右子树,没有右/左子树,此时将该结点删除,后面的子结点接上即可,从而不影响平衡二叉树。
(三)既有左子树,又有右子树
平衡二叉树中,若要删除的结点既有左子树,又有右子树,此时可沿着左(右)子树的右(左)指针,一直走到右(左)子树的最右(左)边的一个结点,用该结点与要删除的结点代替【找到交换的结点
】,然后,可以将其转换为(一)、(二)中的情况,若替代后,该结点为叶子结点则按照(一)进行删除,若非叶子结点则按照(二)进行删除。
例如,删除平衡二叉树中结点11,首先找到要交换的结点,即结点9,所以结点11与结点9进行交换,如下:
然后,由于此时结点11是叶子结点,此时转换为第一种情况,所以可直接删除,如下:
五、平衡二叉树的查找和平均查找长度
平衡二叉树的查找与二叉排序树一样,含有n个结点的平衡二叉树的最大深度
为h=⌈log2(n+1)⌉,所以其平均查找长度
为O(log2n),另外平衡二叉树的最小深度
为h=⌈log2(n+1)⌉。
相关文章:

数据结构学习笔记——查找算法中的树形查找(平衡二叉树)
目录 一、平衡二叉树的定义二、平衡因子三、平衡二叉树的插入和构造(一)LL型旋转(二)LR型旋转(三)RR型旋转(四)RL型旋转 四、平衡二叉树的删除(一)叶子结点&a…...
P1830 轰炸III
题目背景 一个大小为 ��nm 的城市遭到了 �x 次轰炸,每次都炸了一个每条边都与边界平行的矩形。 题目描述 在轰炸后,有 �y 个关键点,指挥官想知道,它们有没有受到过轰炸,如…...
大语言模型LLM知多少?
你知道哪些流行的大语言模型?你都体验过哪写? GPT-4,Llamma2, T5, BERT 还是 BART? 1.GPT-4 1.1.GPT-4 模型介绍 GPT-4(Generative Pre-trained Transformer 4)是由OpenAI开发的一种大型语言模型。GPT-4是前作GPT系列模型的进一步改进,旨在提高语言理解和生成的能力,…...
Redis命令行使用Lua脚本
Redis命令行使用Lua脚本 Lua脚本在Redis中的使用非常有用,它允许你在Redis服务器上执行自定义脚本,可以用于复杂的数据处理、原子性操作和执行多个Redis命令。以下是Lua脚本在Redis中的基本使用详细讲解: 运行Lua脚本: 在Redis中…...

HTML详细基础(三)表单控件
本帖介绍web开发中非常核心的标签——表格标签。 在日常我们使用到的各种需要输入用户信息的场景——如下图,均是通过表格标签table创造出来的: 目录 一.表格标签 二.表格属性 三.合并单元格 四.无序列表 五.有序列表 六.自定义标签 七.表单域 …...

map和set的具体用法 【C++】
文章目录 关联式容器键值对setset的定义方式set的使用 multisetmapmap的定义方式insertfinderase[]运算符重载map的迭代器遍历 multimap 关联式容器 关联式容器里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高。比如:set…...

聚合统一,SpringBoot实现全局响应和全局异常处理
目录 前言 全局响应 数据规范 状态码(错误码) 全局响应类 使用 优化 全局异常处理 为什么需要全局异常处理 业务异常类 全局捕获 使用 优化 总结 前言 在悦享校园1.0版本中的数据返回采用了以Map对象返回的方式,虽然较为便捷但也带来一些问题。一是在…...

【C/C++笔试练习】——数组名和数组名、switch循环语句、数据在计算机中的存储顺序、字符串中找出连续最长的数字串、数组中出现次数超过一半的数字
文章目录 C/C笔试练习1.数组名和&数组名(1)数组名和&数组名的差异(2)理解数组名和指针偏移(3)理解数组名代表的含义(4)理解数组名代表的含义 2.switch循环语句(6…...

力扣每日一题(+日常水题|树型dp)
740. 删除并获得点数 - 力扣(LeetCode) 简单分析一下: 每一个数字其实只有2个状态选 or 不 可得预处理每一个数初始状态(不选为0,选为所有x的个数 * x)累加即可 for(auto &x : nums)dp[x][1] x;每选一个树 i 删去 i 1 和 i - 1 故我们可以将 i…...
使用perming加速训练可预测的模型
监督学习模型的训练流程 perming是一个主要在支持CUDA加速的Windows操作系统上架构的机器学习算法,基于感知机模型来解决分布在欧式空间中线性不可分数据集的解决方案,是基于PyTorch中预定义的可调用函数,设计的一个面向大规模结构化数据集的…...

【数据库】存储引擎InnoDB、MyISAM、关系型数据库和非关系型数据库、如何执行一条SQL等重点知识汇总
目录 存储引擎InnoDB、MyISAM的适用场景 关系型和非关系型数据库的区别 MySQL如何执行一条SQL的 存储引擎InnoDB、MyISAM的适用场景 InnoDB 是 MySQL 默认的事务型存储引擎,只有在需要它不支持的特性时,才考虑使用其它存储引擎。实现了四个标准的隔…...
车道线分割检测
利用opencv,使用边缘检测、全局变化梯度阈值过滤、算子角度过滤、HLS阈值过滤的方法进行车道线分割检测,综合多种阈值过滤进行检测提高检测精度。 1.利用cv2.Sobel()计算图像梯度(边缘检测) import cv2 import numpy as np import matplotlib.pyplot a…...

树莓集团又一力作,打造天府蜂巢成都直播产业园样板工程
树莓集团再次推出惊艳之作,以打造成都天府蜂巢直播产业园为目标。该基地将充分展现成都直播产业园的巨大潜力与无限魅力,成为一个真正的产业园样板工程。 强强联手 打造未来 成都天府蜂巢直播产业园位于成都科学城兴隆湖高新技术服务产业园内࿰…...
ubuntu 软件包管理之二制作升级包
Deb 包(Debian 软件包)是一种用于在 Debian 及其衍生发行版(例如 Ubuntu)中分发和安装软件的标准包装格式。它们构成了 Debian Linux 发行版中的软件包管理系统的核心组成部分,旨在简化软件的分发、安装、更新和卸载流程。在本篇文章中,我们将深入探讨以下内容: Deb 包基…...
TCP/IP网络江湖——数据链路层的防御招式(数据链路层下篇:数据链路层的安全问题)
目录 引言 一、 数据链路层的隐私与保密 二、数据链路层的安全协议与加密...
ios项目安装hermes-engine太慢问题
问题说明 ios工程,在使用"pod install"安装依赖的时候,由于超时总是报错 $ pod install ... Installing hermes-engine (0.71.11)[!] Error installing hermes-engine [!] /usr/bin/curl -f -L -o /var/folders/4c/slcchpy55s53ysmz_1_q_gzw…...

构建个人云存储:本地电脑搭建SFTP服务器,开启公网访问,轻松共享与管理个人文件!
本地电脑搭建SFTP服务器,并实现公网访问 文章目录 本地电脑搭建SFTP服务器,并实现公网访问1. 搭建SFTP服务器1.1 下载 freesshd 服务器软件1.3 启动SFTP服务1.4 添加用户1.5 保存所有配置 2. 安装SFTP客户端FileZilla测试2.1 配置一个本地SFTP站点2.2 内…...
springboot 下载文件为excel数据,中文自定义单元格宽度
/**2 * Description:表格自适应宽度(中文支持)3 * Author: 4 * param sheet sheet5 * param columnLength 列数6 */7 private static void setSizeColumn(HSSFSheet sheet, int columnLength) {8 for (int columnNum 0; columnNum < …...
机器学习 面试/笔试题
1. 生成模型 VS 判别模型 生成模型: 由数据学得联合概率分布函数 P ( X , Y ) P(X,Y) P(X,Y),求出条件概率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X)的预测模型。 朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型(LDA)、限制玻尔兹曼机…...

某企查ymg_ssr列表详情
js篇— 今天来看下某企查的列表详情–侵删 header发现这个参数 先断点一下 然后上一步 就到了这个地方 就开始扣一下这个js 三大段,先不解混淆了, 给a粘贴出来 ,去掉自执行 给结果稍微改一下 缺windows,开始补环境 直接上…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...

初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...