平衡二叉树

简介:

前面我写了一篇二叉排序树,最后我们提到提高二叉排序树的查找效率是让二叉树的形状均衡,所以就引入了平衡二叉树。

特点:

  • 一种特殊类型的二叉排序树

  • 所有结点的左、右子树深度之差的绝对值≤1

  • 左右子树是平衡二叉树;

平衡因子:该结点左子树和右子数的高度差

任意一个结点的平衡因子只能取:-1、0或1;如果树中任意一个结点的平衡因子的绝对值大于1,则这棵二叉树就失去平衡,不再是AVL树;

对于一棵有n个结点的AVL树,其高度保持在O(log2n)数量级,ASL也保持在O(log2n)量级。

这里写图片描述

如果在一棵AVL树中插入一个新结点,就有可能造成失衡,此时必须重新调整树的结构,使之恢复平衡。我们称调整平衡过程为平衡旋转

调整方法:找到最小不平衡子树,可将重新平衡的范围局限于这棵子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各个结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。

最小不平衡子树:离插入结点最近且平衡因子绝对值超过1的祖先结点,以该结点为根的子树称为最小不平衡子树。

假设最小不平衡子树的根结点为A,则失去平衡后进行调整的规律可归纳为以下四种情况。

  • LL平衡旋转

  • RR平衡旋转

  • LR平衡旋转

  • RL平衡旋转

1)LL平衡旋转:

若在A的左子树的左子树插入结点,使A的平衡因子从1增加到2,需要进行一次向右顺时针旋转(以B为旋转轴)
这里写图片描述

这里写图片描述

2)RR平衡旋转:

若在A的右子树上插入结点,使A的平衡因子从-1
增加至-2,需要进行一次逆时针旋转(以B为旋转轴)

这里写图片描述

这里写图片描述

3)LR平衡旋转:

若在A的左子树的右子树上插入结点,使A的平衡因子从1增加到2,需要先进行逆时针旋转,再顺时针旋转。(以插入的结点

目录
相关文章
|
缓存 前端开发 Java
nacos常见问题之开启鉴权后客户端报403升级版本如何解决
Nacos是阿里云开源的服务发现和配置管理平台,用于构建动态微服务应用架构;本汇总针对Nacos在实际应用中用户常遇到的问题进行了归纳和解答,旨在帮助开发者和运维人员高效解决使用Nacos时的各类疑难杂症。
2354 0
|
定位技术
阿里研究员玄难:如何做电商业务中台
2016 ATF阿里技术论坛于4月15日在清华大学举办,主旨是阐述阿里对世界创新做出的贡献。会上阿里业务平台事业部&淘宝基础平台技术部负责人玄难阐释了淘宝经历13年的发展中,业务平台从零到有,同时又逐步演进为业务中台。
41112 0
有哪些CAD软件支持(国产操作系统)麒麟操作系统
CAD梦想画图是由成都梦想凯德科技自主研发的轻量级CAD软件,专为国产操作系统如麒麟、统信设计。支持AutoCAD所有版本的dwg二维图纸,具备精准显示、测量、标注、绘图修改、文字查找及批注等功能,操作流畅,无需安装字体。用户可通过应用商店轻松安装,适合新手和专业人士使用。
|
8月前
|
机器学习/深度学习 人工智能 芯片
【AI系统】谷歌 TPU v4 与光路交换
TPU v4 是谷歌在 TPU v3 发布四年后推出的最新一代 AI 加速器,采用了 7nm 工艺,MXU 数量翻倍,内存容量和带宽显著提升。TPU v4 引入了 Sparse Core 以优化稀疏计算,首次采用了 3D Torus 互联方式,通过 Palomar 光路开关芯片减少系统延迟和功耗。TPU v4 Pod 实现了 1.126 Exaflops 的 BF16 峰值算力,展现了谷歌在大规模并行计算领域的突破。然而,TPU v4 也面临着系统成熟度低、拓扑僵硬和负载均衡问题等挑战。
377 0
|
缓存 Java 网络安全
Nacos报错问题之获取配置文件的时候报错如何解决
Nacos是一个开源的、易于部署的动态服务发现、配置管理和服务管理平台,旨在帮助微服务架构下的应用进行快速配置更新和服务治理;在实际运用中,用户可能会遇到各种报错,本合集将常见的Nacos报错问题进行归纳和解答,以便使用者能够快速定位和解决这些问题。
1773 1
|
监控 Java Spring
Spring Cloud Turbine(集群监控)
简介: Turbine是聚合服务器发送事件流数据的一个工具,Hystrix的监控中,只能监控单个节点,实际生产中都为集群,因此可以通过Turbine来监控集群下Hystrix的metrics情况Turbine的github地址:https://github.com/Netflix/Turbine 使用场景 在复杂的分布式系统中,相同服务的结点经常需要部署上百甚至上千个,很多时候,运维人员希望能够把相同服务的节点状态以一个整体集群的形式展现出来,这样可以更好的把握整个系统的状态。
4448 0
|
SQL 存储 JSON
MySQL执行请求报错 Error: Row size too large (>8126)
最近遇到一个业务问题,在执行一个大的业务查询时会抛出异常报错,所以今天就总结一下 MySQL执行请求报错 Row size too large (>8126) 报错的相关问题。
|
存储 传感器 消息中间件
基于阿里云IoT组件搭建车联网基础平台
IoT在汽车行业企业中的应用多为车联网,车联网的搭建往往需要软件、硬件、通信等多方面的技术基础设施。阿里云IoT组件可以快速帮助企业解决相关平台搭建问题,帮助企业将精力更多的聚焦到业务本身的开发上去。
3461 2
基于阿里云IoT组件搭建车联网基础平台
LXJ
|
存储 Windows
无影云电脑评测
无影云电脑评测
LXJ
1087 0
无影云电脑评测