vlambda博客
学习文章列表

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?



—————  第二天  —————

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?



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

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?


漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?



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


漫画:什么是平衡二叉树?


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


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


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


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


漫画:什么是平衡二叉树?


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


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


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


漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?


漫画:什么是平衡二叉树?


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


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



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


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


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


左旋转:


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


漫画:什么是平衡二叉树?

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



右旋转:


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


漫画:什么是平衡二叉树?

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

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?



1. 左左局面(LL)


漫画:什么是平衡二叉树?


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


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


漫画:什么是平衡二叉树?


2. 右右局面(RR)


漫画:什么是平衡二叉树?


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


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



漫画:什么是平衡二叉树?


3. 左右局面(LR)


漫画:什么是平衡二叉树?


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


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


漫画:什么是平衡二叉树?


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


漫画:什么是平衡二叉树?


4. 右左局面(RL)


漫画:什么是平衡二叉树?


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


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


漫画:什么是平衡二叉树?


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


漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?


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


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


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


漫画:什么是平衡二叉树?


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


漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?


漫画:什么是平衡二叉树?


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


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


漫画:什么是平衡二叉树?


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


漫画:什么是平衡二叉树?


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

漫画:什么是平衡二叉树?

漫画:什么是平衡二叉树?


推荐阅读:




    
      
      
    
给个[在看],是对小灰最大的支持!