Python
Java
PHP
IOS
Android
Nodejs
JavaScript
Html5
Windows
Ubuntu
Linux
AVL 树
2023-05-16
目录
介绍
结点高度
结点平衡因子
AVL 树旋转
右旋
左旋
先左后右
先右后左
旋转的选择
插入结点
删除结点
查找结点
AVL 树典型应用
介绍
在进行多次插入与删除操作后,二叉搜索树可能会退化为链表
此时所有操作的时间复杂度都会由 𝑂(log 𝑛) 劣化至 𝑂(𝑛)
如下图所示,执行两步删除结点后,该二叉搜索树就会退化为链表
再比如,在以下完美二叉树中插入两个结点后,树严重向左偏斜,查找操作的时间复杂度也随之发生劣化
而在不断添加与删除结点后,AVL 树仍然不会发生退化,进而使得各种操作的时间复杂度均能保持在 𝑂(log 𝑛) 级别
换言之,在频繁增删查改的使用场景中,AVL 树可始终保持很高的数据增删查改效率,具有很好的应用价值
「AVL 树」既是「二叉搜索树」又是「平衡二叉树」,同时满足这两种二叉树的所有性质,因此又被称为「平衡二叉搜索树」
结点高度
在 AVL 树的操作中,需要获取结点「高度 Height」,所以给 AVL 树的结点类添加 height 变量
「结点高度」是最远叶结点到该结点的距离,即走过的「边」的数量
需要特别注意,叶结点的高度为 0 ,空结点的高度为 ‑1
封装两个工具函数,分别用于获取与更新结点的高度
结点平衡因子
结点的「平衡因子 Balance Factor」是 结点的左子树高度减去右子树高度,并定义空结点的平衡因子为 0
同样地,将获取结点平衡因子封装成函数,以便后续使用
设平衡因子为 𝑓 ,则一棵 AVL 树的任意结点的平衡因子皆满足 −1 ≤ 𝑓 ≤ 1
AVL 树旋转
AVL 树的独特之处在于「旋转 Rotation」的操作,其可在不影响二叉树中序遍历序列的前提下,使失衡结点重新恢复平衡
换言之,旋转操作既可以使树保持为「二叉搜索树」,也可以使树重新恢复为「平衡二叉树」
将平衡因子的绝对值 > 1 的结点称为「失衡结点」
根据结点的失衡情况,旋转操作分为 右旋、左旋、先右旋后左旋、先左旋后右旋
右旋
如下图所示(结点下方为「平衡因子」),从底至顶看,二叉树中首个失衡结点是 结点 3
聚焦在以该失衡结点为根结点的子树上,将该结点记为 node ,将其左子结点记为 child ,执行「右旋」操作
完成右旋后,该子树已经恢复平衡,并且仍然为二叉搜索树
进而,如果结点 child 本身有右子结点(记为 grandChild ),则需要在「右旋」中添加一步:将 grandChild 作为 node 的左子结点
“向右旋转”是一种形象化的说法,实际需要通过修改结点指针实现,代码如下所示
左旋
类似地,如果将取上述失衡二叉树的“镜像”,那么则需要「左旋」操作
同理,若结点 child 本身有左子结点(记为 grandChild ),则需要在「左旋」中添加一步:将 grandChild 作为node 的右子结点
观察发现,「左旋」和「右旋」操作是镜像对称的,两者对应解决的两种失衡情况也是对称的
根据对称性,可以很方便地从「右旋」推导出「左旋」
具体地,只需将「右旋」代码中的把所有的 left 替换为 right 、所有的 right 替换为 left ,即可得到「左旋」代码
先左后右
对于下图的失衡结点 3 ,单一使用左旋或右旋都无法使子树恢复平衡
此时需要「先左旋后右旋」,即先对child 执行「左旋」,再对 node 执行「右旋」
先右后左
同理,取以上失衡二叉树的镜像,则需要「先右旋后左旋」,即先对 child 执行「右旋」,然后对 node 执行「左旋」
旋转的选择
下图描述的四种失衡情况与上述 Cases 逐个对应,分别需采用 右旋、左旋、先右后左、先左后右 的旋转操作
具体地,在代码中使用失衡结点的平衡因子、较高一侧子结点的平衡因子 来确定失衡结点属于上图中的哪种情况
为方便使用,将旋转操作封装成一个函数
至此可以使用此函数来旋转各种失衡情况,使失衡结点重新恢复平衡
插入结点
「AVL 树」的结点插入操作与「二叉搜索树」主体类似
不同的是,在插入结点后,从该结点到根结点的路径上会出现一系列「失衡结点」
所以需要从该结点开始,从底至顶地执行旋转操作,使所有失衡结点恢复平衡
删除结点
「AVL 树」删除结点操作与「二叉搜索树」删除结点操作总体相同
类似地,在删除结点后,也需要从底至顶地执行旋转操作,使所有失衡结点恢复平衡
查找结点
「AVL 树」的结点查找操作与「二叉搜索树」一致,在此不再赘述
AVL 树典型应用
组织存储大型数据,适用于高频查找、低频增删场景
用于建立数据库中的索引系统
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)
AVL
AVL 树 的相关文章
vcruntime140_1.dll无法继续执行代码如何修复?
vcruntime140 1 dll是电脑系统动态链接中非常重要的文件 xff0c 主要用于处理各种程序 每台计算机上都有相当多的DLL文件 xff0c 不同的程序会使用不同的DLL文件 电脑系统如果丢失dll文件 xff0c 会导致很多软
Linux基础指令的基本操作(一)
文章目录 Linux用户管理 xff1a 1 adduser添加用户2 passwd修改用户密码3 userdel删除用户 其他指令alias指令 取别名 whoami指令man指令 重要 bc指令unamefreedf h Linux 访
Linux 权限(二)权限掩码 粘滞位 详细
文章目录 Linux权限的概念Linux权限管理01 文件访问者的分类 xff08 人 xff09 02 文件类型和访问权限 xff08 事物属性 xff09 拥有者 xff0c 所属组 xff0c other vs root 和普通用户a
Linux——基础IO
文章目录 先来段代码回顾C文件接口写文件读文件输出信息到显示器 xff0c 你有哪些方法 默认打开的三个流 stdin amp stdout amp stderr系统接口openclosewriteread文件描述符fd文件描述符的分配规则
boost字符串库简单使用
boost字符串库简单使用 说明用法大小写转换字符串分割去掉字符串两边空格替换字符串 replace first replace first copy 说明 写c 43 43 程序的时候 xff0c 虽然std string有数百余函数 x
线程安全下单例模式
文章目录 什么是单例模式单例模式的特点定义对象的本质什么时候创建对象饿汉实现方式和懒汉实现方式饿汉方式实现单例模式懒汉方式实现单例模式懒汉方式实现单例模式 线程安全版本 什么是单例模式 单例模式是一种 经典的 常用的 常考的 设计模式 单例
Linux 线程池
文章目录 线程池的定义使用线程池的原因基于POSIX实现的线程池基于block队列的线程池实现基于ring队列的线程池实现 设计单例模式线程池 线程池的定义 线程池就一堆已经创建好的任务线程 xff0c 初始它们都处于空闲等待状态 xff0
魔都,3年,程序员到CTO
过一个平凡无趣的人生实在太容易了 xff0c 你可以不读书 xff0c 不冒险 xff0c 不运动 xff0c 不写作 xff0c 不外出 xff0c 不折腾 但是 xff0c 人生最后悔的事情就是 xff1a 我本可以 陈素封 我可以 在
TCP协议
文章目录 1 保证可靠性机制1 1 确认应答机制1 1 1确认应答机制概念1 1 2常规确认应答的工作方式1 1 3报文按序到达1 1 4 如何确认历史数据被收到1 1 5 16位序号和16确认序号 xff08 字段讲解 xff09 tcp
1 对数器,二分查找,
文章目录 对数器二分查找 1 有序序列二分查找 2 在一个有序数组中 xff0c 找 lt 61 某个数最右侧的位置 3 在一个有序数组中 xff0c 找 gt 61 某个数最左侧的位置 4 无序序列二分查找 xff0c 求局部最小值 对数
2 异或位运算大厂必刷题
文章目录 如何不用额外变量交换两个数一个数组中有一种数出现了奇数次 xff0c 其他数都出现了偶数次 xff0c 怎么找到并打印这种数怎么把一个int类型的数 xff0c 提取出最右侧的1来怎么把一个int类型的数 获取位数为1的数量一个数
链表,栈,队列,递归行为,哈希表,有序表
文章目录 链表1 单链表 双链表的反转2 删除链表中指定的值 队列1 数组循环队列的实现2 双向链表实现双端队列 栈1 用数组实现栈 栈和队列的面试题1 实现最小栈2 两个栈实现一个队列3 两个队列实现一个栈4 用栈实现图的广度优先遍历5
搭建Zabbix6.0版本
Zabbix简介 Zabbix是一个企业级的开源分布式监控解决方案 xff0c 由C语言编写而成的底层架构 xff08 server端和agent端 xff09 xff0c 由一个国外的团队持续维护更新 xff0c 软件可以自由下载使用 x
Linux--网络服务器配置步骤详情【1】
目录 一 配置ip地址 二 配置yum服务器 三 配置安装nfs服务器 1 第一台机 xff1a 2 第二台机 xff1a 四 安装配置samba服务器 五 安装配置DHCP 一 配置ip地址 root 64 wenjian vi etc
vscode提取拓展时出错。XHR failed
vscode提取拓展时出错 XHR failed huas weew12的博客 CSDN博客 提取扩展时出错 转载 这这人家的步骤操作 果然就好了
python天气语音播报
今天的小项目是一个天气播报 xff0c 项目效果是点击运行就读出今天的天气 那么我们可以分两步走 xff0c 第一个 xff1a 先爬取到今天的天天气内容 xff0c 第二步 xff1a 电脑读出今天的天气内容 想要电脑读出内容 xff0c
Linux配置SSH远程登录管理
目录 一 SSH协议 1 SSH简介 2 SSH的优点 3 SSH远程控制软件及服务 二 SSH远程管理配置 1 配置OpenSSH服务端 2 使用SSH客户端软件 xff08 1 xff09 SSH远程登录 xff08 2 xff09 s
随机推荐
Linux系统防火墙firewalld
目录 一 firewalld概述 二 firewalld和iptables的关系 三 firewalld区域的概念 四 firewalld数据处理流程 五 firewalld检查数据包源地址的规则 六 firewalld防火墙的配置种类 1
ubuntu18.04忘记密码后,如何重置密码的方法
ubuntu18 04安装在VMware虚拟上 ubuntu18 04忘记密码后 xff0c 如何重置密码 xff1f 重启系统后 xff0c 当跳出如下图所示画面时 xff0c 按住Shift键不放 xff0c 等待 2 但出现如下图所示
Cloudflare 小记
url xff1a https cn airbusan com content individual 五秒盾打开后一般会出现这个页面 xff0c 然后让你点击确认你是不是真人 xff0c 点击成功后会跳往所访问的url页面 有时候不会出现这
2021.11.17 指针引用数组(指针+1,指针-1以及书写格式)
例如 xff1a int arr 10 61 1 2 3 4 5 6 7 8 9 10 int p 61 arr int q 61 amp arr 0 1 p 和 q 表示的都是一样的 xff0c 表示的都是数组首元素的地址 xff0c 只
超详细的vscode 配置FTP,并本地编辑
废话少说 xff0c 直接上步骤 xff1a 搜索sftp插件并安装 xff1b 安装成功之后 ctrl 43 shift 43 p 搜索sftp config设置内容 没有的需要自己加 xff0c 有的可以不用加 xff1b 34 nam
Python求1+2+3+...+100的值,计算平方根的两个代码程序
目录 前言 一 求1 43 2 43 3 43 43 100的值 1 实现的功能 2 代码程序 3 运行截图 二 计算平方根 1 实现的功能 2 代码程序 3 运行截图 前言 1 因多重原因 xff0c 本博文由两个程序代码部分组成 xff
Python求1+2+3+...+100的值,计算自然数的立方和的两个程序代码
目录 前言 一 求1 43 2 43 3 43 43 100的值 1 实现的功能 2 代码程序 3 运行截图 二 计算自然数的立方和的 1 实现的功能 2 代码程序 3 运行截图 前言 1 因多重原因 xff0c 本博文由两个程序代码部分组
Go基本数据类型与string类型互转
一 基本数据类型转string类型 方法一 xff1a fmt Sprintf 34 参数 34 表达式 1 官方解释 xff1a Sprintf根据format参数生成格式化的字符串并返回该字符串 func Sprintf format
linux下如何设置开机自启(这里以seata服务为例)
1 编写启动脚本 xff0c 大部分都是相同的 xff0c 但是有些程序可能略要修改 Unit Description 61 Seata Server After 61 network target Service User 61 root
MIUI12.5系统精简列表更新版200多个包,ADB卸载
系统MIUI12 5 6 xff0c 无ROOT无面具没破解 xff0c 仅使用ADB工具箱 设备卸载后经过重启测试是否卡米 xff0c 这些都不会卡米 另外要说 xff0c 有些卸载不会卡米 xff0c 但是功能会失效 xff0c 比如
kali安装卡在simple-cdd不动?在右下角,有个小小的符号,找到网络适配器,然后断掉,很快就安装好了。
两种方式为button元素注册点击事件,this指向
两种方式 xff1b 第一种指向button xff0c 第二种 指向window
强化学习实战——Q learning 实现倒立摆
倒立摆参数以及数学模型 首先是写一个倒立摆的AGENT模型 pendulum env py import numpy as np import matplotlib pyplot as plt import matplotlib impor
dependencies.dependency
依赖包有两个 xff0c 根据最下一行的提示找到项目的pom xml文件找到依赖
Vue3---语法初探
目录 hello world 实现简易计时显示 反转字符串 显示隐藏 了解循环 了解双向绑定实现简易记事 设置鼠标悬停的文本 组件概念初探 xff0c 进行组件代码拆分 hello world 最原始形态 xff0c 找到 id 为 roo
MySQL实战解析底层---普通索引和唯一索引,应该怎么选择
目录 前言 查询过程 更新过程 change buffer 的使用场景 索引选择和实践 change buffer 和 redo log 前言 在不同的业务场景下 xff0c 应该选择普通索引 xff0c 还是唯一索引 xff1f 假设你在
准备离开:致消散的梦想
学到现在基本都是悲剧以前的队友现在大多放弃了初心以前的好学长现在摆烂和失败开学时的场景再也见不到了大一开学开启OJ xff0c 那是一个永远绚丽的夜晚不管是学长还是同学 xff0c 都在那时期待未来 xff0c 欲力竭以圆其说而不是现在的颓
MySQL实战解析底层---MySQL为什么有时候会选错索引
目录 前言 优化器的逻辑 索引选择异常和处理 前言 在 MySQL 中一张表其实是可以支持多个索引的但是你写 SQL 语句的时候 xff0c 并没有主动指定使用哪个索引也就是说 xff0c 使用哪个索引是由 MySQL 来确定的不知道你有没
二叉搜索树
目录 定义简介 查找结点 插入结点 删除结点 排序 二叉搜索树的效率 二叉搜索树的退化 二叉搜索树常见应用 定义简介 二叉搜索树 Binary Search Tree 满足以下条件 xff1a 1 对于根结点 xff0c 左子树中所有结点的
AVL 树
目录 介绍 结点高度 结点平衡因子 AVL 树旋转 右旋 左旋 先左后右 先右后左 旋转的选择 插入结点 删除结点 查找结点 AVL 树典型应用 介绍 在进行多次插入与删除操作后 xff0c 二叉搜索树可能会退化为链表此时所有操作的时间复杂
热门标签
statmodels
jquery16
redactorjs
uimotion
balana
googlevpc
rxtest
go114
qmetatype
watchr
plugman
ios30
serverfarm
mlgradle