当前位置: 首页 > 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、拷贝构造…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

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

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...