漫画:什么是AVL树?(修订版)

简介: 而在AVL树当中,我们通过“平衡因子”来判断一颗二叉树是否符合高度平衡。到底什么是AVL树的平衡因子呢?对于AVL树的每一个结点,平衡因子是它的左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候,这颗二叉树才是一颗合格的AVL树。

640.png640.png640.png640.png640.png640.png640.png

 

 

————————————

640.png640.png640.png640.png640.png640.png640.png


在红黑树当中,我们通过红色结点和黑色结点作为辅助,来判断一颗二叉树是否相对平衡。

640.png

 

而在AVL树当中,我们通过“平衡因子”来判断一颗二叉树是否符合高度平衡。

 

到底什么是AVL树的平衡因子呢?



对于AVL树的每一个结点,平衡因子是它的左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候,这颗二叉树才是一颗合格的AVL树。

举个例子,下图就是一颗典型的AVL树,每个节点旁边都标注了平衡因子:

 

640.png

 

其中结点4的左子树高度是1,右子树不存在,所以该结点的平衡因子是1-0=1

结点7的左子树不存在,右子树高度是1,所以平衡因子是0-1=-1

所有的叶子结点,不存在左右子树,所以平衡因子都是0

640.png640.png640.png

上图原本是一个平衡的AVL树,当插入了新结点1时,父结点2的平衡因子变成了1,祖父结点4的平衡因子变成了2

此时,结点4的左右子树高度差超过了1,打破了AVL树的平衡。

那么,怎样才能重新恢复AVL的平衡呢?

之前讲解红黑树的时候,我们提到红黑树包括左旋转、右旋转、变色这三种操作。

AVL树不存在变色的问题,只有左旋转、右旋转这两种操作。

左旋转:

 

逆时针旋转AVL树的两个结点XY,使得父结点被自己的右孩子取代,而自己成为自己的左孩子。说起来有些绕,见下图(标号1,2,3的三角形,是结点XY的子树):

 640.png

图中,身为右孩子的Y取代了X的位置,而X变成了自己的左孩子。此为左旋转。

 

右旋转:

 

顺时针旋转AVL树的两个结点XY,使得父结点被自己的左孩子取代,而自己成为自己的右孩子。见下图:

 

640.png

图中,身为左孩子的Y取代了X的位置,而X变成了自己的右孩子。此为右旋转。 640.png640.png

 

1. 左左局面(LL

 

640.png

 

顾名思义,祖父结点A有一个左孩子结点B,而结点B又有一个左孩子结点C。标号1,2,3,4的三角形是各个结点的子树。

在这种局面下,我们以结点A为轴,进行右旋操作:



640.png

 

2. 右右局面(RR

 

 

 640.png

祖父结点A有一个右孩子结点B,而结点B又有一个右孩子结点C

在这种局面下,我们以结点A为轴,进行左旋操作:

 

640.png

 

3. 左右局面(LR

 

640.png

祖父结点A有一个左孩子结点B,而结点B又有一个右孩子结点C

在这种局面下,我们先以结点B为轴,进行左旋操作:

640.png

这样就转化成了左左局面。我们继续以结点A为轴,进行右旋操作:

 

640.png

 

4. 右左局面(RL

 640.png

祖父结点A有一个右孩子结点B,而结点B又有一个左孩子结点C

在这种局面下,我们先以结点B为轴,进行右旋操作:

 

640.png

这样就转化成了右右局面。我们继续以结点A为轴,进行左旋操作:

 

640.png640.png640.png

 

例子中,以结点4为根的子树出现了不平衡的情况。

不难看出,这个子树正好符合 “左左局面”。

于是,我们以结点4为轴,进行右旋操作:

 640.png


这样一来,这颗AVL树重新恢复了高度平衡。

640.png640.png640.png


如上图所示,在AVL树中删除了结点1,导致父节点2的平衡因子变为-2,打破了平衡。

此时,以结点2为根的子树正好形成了“右左局面”,于是我们首先以结点4为轴进行右旋:

 

640.png

然后以结点2为轴进行左旋:

 640.png

如此一来,AVL树重新恢复了高度平衡。

640.png640.png

相关文章
|
1月前
|
Java
手撸二叉树——AVL平衡二叉树
本文介绍了AVL平衡二叉树的基本概念和实现方法。首先回顾了二叉查找树在插入节点后的不平衡问题,然后详细讲解了四种旋转操作:左左单旋转、右右单旋转、左右双旋转和右左双旋转,以确保树的平衡。文章还提供了Java代码实现,包括节点插入、删除和平衡调整的具体方法。通过这些操作,AVL树能够保持较低的高度,从而提高查询性能。
25 0
|
6月前
|
存储 C++ 容器
c++的学习之路:26、AVL树
c++的学习之路:26、AVL树
49 0
|
4月前
|
C++
【C++】手撕AVL树(下)
【C++】手撕AVL树(下)
51 1
|
4月前
|
Java C++ Python
【C++】手撕AVL树(上)
【C++】手撕AVL树(上)
52 0
|
存储
手撕AVL树
手撕AVL树
52 0
|
6月前
|
存储 C++ 索引
『 C++ 』AVL树详解 ( 万字 )
『 C++ 』AVL树详解 ( 万字 )
|
C++ 容器
【C++进阶】五、AVL树
目录 前言 一、AVL树的概念 二、AVL树节点的定义 三、AVL树的插入 四、AVL树的旋转 4.1 左单旋 4.2 右单旋 4.3 左右双旋 4.4 右左双旋 五、AVL树的验证 六、AVL树的性能 七、完整代码
98 0
【C++进阶】五、AVL树
|
算法 Java
Java数据结构与算法分析(九)AVL树(平衡二叉树)
AVL(Adelson-Velskii 和 Landis)树是带有平衡条件的二叉查找树,又叫做平衡二叉树。在AVL树中任何节点的两个子树高度差最多为1,所以它又被称为高度平衡树。
110 0
|
存储 算法
漫画:什么是 “哈夫曼树” ?
哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明,这到底是一颗什么样的树呢? 刚才我们学习了树的带权路径长度(WPL),而哈夫曼树(Huffman Tree)是在叶子结点和权重确定的情况下,带权路径长度最小的二叉树,也被称为最优二叉树。 举个例子,给定权重分别为1,3,4,6,8的叶子结点,我们应当构建怎样的二叉树,才能保证其带权路径长度最小? 原则上,我们应该让权重小的叶子结点远离树根,权重大的叶子结点靠近树根。
325 0
漫画:什么是 “哈夫曼树” ?