玩转红黑树 (第二部分)平衡二叉树

玩转红黑树 (第二部分)平衡二叉树

平衡二叉树(AVL)

定义:它或者是一颗空树,或者具有每以下性质的二叉树:它的左子树和右子树的深度之差的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。

优点:平衡二叉树是特殊的二叉排序树,他的结点元素间存在着偏序关系。平衡二叉树是在二叉排序树(BST)上引入的,就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降,那么AVL就保持住了(BST)的最好时间复杂度O(logn)

存在的问题:在某些极端情况下,可能会出现只有左(右)树存在节点。如下图,这就类似于链表结构。为了避免这种极端的情况发生,所以需要将不平衡二叉树优化成平衡二叉树。那么如何才能在每次插入和删除的时候,一直保持平衡关系呢?本文将用最简单明了的方式进行图文讲解,"旋转"的奥秘。请继续往下翻~~

如何构建平衡二叉树

如何判断树不平衡了?

  • 平衡因子计算公式:左树高度 - 右树高度
  • 不平衡条件:平衡因子大于1

如下图所示。

  • 图1平衡因子为2,则说明不平衡。
  • 图2平衡因子为1,则说明平衡。
  • 图3平衡因子为1,则说明平衡
  • 图4平衡因子为2,则说明不平衡

对上面3种情况进行"旋转",使之成为平衡二叉树

敲黑板!!! 牢记平衡二叉树的基本规则,左边放小的,右边放大的

  1. 图一

这个旋转是不是很直观了呢~ 以⑨为圆心,⑩顺时针往下旋转(右旋转)。如果这都没看懂的话~ 建议出门往左!OK,我们继续往下

  1. 图二

还在想图二怎么旋转的,面壁思过3分钟!判断是否平衡:是否有负载因子大于等于2的!!

  1. 图三怎么旋转,才能使它平衡呢!

我们在旋转图一的时候,是不是感觉很轻松。将⑩右旋一次就达到平衡。那么,如果我们能够把图四也改变成图一的结构,那不就so easy了吗~~ 好的,恭喜你已经领悟到真谛了,请继续观看下图。 最后节点是以左节点结尾,并且中途没有断层过的结构,以下称之为LL型(left left简称)。如图一

如何旋转,才能达到上图效果呢?接着看下图

经过左旋之后,这不就是我们预期的LL型结构吗??那么,按照图一的方式,再次进行一个右旋即可达到平衡。接着看下图

END! 以上就是旋转的原理,无论树有多复杂,按照这种思路去进行重复旋转,最终就会得到一颗完美的平衡二叉树

上一章(树的基本认识)

下一章(玩转红黑树 (第三部分)使用java实现平衡二叉树(插入,旋转))

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×