专栏首页程序员小灰漫画:什么是平衡二叉树?

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

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

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

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

而在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树重新恢复了高度平衡。

本文分享自微信公众号 - 程序员小灰(chengxuyuanxiaohui),作者:小灰

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:什么是红黑树?

    2017年,小灰曾经发布过一篇关于红黑树的漫画,当时由于时间仓促,部分知识点一带而过,并没有讲解得很细致全面。

    小灰
  • 漫画:什么是红黑树?(下篇)

    上周,我们初步介绍了红黑树存在的意义,以及红黑树的插入操作,没看过的小伙伴可以点击下面链接:

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

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

    小灰
  • 约瑟夫环 队列+链表

    设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编...

    attack
  • 数据结构 | 每日一练(39)

    ——老子

    闫小林
  • 红黑树

    每个结点不是红色就是黑色 不可能有连在一起的红色结点 根结点都是黑色 每个红色结点的两个子结点都是黑色 任一结点到其子树中每个叶子节点的路径都有相同数量...

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

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

    小灰
  • 30 张图带你彻底理解红黑树

    小吴正在写红黑树的相关系列文章,不过内容太多,动画做起来比较慢,大家可以先看一下这篇红黑树的介绍,内容很不错。

    五分钟学算法
  • 30 张图带你彻底理解红黑树

    本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难...

    智能算法
  • 红黑树(一):构建红黑树

    前两篇文章谈了B-Tree和B+Tree,它们属于多路平衡树,所有叶子结点都在同一层,除了这两种平衡树, 我们熟知的还有平衡二叉树和红黑树。这一篇文章就来看看如...

    每天学Java

扫码关注云+社区

领取腾讯云代金券