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

【数据结构】二叉排序树——平衡二叉树的调整

文章目录

    • 前置概念
    • 一、构造平衡二叉树的基本思想
    • 二、一个示例
    • 三、平衡二叉树的调整细节
      • (1)LL型(顺时针 )
        • 举例
      • (2)RR型(逆时针)
      • (3)LR型(先逆时针再顺时针)
        • 举例
      • (4)RL型(先顺时针再逆时针)
      • (5)四种调整类型总结
    • 四、例题
      • 解题过程

参考视频:
懒猫老师-数据结构-(59)平衡二叉树【互动视频】

前置概念

最小不平衡子树:在平衡二叉树的构造过程中,以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树。

在这里插入图片描述

例如上图,此处4就是最小不平衡子树的根节点。

一、构造平衡二叉树的基本思想

每插入一个结点,

  • 从插入结点向上计算各结点的平衡因子,如果某结点的平衡因子的绝对值大于1,则说明插入操作破坏了二叉排序树的平衡性,需要进行平衡调整;否则继续执行插入操作。
  • 如果二叉排序树不平衡,则找出最小不平衡子树的根节点,根据新插入结点与最小不平衡子树根节点的关系判断调整类型。
  • 根据调整类型进行相应的调整,使之成为新的平衡子树。

二、一个示例

在这里插入图片描述

三、平衡二叉树的调整细节

设结点A为最小不平衡子树的根结点,对该子树平衡调整有以下四种情况:

  1. LL型
  2. RR型
  3. LR型
  4. 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 或 Adob​​e 软件即可快速准确地转换文档。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 的有限状态机总结前言 本博客仅做学习笔记,如有侵权,联系后即刻更改 科普&#xff1a…...

HTML-CSS-js教程

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

【Nacos】Nacos配置中心客户端启动源码分析

SpringCloud项目启动过程中会解析bootstrop.properties、bootstrap.yaml配置文件&#xff0c;启动父容器&#xff0c;在子容器启动过程中会加入PropertySourceBootstrapConfiguration来读取配置中心的配置。 PropertySourceBootstrapConfiguration#initialize PropertySource…...

中国特色地流程管理系统,天翎让流程审批更简单

编者按&#xff1a;本文分析了国内企业在采购流程管理系统常遇到的一些难点&#xff0c;并从适应中国式流程管理模式的特点出发&#xff0c;介绍了符合中国特色的流程审批管理系统——天翎流程管理系统。关键词&#xff1a;可视化开发&#xff0c;拖拽建模&#xff0c;审批控制…...

Python算法:DFS排列与组合算法(手写模板)

自写排列算法&#xff1a; 例&#xff1a;前三个数的全排列&#xff08;从小到大&#xff09; def dfs(s,t):if st: #递归结束&#xff0c;输出一个全排列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大牛&#xff0c;那本文一定不适合你&#xff1b;如果当您需要自己做一张海报时&#xff0c;可以立马有小伙伴帮您实现&#xff0c;那本文大概率也不适合你。但是&#xff0c;如果你跟我一样&#xff0c;遇上到以下场景&#xff0c;最近公司上了不…...

【C++】类和对象(二)

目录 一、默认成员函数 二、构造函数 1、构造函数概念 2、构造函数编写 3、默认构造函数 4、内置类型成员的补丁 三、析构函数 1、析构函数概念 2、析构函数编写 3、默认析构函数 四、拷贝构造函数 1、拷贝构造函数概念及编写 2、默认拷贝构造函数 3、拷贝构造…...

自动化立体仓库堆垛机设计(设计说明书+17张CAD图纸+开题报告+任务书+实习报告+中期检查报告+外文翻译)

自动化立体仓库堆垛机作为现代物流系统的核心设备&#xff0c;其设计需兼顾机械结构强度、运动控制精度与系统稳定性。该设计通过三维建模与力学仿真验证&#xff0c;确保堆垛机在高速运行时的结构可靠性&#xff0c;同时优化货叉伸缩机构与载货台升降导轨的配合间隙&#xff0…...

STM32姿态报警器设计:MPU6050与卡尔曼滤波实战

基于STM32的姿态翻转报警器设计与实现1. 项目概述1.1 系统架构本姿态翻转报警系统采用模块化设计&#xff0c;核心架构由STM32F103RCT6微控制器作为主控单元&#xff0c;通过I2C接口连接MPU6050惯性测量单元(IMU)传感器&#xff0c;实时采集设备的三轴加速度和三轴角速度数据。…...

PLCopen运动控制功能块实战:从单轴控制到多轴联动的5个经典案例解析

PLCopen运动控制功能块实战&#xff1a;从单轴控制到多轴联动的5个经典案例解析 在工业自动化领域&#xff0c;精确的运动控制是实现高效生产的关键。无论是简单的传送带定位&#xff0c;还是复杂的多轴协同作业&#xff0c;PLCopen规范提供的标准化功能块都能为工程师提供强大…...

别再用ls了!从Linux文件系统卡顿,看透MinIO多级目录的性能陷阱与正确用法

从Linux文件系统卡顿到MinIO性能陷阱&#xff1a;高效查询的工程哲学 当你在Linux终端输入ls命令后&#xff0c;系统突然卡死——这种经历对许多开发者来说并不陌生。但很少有人意识到&#xff0c;同样的性能陷阱正潜伏在MinIO这类对象存储系统的日常使用中。本文将揭示文件系…...

AS_BH1750库:BH1750FVI环境光传感器嵌入式驱动设计与工程实践

1. AS_BH1750库概述&#xff1a;面向嵌入式系统的BH1750FVI环境光传感器驱动设计与工程实践BH1750FVI是由ROHM Semiconductor推出的高精度数字环境光传感器&#xff08;Ambient Light Sensor, ALS&#xff09;&#xff0c;采用IC接口&#xff0c;具备宽动态范围&#xff08;0.1…...

XML Notepad:Windows平台XML文档编辑与转换的完整解决方案

XML Notepad&#xff1a;Windows平台XML文档编辑与转换的完整解决方案 【免费下载链接】XmlNotepad XML Notepad provides a simple intuitive User Interface for browsing and editing XML documents. 项目地址: https://gitcode.com/gh_mirrors/xm/XmlNotepad XML No…...

嵌入式系统SOC验证与Linux实时补丁技术解析

嵌入式系统软件工程师面试技术要点解析 1. SOC原型验证技术体系 1.1 SOC验证工作内容与方法论 SOC原型验证是芯片设计流程中的关键环节&#xff0c;主要工作内容包括&#xff1a; 功能验证&#xff1a;确保设计符合规范要求 性能验证&#xff1a;评估系统吞吐量、延迟等指标…...

2026必看:八款热门AI编程工具横评

一、AI编程工具榜单综述当下AI技术全面渗透软件开发领域&#xff0c;各类AI编程工具大幅降低了开发门槛、提升了编码效率&#xff0c;成为开发者必备的效率神器。本次横评精选海内外8款主流产品&#xff0c;覆盖AI原生IDE、插件式编程助手等不同形态&#xff0c;全方位盘点各工…...

ChatBI 开源产品实战解析:从语义层到Agent,如何选择你的AI数据助手?

1. 为什么企业需要AI数据助手&#xff1f; 想象一下这个场景&#xff1a;市场部的小王需要统计上季度各区域的销售数据&#xff0c;他对着Excel表格里密密麻麻的数字发愁&#xff0c;不得不找IT部门帮忙写SQL查询。三天后拿到数据时&#xff0c;业务窗口期已经错过——这是很多…...

开源工具实现游戏存档编辑:虚幻引擎存档处理全指南

开源工具实现游戏存档编辑&#xff1a;虚幻引擎存档处理全指南 【免费下载链接】uesave 项目地址: https://gitcode.com/gh_mirrors/ue/uesave 在游戏开发与玩家体验中&#xff0c;虚幻引擎的存档文件往往以二进制格式存储&#xff0c;这给数据修改、备份与分析带来了挑…...