您现在的位置是:首页 > 正文

【数据结构】 平衡二叉数(AVL树)

2024-04-01 03:06:33阅读 2

案例

给你一个数列{1,2,3,4,5,6},要求创建一颗二叉排序树(BST), 并分析问题所在.

问题分析:

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

定义

平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树, 可以保证查询效率较高

有以特点它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树AVL替罪羊树Treap伸展树

上面的五个二叉树中,第一个不是平衡二叉树,其根结点的左子树高度为2,右子树高度为0;第二个是平衡二叉树;第三个不是平衡二叉树,其根结点的左子树高度为1,右子树高度为3;第三个不是平衡二叉树,其根结点的左子树高度为4,右子树高度为1;第五个是平衡二叉树。平衡二叉树是一种特殊的二叉排序树(平衡二叉树一定是二叉排序树,平衡二叉树不一定是二叉排序树)。

平衡因子:左子树的高度减去右子树的高度。由平衡二叉树的定义可知,平衡二叉树的平衡因子的取值只可能为0,1,-1.分别对应着左右子树等高,左子树比较高,右子树比较高。

平衡二叉树的调整 

如何将一棵不平衡的二叉树变成平衡二叉树(只讨论不平衡的是因为假如树是平衡的就不必我们进行处理)。平衡二叉树的失衡调整主要是通过旋转最小不平衡子树来实现的

什么是最小不平衡子树:从新插入的结点向上查找,以第一个平衡因子的绝对值超过1的结点为根的子树称为最小不平衡子数。也就是说,一颗平衡二叉树可能有有多棵子树同时失衡,这个时候只需要调整最小的不平衡子树,就能够将不平衡的树调整成平衡的树。

如图a中,结点2的左子树高度与右子树高度差值为2,结点3的左子树高度与右子树高度的差值也是2,所以 该二叉树同时存在两棵不平衡子树,以3为根的树是最小的不平衡子树。由于右边出现了不平衡,我们只需要以3为中心,将该最小不平衡树向左旋转,即可得到图b所示的平衡二叉树。

左旋就是将节点的右支往左拉,右子节点变成父节点,并把晋升之后多余的左子节点出让给降级节点的右子节点;

而右旋就是反过来,将节点的左支往右拉,左子节点变成了父节点,并把晋升之后多余的右子节点出让给降级节点的左子节点。

即左旋就是往左变换,右旋就是往右变换。不管是左旋还是右旋,旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。

左旋方法:

右旋方法:

2-3树

为了保证查找树的平衡性,我们需要一些灵活性,因此我们允许树的一个结点中保存多个值。我们可以将一颗标准的二叉排序树中的结点称为2-结点(含有一个值和两个子结点),左子结点的值都小于该结点的值,右子树现在引入3-结点,它含有两个键和三个子结点,右子结点的键都大于该结点的键。 一棵2-3查找树可以是一棵空树。

一刻完美平衡的2-3树是指所有的叶子结点都在同一层上,通常称2-3树就是指代完美平衡的2-3查找树。 

网站文章

  • Linux基础命令---comm

    comm      逐行比较两个已经排序过的文件。结果以3列显示:第1列显示只在file1出现的内容,第2列显示只在file2出现的内容,第3列显示同时出现的内容。      此命令的适用范围:RedHat、RHEL、Ubuntu、CentOS、SUSE、openSUSE、Fedora。 1、语法      comm [OPTION]... FILE1 FILE2  2...

    2024-04-01 03:05:52
  • 《数据库系统概论》 第十章 数据库恢复技术 热门推荐

    《数据库系统概论》 第十章 数据库恢复技术 热门推荐

    事务是一系列的数据库操作,是数据库应用程序的基本逻辑单元。事务处理(transaction processing)技术主要包括数据库恢复技术和并发控制技术。 10.1 事务的基本概念 事务:是用户定义的一个数据库操作序列,是一个不可分割的工作单位(原子性) 一般的,一个程序中被包含多个事务。如果用户没有显式的定义事务,则DBMS自动划分事务。 事务一般以BEGIN TRANSACTION...

    2024-04-01 03:05:45
  • Win10搭建Pyspark2.4.4+Pycharm开发环境(亲测可用)

    Win10搭建Pyspark2.4.4+Pycharm开发环境(亲测可用)

    Win10搭建Pyspark2.4.4+Pycharm开发环境(亲测可用),包含常见问题及解决方法

    2024-04-01 03:05:38
  • The web services enumeration components are not available

    The web services enumeration components are not available

    The web services enumeration components are not available Error Message:The web services enumeration components are not available. You need to reinstall Visual Stu...

    2024-04-01 03:05:30
  • 【华为机试 Python实现】HJ37 统计每个月兔子的总数

    有一种兔子,从出生后第3个月起每个月都生一只兔子,小兔子长到第三个月后每个月又生一只兔子。例子:假设一只兔子第3个月出生,那么它第5个月开始会每个月生一只兔子。 一月的时候有一只兔子,假如兔子都不死,问第n个月的兔子总数为多少?数据范围: 输入满足 1≤n≤31输入描述: 输入一个int型整数表示第n个月输出描述: 输出对应的兔子总数输入: 3输出: 2......

    2024-04-01 03:04:50
  • Hibernate对象生命周期

    hibernate对象生命周期对象三种状态  hibernate对象三种状态:1、瞬时态transient   new了一个对象,此时对象就是瞬时态   瞬时态对象和数据库记录没有对关系,和session没有关系。    2、持久态persistent   瞬时态对象执行save变化持久层   持久态对象和数据库记录存在对应关系,和session

    2024-04-01 03:04:43
  • 也谈一下Activiti工作流节点的自由跳转

    最近在搞openwebflow的工作流节点自由跳转功能,在网上看了一些资料,感觉不是很好,总结原因如下:直接手动调用SqlSession的操作,感觉会漏掉一些重要的初始化操作(如:启动新节点之后加载其...

    2024-04-01 03:04:35
  • 巨杉数据库再夺“广州独角兽”称号

    巨杉数据库再夺“广州独角兽”称号

    2019年6月14日,由广州市科学技术局指导、广州市科技创新企业协会、《快公司FastCompany》联合主办的2018年独角兽创新企业颁牌暨2019广州“发现独角兽”创新企业项目启动仪式在广东迎宾馆顺利举办。 巨杉数据库再获“独角兽”企业称号。2018年12月,广州市科创企业协会公示了 “独角兽”创新企业榜单遴选结果。榜单涵盖40家企业,覆盖大数据、云计算、信息技术、物联网、生物...

    2024-04-01 03:03:54
  • Spring 依赖注入的处理过程与 DependencyDescriptor 的说明

    Spring 依赖注入的处理过程与 DependencyDescriptor 的说明

    Spring 依赖注入处理的代码入口在DefaultListableBeanFactory#resolveDependency() 方法。该方法第一个参数DependencyDescriptor de...

    2024-04-01 03:03:47
  • 通俗易懂k8s——核心组件

    通俗易懂k8s——核心组件

    核心组件原理 —— pod 核心原理pod 是什么pod 也可以理解是一个容器,装的是 docker/containerd 创建的容器,也就是用来封装容器的一个容器;pod 是一个虚拟化分组, 有自己...

    2024-04-01 03:03:39