【数据结构】二叉排序树——平衡二叉树的调整
文章目录
- 前置概念
- 一、构造平衡二叉树的基本思想
- 二、一个示例
- 三、平衡二叉树的调整细节
- (1)LL型(顺时针 )
- 举例
- (2)RR型(逆时针)
- (3)LR型(先逆时针再顺时针)
- 举例
- (4)RL型(先顺时针再逆时针)
- (5)四种调整类型总结
- 四、例题
- 解题过程
参考视频:
懒猫老师-数据结构-(59)平衡二叉树【互动视频】
前置概念
最小不平衡子树:在平衡二叉树的构造过程中,以
距离插入结点最近
的、且平衡因子的绝对值大于1
的结点为根的子树。
例如上图,此处4就是最小不平衡子树的根节点。
一、构造平衡二叉树的基本思想
每插入一个结点,
- 从插入结点向上计算各结点的平衡因子,如果某结点的平衡因子的绝对值大于1,则说明插入操作破坏了二叉排序树的平衡性,需要进行平衡调整;否则继续执行插入操作。
- 如果二叉排序树不平衡,则找出最小不平衡子树的根节点,根据新插入结点与最小不平衡子树根节点的关系判断调整类型。
- 根据调整类型进行相应的调整,使之成为新的平衡子树。
二、一个示例
三、平衡二叉树的调整细节
设结点A为最小不平衡子树的根结点,对该子树平衡调整有以下四种情况:
- LL型
- RR型
- LR型
- RL型
(1)LL型(顺时针 )
插入结点X之后,这棵二叉树不平衡了。B结点的平衡因子变成1(h+1-h)
,A结点的平衡因子变成2(h+2-h)
。这里我们称X结点为问题的发生者;A结点为问题的发现者。从问题的发现者A结点到问题的发生者要经过左子树的左子树(即LL)。
现在A发现二叉树不平衡了,就需要对二叉树进行调整。
旋转:扁担原理; 冲突:旋转优先
利用扁担原理,A结点的左右子树不平衡了:左子树“重”,右子树“轻”。那么我们把B结点往上抬,A结点往下压(进行了一个顺时针旋转),A结点变成了B结点的右子树,B结点原来的右子树调整为A结点的左子树(B结点的右子树上的所有结点一定小于A结点,所以将B原来的右子树调整为A结点的左子树是最合适的)。
举例
(2)RR型(逆时针)
(3)LR型(先逆时针再顺时针)
理解记忆:想象我们正在背一个扁担,发现左边重,但对于左边来说,左边的右边又比较重,所以这个LR型调整成平衡二叉树更为复杂。我们先需要对左边好好调整一番,规整一下(逆时针旋转),调整成LL型,让所有重量完全彻底地压到左边。接着对得到的LL型一次性向右调整(顺时针旋转)。
举例
(4)RL型(先顺时针再逆时针)
(5)四种调整类型总结
四、例题
解题过程
-
找到最小不平衡子树的根结点:5
-
判断类型:从问题的发现者开始到问题的发生者,先左后右,画圈的为RL型不平衡树。
注意:
下面对画圈的部分独立操作。
-
将RL型的不平衡树进行顺时针旋转变成RR型
-
插入结点9,发现二叉树又不平衡了,找到最小不平衡子树的根结点:4
- 判断类型:RR型不平衡树
- 对RR型不平衡树进行逆时针旋转
相关文章:

【数据结构】二叉排序树——平衡二叉树的调整
文章目录前置概念一、构造平衡二叉树的基本思想二、一个示例三、平衡二叉树的调整细节(1)LL型(顺时针 )举例(2)RR型(逆时针)(3)LR型(先逆时针再顺…...
03- pandas 数据库可视化 (数据库)
pandas库的亮点: 一个快速、高效的DataFrame对象,用于数据操作和综合索引;用于在内存数据结构和不同格式之间读写数据的工具:CSV和文本文件、Microsoft Excel、SQL数据库和快速HDF 5格式;智能数据对齐和丢失数据的综合处理&#…...

第三方电容笔怎么样?开学适合买的电容笔
随着科学技术的进步,很多新型的电子产品和数码设备都出现了。比如手机,IPAD,蓝牙耳机,电容笔等等。实际上,如果你想要更好的使用ipad,那么你就需要一支电容笔。比如ipad,我们用ipad来做笔记&…...
Java学习-IO流-字节输出流
Java学习-IO流-IO流的体系和字节输出流基本用法 //IO流 → 字节流 → 字节输入流:InputStream // ↘ ↘ 字节输出流:OutputStream // ↘ 字符流 → 字符输入流:Reader // ↘ 字符输出流:WriterFileInputStream…...

linux性能分析 性能之巅学习笔记和内容摘录
本文只是在阅读《性能之巅》的过程中,对一些觉得有用的地方进行的总结和摘录,并附加一些方便理解的材料,完整内容还请阅读Gregg的大作 概念和方法 性能分析领域一词的全栈代表了整个操作系统的软硬件在内的所有事物 软件生命周期和性能规划…...

机器学习笔记之生成模型综述(三)生成模型的表示、推断、学习任务
机器学习笔记之生成模型综述——表示、推断、学习任务引言生成模型的表示任务从形状的角度观察生成模型的表示任务从概率分布的角度观察生成模型的表示任务生成模型的推断任务生成模型的学习任务引言 上一节介绍了从监督学习、无监督学习任务的角度介绍了经典模型。本节将从表…...

第八章 Flink集成Iceberg的DataStreamAPI、TableSQLAPI详解
1、概述 目前Flink支持使用DataStream API 和SQL API方式实时读取和写入Iceberg表,建议使用SQL API方式实时读取和写入Iceberg表。 Iceberg支持的Flink版本为1.11.x版本以上,以下为版本匹配关系: Flink版本Iceberg版本备注Flink1.11.XI…...

PyTorch学习笔记:nn.Sigmoid——Sigmoid激活函数
PyTorch学习笔记:nn.Sigmoid——Sigmoid激活函数 torch.nn.Sigmoid()功能:逐元素应用Sigmoid函数对数据进行激活,将元素归一化到区间(0,1)内 函数方程: Sigmoid(x)σ(x)11e−xSigmoid(x)\sigma(x)\frac1{1e^{-x}} Sigmoid(x)σ(…...

个人学习系列 - 解决拦截器操作请求参数后台无法获取
由于项目需要使用拦截器对请求参数进行操作,可是请求流只能操作一次,导致后面方法不能再获取流了。 新建SpringBoot项目 1. 新建拦截器WebConfig.java /*** date: 2023/2/6 11:21* author: zhouzhaodong* description:*/ Configuration public class W…...

【编程基础之Python】2、安装Python环境
【编程基础之Python】2、安装Python环境安装Python环境在Windows上安装Python验证Python运行环境在Linux上安装Python验证Python运行环境总结安装Python环境 所谓“工欲善其事,必先利其器”。在学习Python之前需要先搭建Python的运行环境。由于Python是跨平台的&am…...

Java开发 - 问君能有几多愁,Spring Boot瞅一瞅。
前言 首先在这里恭祝大家新年快乐,兔年大吉。本来是想在年前发布这篇博文的,奈何过年期间走街串巷,实在无心学术,所以不得不放在近日写下这篇Spring Boot的博文。在还没开始写之前,我已经预见到,这恐怕将是…...

Office Server Document Converter Lib SDK Crack
关于 Office Server 文档转换器 (OSDC) 无需 Microsoft Office 或 Adobe 软件即可快速准确地转换文档。antennahouse.com Office Server 文档转换器 (OSDC) 会将您在 Microsoft Office(Word、Excel、PowerPoint)中创建的重要文档转换为高质量的 PDF …...

Cubox是什么应用?如何将Cubox同步至Notion、语雀、在线文档中
Cubox是什么应用? Cubox 是一款跨平台的网络收藏工具,通过浏览器扩展、客户端、手机应用、微信转发等方式,将网页、文字、图片、语音、视频、文件等内容保存起来,再经过自动整理、标签、分类之后,就可以随时阅读、搜索…...

计算机网络-传输层
文章目录前言概述用户数据报协议 UDP(User Datagram Protocol)传输控制协议 TCP(Transmission Control Protocol)TCP 的流量控制拥塞控制方法TCP 的运输连接管理TCP 的有限状态机总结前言 本博客仅做学习笔记,如有侵权,联系后即刻更改 科普:…...

HTML-CSS-js教程
HTML 双标签<html> </html> 单标签<img> html5的DOCTYPE声明 <!DOCTYPE html>html的基本骨架 <!DOCTYPE html> <html> </html>head标签 用于定义文档的头部。文档的头部包含了各种属性和信息,包括文档的标题&#…...

【Nacos】Nacos配置中心客户端启动源码分析
SpringCloud项目启动过程中会解析bootstrop.properties、bootstrap.yaml配置文件,启动父容器,在子容器启动过程中会加入PropertySourceBootstrapConfiguration来读取配置中心的配置。 PropertySourceBootstrapConfiguration#initialize PropertySource…...

中国特色地流程管理系统,天翎让流程审批更简单
编者按:本文分析了国内企业在采购流程管理系统常遇到的一些难点,并从适应中国式流程管理模式的特点出发,介绍了符合中国特色的流程审批管理系统——天翎流程管理系统。关键词:可视化开发,拖拽建模,审批控制…...
Python算法:DFS排列与组合算法(手写模板)
自写排列算法: 例:前三个数的全排列(从小到大) def dfs(s,t):if st: #递归结束,输出一个全排列print(b[0:n])else:for i in range(t):if vis[i]False:vis[i]Trueb[s]a[i] #存排列dfs(s1,t)vis[i]Falsea[1,2,3,4,…...

拿来就用的Java海报生成器ImageCombiner(一)
背景如果您是UI美工大师或者PS大牛,那本文一定不适合你;如果当您需要自己做一张海报时,可以立马有小伙伴帮您实现,那本文大概率也不适合你。但是,如果你跟我一样,遇上到以下场景,最近公司上了不…...

【C++】类和对象(二)
目录 一、默认成员函数 二、构造函数 1、构造函数概念 2、构造函数编写 3、默认构造函数 4、内置类型成员的补丁 三、析构函数 1、析构函数概念 2、析构函数编写 3、默认析构函数 四、拷贝构造函数 1、拷贝构造函数概念及编写 2、默认拷贝构造函数 3、拷贝构造…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...

高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...