什么是AVL平衡二叉树,AVL树有哪些特性?

AVL平衡二叉树

平衡二叉树也叫AVL(发明者名字简写),也属于二叉搜索树的一种,与其不同的是AVL通过机制保证其自身的平衡。

AVL树是最先发明的自平衡二叉查找树。

在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

AVL树的特性

AVL树本质上还是一棵二叉搜索树,它有以下特性:

  • 特性1: 对于任何一颗子树的root根结点而言,它的左子树任何节点的key一定比root小,而右子树任何节点的key 一定比root大;
  • 特性2:对于AVL树而言,其中任何子树仍然是AVL树;
  • 特性3:每个节点的左右子节点的高度之差的绝对值最多为1;

特性1表明,AVL 继承于 BST , 所以:

1.AVL本身首先是一棵BST 二叉搜索树。
2.AVL带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

在插入、删除树节点的时候,如果破坏了以上的原则,AVL树会自动进行调整使得以上三条原则仍然成立。

也就是说,AVL树,本质上是带了平衡功能的二叉查找树(二叉排序树,二叉搜索树)。

AVL树的平衡功能

举个例子,下左图为AVL树最长的2节点与最短的8节点高度差为1;

当插入一个新的节点后,根据上面第一条原则,它会出现在2节点的左子树,但这样一来就违反了原则3。

图片[1]-什么是AVL平衡二叉树,AVL树有哪些特性?-不念博客
例子

此时AVL树会通过节点的旋转进行进行平衡,

AVL调整的过程称之为左旋和右旋,

AVL平衡的调整过程

旋转之前,首先确定旋转支点(pivot): 这个旋转支点就是失去平衡这部分树,在自平衡之后的根节点,

平衡的调整过程,需要根据pivot它来进行旋转。

我们在学习AVL树的旋转时,不要将失衡问题扩大到整个树来看,这样会扰乱你的思路,

我们只关注失衡子树的根结点 及它的子节点和孙子节点即可。

事实上,AVL树的旋转,我们权且叫“AVL旋转”是有规律可循的,因为只要聚焦到失衡子树,然后进行左旋、右旋即可。

很多人在左旋和右旋有时候弄不明白,

其实左旋就是逆时针转,右旋是顺时针转

说明:本文会以pdf格式持续更新,更多最新尼恩3高pdf笔记,请从下面的链接获取:语雀 或者 码云

AVL子树失衡的四大场景

导致AVL失衡的场景就是有限的4个:

  • 左左结构失衡(LL型失衡)
  • 右右结构失衡(RR型失衡)
  • 左右结构失衡(LR型失衡)
  • 右左结构失衡(RL型失衡)

删除元素,也会导致AVL失衡,需要再平衡,但是原理和插入元素是类似的。

这里聚焦 介绍插入元素的平衡过程, 删除元素,不做介绍。

场景1: LL型失衡-左左结构失衡(右旋):

场景: 插入的元素在子树root的左侧不平衡元素的左侧

此时,以root的左儿为支点,也就是,左侧的不平衡元素为pivot(支点), 进行右旋

图片[2]-什么是AVL平衡二叉树,AVL树有哪些特性?-不念博客
右旋

来一个右旋的动画:

图片[3]-什么是AVL平衡二叉树,AVL树有哪些特性?-不念博客

右旋过程中,如果pivot有右子树,则作为 原root的 左子树, 保障AVL的特性1

记忆要点

尼恩备注记忆要点,LL型失衡怎么 平衡呢?

旋转的反向,与失衡的方向相反,

LL 型失衡,与左边 相反的方向, 是右边,所以是右旋

场景2 RR型失衡:右右结构失衡(左旋)

场景:插入的元素在子树root右侧的不平衡子树的右侧

此时,以root的右儿为支点,也就是,右侧的不平衡元素 为 pivot(支点), 进行左旋

图片[4]-什么是AVL平衡二叉树,AVL树有哪些特性?-不念博客
左旋

来一个左旋的动画:

图片[5]-什么是AVL平衡二叉树,AVL树有哪些特性?-不念博客

左旋过程中,如果pivot有左子树,则作为 原root的 右子树,

保障AVL的特性1,

记忆要点

尼恩备注记忆要点,RR型失衡怎么 平衡呢?

旋转的反向,与失衡的方向相反

RR 型失衡,与右边 相反的方向, 是左边,所以是左旋

场景3 LR型失衡:左右结构失衡(左旋+右旋):

场景: 插入的元素在左侧的不平衡元素的右侧

图片[6]-什么是AVL平衡二叉树,AVL树有哪些特性?-不念博客
左旋+右旋

记忆要点

尼恩备注记忆要点,LR型失衡怎么 平衡呢?

旋转的反向,与失衡的方向相反

LR型失衡,与只相反的方向是 RL,但是先旋转底部,再旋转顶部,RL进行次序颠倒,LR

所以, LR型失衡,旋转的方式,是先左旋, 再右旋

场景4 RL失衡: 右左结构 (右旋+左旋):

场景: 插入的元素在右侧的不平衡元素的左侧

图片[7]-什么是AVL平衡二叉树,AVL树有哪些特性?-不念博客
右旋+左旋

记忆要点

尼恩备注记忆要点,RL型失衡怎么 平衡呢?

旋转的反向,与失衡的方向相反

RL型失衡,与只相反的方向是 LR,但是先旋转底部,再旋转顶部,所以,LR进行次序颠倒,RL

最终, RL型失衡,旋转的方式,是先右旋, 再左旋

AVL树平衡总结

可见无论哪种情况的失衡,都可以通过旋转来调整。

不难看出,旋转在图上像是将pivot(支点)节点向上提(将它提升为root节点),而后两边的节点会物理的分布在新root节点的两边,

接下来按照AVL二叉树的要求:

左子树小于root,右子树大于root进行调整。

从图LL结构可以看出,当右旋时原来pivot(7)的右子树(8)会转变到原root点(9)的左子树处;

图片[8]-什么是AVL平衡二叉树,AVL树有哪些特性?-不念博客
LL结构

从图右右结构可见,当左旋时,原来pivot(18)的左子树会分布到原root点(9)的右子树。

图片[9]-什么是AVL平衡二叉树,AVL树有哪些特性?-不念博客
右右结构

对于左右结构和右左结构无非是经过多次旋转达到稳定,旋转的方式并没有区别,

AVL树本质上还是一棵二叉搜索树,它有以下特性:
1.本身首先是一棵二叉搜索树。
2.带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

也就是说,AVL树,本质上是带了平衡功能的二叉查找树(二叉排序树,二叉搜索树)。

AVL树的删除

删除的判断标准

  1. 要删除的节点是什么类型的节点?;
  2. 删除后是否会破坏平衡 ;

节点类型

  1. 叶子节点;
  2. 节点只有左子树或只有右子树 ;
  3. 既有左右子树都有。

处理的思路

  1. 当删除为叶子节点,则直接删除,并从父亲节点开始往上看,判断是否失衡;如果没有失衡,再判断父亲的父节点是否失衡,直到根节点。若失衡则判断失衡类型(LL、LR、RR、RL),再进行相应的调整。
  2. 删除的节点只有左子树或只有右子树,那么将节点删除,以左子树或右子树进行代替,并进行相应的平衡判断,若失衡则调整,一直到根节点 ;
  3. 删除的节点既有左子树又有右子树,找到其前驱或者后驱节点将其替换,再判断是否失衡,然后根据失衡情况调整,直到根节点。

说明:本文会以pdf格式持续更新,更多最新尼恩3高pdf笔记,请从下面的链接获取:语雀 或者 码云

常见AVL面试题

问:什么是AVL左旋和右旋?

加入节点后,左旋和右旋 ,维护AVL平衡性

右旋转

场景: 插入的元素在不平衡元素的左侧的左侧

x.right = y

y.left = xxx(原x.right)

   对节点y进行向右旋转操作,返回旋转后新的根节点x
            y                             x
           / \                          /   \
          x   T4     向右旋转 (y)        z     y
         / \       - - - - - - - ->    / \   / \
        z   T3                       T1  T2 T3 T4
       / \
     T1   T2

场景:插入的元素在不平衡元素的右侧的右侧

// 向左旋转过程

x.left = y;

y.right =(原x.left )

对节点y进行向左旋转操作,返回旋转后新的根节点x
        y                             x
      /  \                          /   \
     T1   x      向左旋转 (y)       y     z
         / \   - - - - - - - ->   / \   / \
       T2  z                     T1 T2 T3 T4
          / \
         T3 T4

AVL树的问题

既然AVL树可以保证二叉树的平衡,这就意味着AVL搜索的时候,它最坏情况的时间复杂度O(logn) ,要低于普通二叉树BST和链表的最坏情况O(n)。

那么HashMap直接使用AVL树来替换链表就好了,为什么选择用红黑树呢?

原因是:

由于AVL树必须保证左右子树平衡,Max(最大树高-最小树高) <= 1,

所以在插入的时候很容易出现不平衡的情况,一旦这样,就需要进行旋转以求达到平衡。

正是由于这种严格的平衡条件,导致AVL需要花大量时间在调整上,故AVL树一般使用场景在于查询场景, 而不是 增加删除 频繁的场景。

红黑树(rbt)做了什么优化呢?

红黑树(rbt)继承了AVL可自平衡的优点,

同时, 红黑树(rbt)在查询速率和平衡调整中寻找平衡,放宽了树的平衡条件,从而可以用于 增加删除 频繁的场景。

在实际应用中,红黑树的使用要多得多。

© 版权声明
THE END