数据结构与算法(Python版)五十四:AVL树的定义和性能

平衡二叉查找树: AVL树的定义

我们来看看能够在key插入时一直保持平衡的二叉查找树: AVL树

AVL是发明者的名字缩写: G.M. AdelsonVelskii and E.M. Landis

利用AVL树实现ADT Map, 基本上与BST的实现相同

不同之处仅在于二叉树的生成与维护过程

AVL树的实现中, 需要对每个节点跟踪“平衡因子balance factor”参数

平衡因子是根据节点的左右子树的高度来定义的, 确切地说, 是左右子树高度差:

balanceFactor = height(leftSubTree) − height(rightSubTree)
如果平衡因子大于0,称为“左重left-heavy”,小于零称为“右重right-heavy”,平衡因子等于0,则称作平衡。

平衡二叉查找树:平衡因子

如果一个二叉查找树中每个节点的平衡因子都在-1, 0, 1之间, 则把这个二叉搜索树称为平衡树

在这里插入图片描述

平衡二叉查找树: AVL树的定义

在平衡树操作过程中, 有节点的平衡因子超出此范围, 则需要一个重新平衡的过程

要保持BST的性质!

先来看看AVL树的性能

我们来分析AVL树最差情形下的性能:即平衡因子为1或者-1

下图列出平衡因子为1的“左重”AVL树,树的高度从1开始,来看看问题规模(总节点数N)和比对次数(树的高度h)之间的关系如何?
在这里插入图片描述

观察上图h=1~ 4时, 总节点数N的变化

  • h= 1, N= 1
  • h= 2, N= 2= 1+ 1
  • h= 3, N= 4= 1+ 1+ 2
  • h= 4, N= 7= 1+ 2+ 4

在这里插入图片描述

观察这个通式, 很接近斐波那契数列!

定义斐波那契数列Fi

利用Fi重写Nh
在这里插入图片描述

斐波那契数列的性质: Fi/Fi-1趋向于黄金分割Φ

可以写出Fi的通式
在这里插入图片描述

将Fi通式代入到Nh中, 得到Nh的通式

在这里插入图片描述

上述通式只有N和h了, 我们解出h

在这里插入图片描述

最多搜索次数h和规模N的关系, 可以说AVL树的搜索时间复杂度为O(log n)

热门文章

暂无图片
编程学习 ·

终于等到你,飞凌嵌入式i.MX6ULL核心板如约而至!

自从 2016年初,我们推出了FETMX6UL-C 核心板后,其高性价比、丰富的功能、15年生命周期、高稳定性的多方面优势,受到了广大客户的一致好评,在电力、医疗、工控、 物联网、能源管理、光伏、环境监测等领域取得大规模应用。 在此基础上, 我们推出了 FETMX6UL-C的“双胞胎兄弟…
暂无图片
编程学习 ·

安卓扫描车牌识别的功能SDK

安卓扫描车牌识别的功能SDK 为了缓解停车压力,在不影响道路使用的情况下,很多地方都在道路上划出一部分停车位,来供车主使用,此之为占道停车。目前国内路边占道停车主要是使用咪表、地磁、手持终端及人工的方式进行管理和收费。对于占道停车管理来说,在手机端集成一个优秀…
暂无图片
编程学习 ·

Web会话管理

1.会话管理基本原理 1.隐藏域 将表单中的内容在显示页面时隐藏,不显示数据,在JSP 中将input标签type设置为hidden 生成一个隐藏表单域。将会话的唯一标识记录到隐藏域中的value值中,并设定name值。提交给服务器之后,服务器会根据根据会话标识找到会话对象。 缺点:实现比较…
暂无图片
编程学习 ·

718. 最长重复子数组

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。目录1、题目分析2、解题分析3、代码示例 1:输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。1、题目分析求两个数组公共的子数组的长度,那么可以用较短的那个…
暂无图片
编程学习 ·

利用OpenJ9大幅度降低JAVA内存占用

OpenJ9 介绍OpenJ9是一种高性能,可扩展的Java™虚拟机(VM)实现,完全符合Java虚拟机规范。在运行时,VM解释由Java编译器编译的Java字节码。VM充当语言与底层操作系统和硬件之间的翻译器。Java程序需要特定的VM才能在特定的平台(例如Linux,z /OS或Windows™)上运行。Open…
暂无图片
编程学习 ·

window.performance.navigation.type

performance.navigation.type(该属性返回一个整数值,表示网页的加载来源,可能有以下4种情况):0:网页通过点击链接、地址栏输入、表单提交、脚本操作等方式加载,相当于常数performance.navigation.TYPE_NAVIGATE。1:网页通过“重新加载”按钮或者location.reload()方法加…
暂无图片
编程学习 ·

Android中给Layout添加点击事件

@Android中给Layout添加点击事件 步骤一:在layout控件中设置clickable和focuseable和id <LinearLayout android:id="@+id/to_anchor_dialog" android:onClick=“onClick” android:clickable=“true” android:layout_width=“match_parent” android:layout_hei…
暂无图片
编程学习 ·

还是别看学位论文

最近我实验室的一个组在做疫情预测的工作。效果还行,论文也写的差不多了。不过上面的老师说引的文章都太老了,让再加点新的。于是今天下午我就和大家一起看文献。之所以之前引的都比较老,主要是因为传染病预测这块分两派,一派是理论建模派,主要工具就是微分动力模型,一般…
暂无图片
编程学习 ·

01 | 为什么需要消息队列?

1.应用场景见: https://blog.csdn.net/william_n/article/details/1040254082.学习/操作2.1 阅读文档01 | 为什么需要消息队列?李玥 2020-01-1400:0011:24讲述:李玥 大小:10.46M你好,我是李玥。今天我们来讲讲为什么需要消息队列,消息队列主要解决的是什么问题。消息队列…
暂无图片
编程学习 ·

LeetCode_Everyday:021 Merge Two Sorted Lists

LeetCode_Everyday:021 Merge Two Sorted Lists题目:示例:代码参考此外 LeetCode Everyday:坚持价值投资,做时间的朋友!!! 题目: 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例:示例 1:输入:1->2->4, 1-…
暂无图片
编程学习 ·

latex小技巧

latex小技巧 大学写论文需要用到的latex编辑工具,当初从0开始学习着实走了很多弯路,现在大学毕业了,估计这个东西很长一段时间不会用到了,做个笔记以后遗忘了可以来回看一看。 在已经具有完整latex模板的前提下,使用下面的内容将帮助你快速完成Latex的编写。 工具栏实用工…
暂无图片
编程学习 ·

STM32CubeMX5.6.1生成的代码无启动文件

丢失启动文件 使用这个版本的CubeMX,生成的代码里面没有对应的启动文件。编译报错 展开图片,在Drivers/CMSIS文件夹下面,没有启动文件。编译不通过,报错No section matches selector - no section to be FIRST/LAST。//------------------------------------------ 解决方法…
暂无图片
编程学习 ·

本地项目提交到Github上

1.在个人github主页创建一个空仓库2.填写完相关资料后再项目文件中打开本地git客户端3.进入到刚刚的新建仓库中,如图操作3.依次在git客户端内输入以下命令,这部会用到上面复制到的地址 git initgit add .origin后面的地址是你刚刚自己复制的地址 git remote add origin https:/…
暂无图片
编程学习 ·

Java网络编程

端口号范围:0~65535,建议选择1024以上 UDP:面向无连接,数据不安全,速度快,不区分客户端和服务器(有发送端和接收端)(发短信) TCP:面向连接(三次握手),数据安全,速度略低,分为客户端和服务器(打电话) 1.UDP package day26;import java.io.IOException; import…
暂无图片
编程学习 ·

Java数据结构--循环链表

一、简介 1.1 概念对于单链表而言,最后一个结点的地址为空,如果表示最后一个结点的指针域指向头结点,整个链表形成一个环,就构成了单循环链表。 与单链表相比,只是将原来判断指针是否为空变为判断是否是头指针,没有其他的变化。 访问单循环链表某一结点,可以从任何一个结…
暂无图片
编程学习 ·

UE4学习-添加机关并添加代码控制

文章目录添加机关代码编写给密室添加屋顶打印日志控制系统角色创建一个新游戏模式替换DefaultPawn添加抓取组件获取起点和终点物体拾取,碰撞属性设置今日完整代码 添加机关 首先向场景里面添加一个聚光源添加聚光源以后,可以对其属性进行修改,如图:然后需要给聚光源添加一个…
暂无图片
编程学习 ·

Node.js爬虫实验项目二(二)后续

登录与注册 随后我们开始设置登录与注册页面,我们需要设定一些制度,比如没有注册的用户不可以登陆,不登陆不可以查看数据。 在登陆和注册时也需要添加提示功能,类似于登录时的密码错误时提示,注册时两次密码不相同时提示等日常登录注册页面所需要的提示功能必须都具备。 登…
暂无图片
编程学习 ·

查看、生成 SSH 密钥用于安全登陆

SSH 可以用来登陆服务器,远程执行命令,并用强加密算法编码保护通信安全,目前广泛应用于远程命令控制、文件加密传输等方面。SSH 登陆服务器的方法一般有两种:密码登陆和密钥登陆。 在受信任的设备上使用密钥鉴权方式登陆相比于每次登陆时输入密码更加方便,也免除了密码被偷…