初识平衡二叉树-AVL

标签:修改   load   sub   重要   get   路径   区间   avl树   简单的   

前言

上一篇文章只是简单地认识下二叉树,并未提到它的缺陷。数据结构的好坏取决于时间复杂度,由于每次操作(插入、删除、查找)需要与节点比较来选择进入到左子树还是右子树,也就是说每次比较都会排除一些可能(选择左右其中一侧),当然了这是对于随机均匀分布的二叉树来说,它的时间复杂度是O(log2n),但是对于只有单向的左子树或右子树来说,它的时间复杂度就变成了O(n),每次操作都会从头到尾所有节点比较一遍。总的来说,二叉树的时间复杂度区间是在O(log2n) ~ O(n)之间,这完全取决于二叉树的结构!如图所示:

单向二叉树结构

随着单向二叉树越来越长,所消耗的时间也会越来越多,这已经跟单链表没有什么区别了。因此,为了解决单链表的情况,将时间复杂度降低至O(log2n),衍生出了平衡二叉树

平衡二叉树

通过上面的分析看出,只要将节点均匀分布在两侧即可完成目的,而这也正是平衡二叉树所要做的事,因此它要求任何节点的左右子树的高度相差不超过1,实际上就是计算同一层中最大的高度值与最小的高度值相差不超过1,解释下高度的含义:从叶子节点开始自底向上到指定节点的最长距离,叶子节点的高度为0,空树的高度为-1。对于AVL树来说,它只是平衡二叉树的其中一种,节点的左右子树高度差被称为平衡因子,如图所示:

平衡二叉树结构

图中左侧为平衡二叉树,每一层的高度差值都不会超过1,图中右侧中出现高度差值超过1,故非平衡二叉树。仔细观察下,图中左右两个的二叉树无非就差了一个节点6,可以将这个多余的节点看成是新插入的节点,是该操作导致了二叉树失去平衡,更严格来说,只要是修改了树的结构,都有可能导致平衡失调,而能修改树结构的操作只有删除与插入。那么该如何才能让它继续保持平衡呢?很容易想到,只要稍微移动下树的结构就能使之平衡,这样子的操作被称为旋转,分为单旋转双旋转。在想一想,图中右侧中左子树相对偏高,若是旋转的话应该将左子树的高度降低,相应的右子树也会增高,这样子就达到平衡了。

AVL树旋转

上面提到只有删除与插入会导致二叉树不平衡,这里就举插入来介绍平衡二叉树的几种旋转方式。插入的话无非就以下几种方式:

左左型

  • 插入到根节点的左子树的左子树上,称作左左型LL(右旋转)。该方式导致的不平衡是因为左子树上的节点增加了,所以旋转的话就应当将左子树的高度降低,而旋转的节点是插入的节点到根节点的路径上的节点都有可能旋转(这个很在编写代码中很关键),也就是说有可能旋转多次才能达到平衡,如图所示操作:

avl平衡二叉树结构-1

图中可见是节点7,我们知道向右旋转会导致左子树的高度降低,没错,旋转正确的话是使二叉树达到平衡。我们将节点7移动到根节点位置上,节点5、6紧随其后,而节点8变成了节点的右子树,节点9还是节点8的右子树,简单来说,随着某个节点的移动,其他节点也会相应的移动,这样子才能达到平衡。不知道你们发现没有,旋转过后,不仅符合二叉树的规则,同时也达到平衡,只不过根节点变化了,不过这丝毫不影响!这是比较简单的左左型LL,在来看另外一种情况:

avl平衡二叉树结构-2

此种情况比上面多了一个节点,不过这不是关键。我们发现节点X应该是比节点7大,而比节点8小,也就是说它可以当作节点7的右子树,也可以当作节点8的左子树,而随着节点7移动到根节点上,它已经有了节点5与节点8两个子节点,容不下第三个节点了,也就是说它已经做不了节点7的右子树了,那么这个时候节点X只能考虑去走另外一套方案了,让我称为节点8的左子树,所以最终旋转的结果如上图所示。理解了右旋转,左旋转也是一样的道理。

右右型

  • 插入到根节点的右子树的右子树上,称作右右型RR(左旋转)。该方式导致的不平衡是因为右子树上的节点增加了,所以旋转的话就应当将右子树的高度降低,如图所示:

avl平衡二叉树结构-3

图中可见是节点9导致了二叉树的不平衡,那么应该左旋转来降低右子树的高度。将节点9移动到根节点位置上,节点10、11紧随其后,而节点8变成了节点9的左子树,重点在于节点X,发现节点X比节点8大,而比节点9小,随着节点9的移动,它已经做不了节点9的左子树了,所以结果它成了节点8的右子树。跟上面的右旋转有点类似!

左右型

  • 插入到根节点的左子树的右子树上,称作左右型LR(左右旋转)。该方式的结构与上面的左左型稍微有点区别,因为最终插入的节点是落在了右子树上,所以首先应该先降低右子树的高度,应该左旋转,不过你会发现,随着右子树的移动,左子树的高度最终增加了,二叉树还是不平衡,不过不用担心,事情是往好的方向发展,你发现没有,左旋转后的结构与上面的左左型是一样的!也就是说只需要在向右旋转一次就能达到平衡,总共旋转了两次,所以称为左右旋转!如图所示:

avl平衡二叉树结构-4

我们知道若是直接移动节点7,最终还是不平衡,而咱们说从节点插入的地方到根节点的路径上都有可能需要旋转,那只有节点X了,那么应该通过左旋转来降低高度,不过随着节点X的移动,最终发现二叉树还是不平衡,不过你也应该发现了,这结构和左左型很像,所以最终还需要右旋转来达到平衡!

右左型

  • 插入到根节点的右子树的左子树上,称作右左型RL(右左旋转)。该方式的结构与上面的右右型有些区别,最终插入的节点是落在了左子树上,所以首先应该先降低左子树的高度,那么应该右旋转,同理,随着旋转一次后发现还是不平衡,不过结构倒是很像右右型,接下来的操作就跟右右型一样了,就不做多阐述了!如图所示:

avl平衡二叉树结构-5

这几种类型不难理解,只要记住哪边高度多大就旋转哪边,需要注意的事可能要旋转多次,这也很简单,发现旋转后还是不平衡在继续旋转即可。

平衡二叉树的设计与实现

掌握概念后,最重要的就是实战,我已经把代码写了一遍,不过中途是参考了别人的文章,这边也只是放出了代码图片,有兴趣的同学可以去github上观摩-avl平衡二叉树代码设计与实现

avl平衡二叉树结构代码设计

总结

平衡二叉树中的旋转较为复杂,最好能够结合场景去分析推敲,加油吧!

初识平衡二叉树-AVL

标签:修改   load   sub   重要   get   路径   区间   avl树   简单的   

原文地址:https://www.cnblogs.com/zlia/p/14161984.html

版权声明:完美者 发表于 2020-12-25 12:14:00。
转载请注明:初识平衡二叉树-AVL | 完美导航

暂无评论

暂无评论...