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

十四、平衡二叉树

1、看一个案例(说明二叉排序树可能的问题)

给你一个数列{1,2,3,4,5,6},要求创建一棵二叉排序树(BST),并分析问题所在。
在这里插入图片描述
上面二叉排序树存在问题分析:

  • 左子树全部为空,从形式上看,更像一个单链表
  • 插入速度没有影响
  • 查询速度明显降低(因为需要依次比较),不能发挥BST的优势,因为每次还需要比较左子树,其查询速度比单链表还慢。
  • 解决方案-平衡二叉树(AVL)

2、基本介绍

1)平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树,可以保证查询效率较高。
2)具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL树、替罪羊树、Treap、伸展树等。
3)举例说明,看看下面哪些是AVL树?
在这里插入图片描述

3、应用案例:单旋转(左旋转)

1)要求:给你一个数列,创建出对应的平衡二叉树,数列{4,3,6,5,7,8}
2)思路分析(示意图)
在这里插入图片描述

4、应用案例:单旋转(右旋转)

1)要求:给你一个数列,创建出对应的平衡二叉树,数列{10,12,8,9,7,6}
2)思路分析(示意图)
在这里插入图片描述

5、应用案例:双旋转

在这里插入图片描述
解决思路分析:

当符合右旋转条件时,如果它的左子树的右子树的高度大于它的左子树高度,先对当前这个节点的左节点进行旋转,在对当前节点进行右旋转的操作即可

6、完整代码

相关文章:

十四、平衡二叉树

1、看一个案例(说明二叉排序树可能的问题) 给你一个数列{1,2,3,4,5,6},要求创建一棵二叉排序树(BST),并分析问题所在。 上面二叉排序树存在问题分析: 左子树全部为空,从形式上看&…...

AC/DC 基础

一、概念: AC转换成DC的基本方法有变压器方式和开关方式,如下图1、2所示;整流的基本方法有全波整流和半波整流,如下图3所示。 图1 变压器方式 图2 开关方式 图3 整流方式 二、转换方式 1、变压器方式 变压器方式首先需要通过变压…...

集成电路相关书籍

注:从此开始,文中提到的书籍都会在公众号对应文章末尾给出链接,不需要在微信后台获取,当然还是可以通过在微信后台回复相关书名获取对应的电子书。 在后台看到很多人回复集成电路相关的一些书籍,所以本文就提供一些书籍…...

前端开发之防抖与节流

前端开发中我们经常会通过监听某些事件来完成项目需求 1.通过监听 scroll 事件,检测滚动位置,根据滚动位置显示返回顶部按钮 2.通过监听 resize 事件,对某些自适应页面调整DOM的渲染(通过CSS实现的自适应不再此范围内)…...

大公司如何用A/B测试解决增长问题?

摘要:上线六年,字节跳动的短视频产品——抖音已成为许多人记录美好生活的平台。除了抖音,字节跳动旗下还同时运营着数十款产品,从资讯、游戏,到房产、教育等横跨多个领域。在产品迭代速度和创新能力的快速发展下&#…...

【Airplay_BCT】Bonjour API架构

Bonjour API 架构 OS X 和 iOS 为 Bonjour 服务应用程序提供了多层应用程序编程接口 (API): Foundation 框架中的 NSNetService 和 NSNetServiceBrowser 类; CFNetServices,Core Services 中 CFNetwork 框架的一部分; Java 的 DN…...

为什么sleeping的会话会造成阻塞(2)

背景客户反馈系统突然从11:10开始运行非常缓慢,在SQL专家云中看到大量的产生阻塞的活动会话,KILL掉阻塞的源头马上又出现新的源头,实在没有办法只能重启应用程序断开所有数据库连接才解决,请我们协助分析根本的原因。现象登录SQL专…...

从矩阵中提取对角线元素;将一维数组转换为对角线矩阵:np.diag()函数

【小白从小学Python、C、Java】【计算机等级考试500强双证书】【Python-数据分析】从矩阵中提取对角线元素将一维数组转换为对角线矩阵np.diag()函数选择题下列说法错误的是?import numpy as npmyarray1 np.array([1,2,3])print("【显示】myarray1")print(myarray1…...

JavaSE学习day7_02 封装和构造方法

4. 封装 面向对象的三大特征: 封装、继承、多态 封装:对象代表什么,就得封装对应的数据,并提供数据对应的行为。 比如人画圆:”画“这个行为应该封装在圆这个类,为什么?因为”画“圆要知道圆…...

2022年FIT2CLOUD飞致云开源成绩单

2023年2月15日,中国领先的开源软件公司FIT2CLOUD飞致云发布《2022年开源成绩单》,盘点公司2022年全年在开源软件产品与社区运营方面的表现。目前,飞致云旗下的核心开源软件组合包括JumpServer开源堡垒机、DataEase开源数据可视化分析平台、Me…...

【Python】asyncio使用注意事项

目录协程的定义协程的运行多个协程运行关于loop.close()回调事件循环协程的定义 需要使用 async def 语句 协程可以做哪些事: 1、等待一个future结果 2、等待另一个协程(产生一个结果或引发一个异常) 3、产生一个结果给正在等它的协程 4、引发一个异常给正在等它的协程 …...

成都链安受邀参加第五届CCF中国区块链技术大会

2月10-12日,由中国计算机学会主办的,2023年国内首场大型区块链学术会议—第五届CCF中国区块链技术大会在无锡市成功举办,成都链安作为区块链安全头部企业受邀参加此次大会。大会上,成都链安创始人&CTO郭文生教授与锡东新城商务…...

验证码识别--封装版

前面我们说过了数字英文的验证码识别操作,本章我们对其进行完善一下,结合selenium来实际操作操作。import osimport timedef coding_path(path):Base_Path os.path.abspath(os.path.dirname(os.path.abspath(__file__)) /..)Base_image os.path.join(…...

创建Wails项目

项目生成​ 现在 CLI 已安装,您可以使用 wails init 命令生成一个新项目。 选择您最喜欢的框架: SvelteReactVuePreactLitVanilla 使用 JavaScript 生成一个 Vue 项目: wails init -n myproject -t vue如果您更愿意使用 TypeScript: wails init -…...

深度解析UG二次开发装配的部件事件、部件原型和部件实例

做UG二次开发快一年了,每次遇到装配的问题涉及到部件事件、部件原型和部件实例还是一头雾水,什么是实例,什么是原型这些专业术语等等。 针对这个问题,今天专门写了一篇特辑,结合装配实例深度剖析装配过程中的的所有参数…...

Linux安装elasticsearch-head

elasticsearch-head 是一款专门针对于 elasticsearch 的客户端工具,用来展示数据。 elasticsearch-head 是基于 JavaScript 语言编写的,可以使用 Nodejs 下的包管理器 npm 部署。 1 安装Nodejs nodejs下载地址: https://nodejs.org/en/dow…...

MySQL InnoDB表的碎片量化和整理(data free能否用来衡量碎片?)

网络上有很多MySQL表碎片整理的问题,大多数是通过demo一个表然后参考data free来进行碎片整理,这种方式对myisam引擎或者其他引擎可能有效(本人没有做详细的测试).对Innodb引擎是不是准确的,或者data free是不是可以参…...

Leetcode-每日一题1250. 检查「好数组」(裴蜀定理)

题目链接:https://leetcode.cn/problems/check-if-it-is-a-good-array/description/ 思路 方法:数论 题目意思很简单,让你在数组 nums中选取一些子集,可以不连续,子集中的每个数再乘以任意的数的和是否为1&#xff…...

OpenStack手动分布式部署环境准备【Queens版】

目录 1.基础环境准备(两个节点都需要部署) 1.1关闭防火墙 1.2关闭selinux 1.3修改主机名 1.4安装ntp时间服务器 1.5修改域名解析 1.6添加yum源 2.数据库安装配置 2.1安装数据库 2.2修改数据库 2.3重启数据库 2.4初始化数据库 3.安装RabbitMq…...

Web自动化测试——selenium的使用

⭐️前言⭐️ 本篇文章就进入了自动化测试的章节了,如果作为一名测试开发人员,非常需要掌握自动化测试的能力,因为它不仅能减少人力的消耗,还能提升测试的效率。 🍉欢迎点赞 👍 收藏 ⭐留言评论 &#x1f…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架,该方法利用Stable Diffusion的强大生成能力,仅需单个正常样本和文本描述,即可生成逼真且多样化的异常样本,有效解决了视觉异常检测中异常样本稀缺的难题,为工业质检、医疗影像…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码:冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...

[拓扑优化] 1.概述

常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...