当前位置: 首页 > 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…...

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

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

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

生成 Git SSH 证书

🔑 1. ​​生成 SSH 密钥对​​ 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​: -t rsa&#x…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...

2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版

1.题目描述 2.思路 当前的元素可以重复使用。 (1)确定回溯算法函数的参数和返回值(一般是void类型) (2)因为是用递归实现的,所以我们要确定终止条件 (3)单层搜索逻辑 二…...

rm视觉学习1-自瞄部分

首先先感谢中南大学的开源,提供了很全面的思路,减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接:https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架: 代码框架结构:readme有…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...