<small id='9PLMZ'></small> <noframes id='qzml4U8uZ0'>

  • <tfoot id='tMIpW'></tfoot>

      <legend id='qORJWAZ'><style id='uRWA5PEvD3'><dir id='4nB2bcJyk'><q id='5Ani'></q></dir></style></legend>
      <i id='zUokVg'><tr id='gl5VpcFTa0'><dt id='wWsD0'><q id='gK4LI8'><span id='N1kcy7dT'><b id='4Gux'><form id='ATQ6mfSvyB'><ins id='pRwS6I'></ins><ul id='slGkhTf'></ul><sub id='piVQ7EB'></sub></form><legend id='QmWsuEb'></legend><bdo id='v8sQfAY'><pre id='onwy8'><center id='s80q'></center></pre></bdo></b><th id='MdIQt0jgx'></th></span></q></dt></tr></i><div id='15I9X'><tfoot id='LhEyz'></tfoot><dl id='JmARu9i'><fieldset id='I6umrwa'></fieldset></dl></div>

          <bdo id='OLbGRQ9ck'></bdo><ul id='vXqxh'></ul>

          1. <li id='dnxUfFjX'></li>
            登陆

            数据结构+算法(第11篇)玩平衡二叉树就像跷跷板相同简略!

            admin 2019-07-07 180人围观 ,发现0个评论



            点击上方“Java研制军团”,挑选“置顶大众号”

            关键时刻,第一时刻送达!

            阅览本文需求5分钟


            导言

            在上一篇《无死角“盘”它!二分查找树》中提到了:平衡二叉树的意图便是使得均匀查找长度最短。那么这儿就引出两个问题:

            1. 什么是平衡二叉树?

            2. 为什么平衡二叉树的均匀查找长度最短?

            3. 怎么将非平衡二叉树调整成平衡二叉树?

            1. 平衡二叉树是什么鬼?

            满意如下两个条件的二叉树称为“平衡二叉树”:

            1. 首要它得是二分查找树

            2. 然后它的左右子树的高度相差不超越1

            图1 平衡二叉树

            图2 非平衡二叉树

            图1便是一棵平衡二叉树,而图2不是平衡二叉树。

            在图2中,关于值为9的节点,它的左子树为空,高度为0,右子树高度为3,两者相差3,不满意平衡二叉树界说的第二条规矩。


            2. 怎么证明平衡二叉树的均匀查找长度最短?

            首要研讨一下平衡二叉树与非平衡二叉树的联系。

            图3表明的是一棵平衡二叉树,与它对应的恣意一棵非平衡二叉树都能够重复依照如下方法改换而来——在保持二分查找树的前提下,从高度较小的子树中取出一个节点A,刺进到高度较大的子树中——如图4所示。

            图3 平衡二叉树与非平衡二叉树的转化

            图4 平衡二叉树与非平衡二叉树的转化

            接下来用反证法来证明:

            假定平衡二叉树的均匀查找长度L并不是最短的,那么必定存在一棵非平衡二叉树的均匀查找长度L'<L (出题1)

            对应到上面的图示便是:

            图3的平衡二叉树的均匀查找长度L>图4的非平衡二叉树的均匀查找长度L'(假定1)

            假定1其实是出题1的充分条件,也便是说:只需假定1为真,出题1必为真。

            图3的节点总数=图4的节点总数,设为N;

            设节点A在图3中的查找长度(从根节点到A所需求的比较次数)为La,在图4中的查找长度为La’,则依据均匀查查长度的界说

            均匀查找长度=每个节点的查找长度之和/节点总数

            得到:

            明显上式与前面的假定1对立,然后证明了平衡二叉树的均匀查找长度最短。


            3. 怎么将非平衡二叉树调整成平衡二叉树?

            朴素的主意便是:遍历每个节点,查看它的左右子树高度,若高度之差超越1,设法交流一些节点的方位,使得该方位左右子树新的高度差缩减到1以内。

            这儿牵扯出3个问题:

            1. 遍历的方向:自顶向下仍是自底向上?

            2. 遍历的时分怎么方便地获取左右子树的高度?

            3. 怎么交流节点的方位,使得新的高度差在1以内?

            关于问题1,假如你细心研讨过笔者前几篇文章的话——《神力加身!动态编程》《史上最猛之递归屠龙奥义》——那么你很简单得出结论:

            两个方向都能够:自顶向上的话,写递归式算法;自底向上的话,写非递归式算法。

            这儿的“顶”指的是二叉树的根节点,“底”指的是二叉树的尾节点。

            关于问题2,取决于问题1选用哪种方法——假如选用递归式算法,那么在递归的时分,也顺便把高度递归核算了;假如选用非递归式,那么就在自底向上归并的时分,动态核算高度。

            问题3才是真实的新鲜问题。图5和图6别离描绘了一般状况。

            图5

            图6

            为了处理这个“新鲜问题”,咱们先来看一个引理:

            引理12.1

            1. 由于恣意非叶子节点A,它的值都比其右孩子B的值小,所以它能够变成B的左孩子。这样改换之后,A、A的左子树下降,B、B的右子树上升,高度差变小。

            2. 由于恣意非叶子节点A,它的值都比其左孩子C的值大,所以它能够变成C的右孩子。这样改换之后,A、A的右子树下降,B、B的左子树上升,高度差变小。

            图7

            图8

            上述的改换是不是很像一种“旋转”:)

            那么是不是这样“旋转”之后,调整就OK了呢?答案是否定的。

            看看下面这个比如:

            图9

            图9中,B节点一开端的左子树高度比其右子树大,即:

            H(B.Left)=H(B.Right)+∆h (式1)

            “旋转”调整后,B的左子树变成A的右子树,A变成B的左孩子,设高度相关于节点的函数为H,则:

            H(A)=Max(H(B.Left), H(A.Left))+1
            ≥H(B.Left)数据结构+算法(第11篇)玩平衡二叉树就像跷跷板相同简略!+1 (式2)

            将式1代入式2可得:

            H(A)≥H(B.Right)+∆h+1
            =H(B.Right)+∆H (式3)

            当∆h=1时,∆H=2。

            此刻H(A)≥H(B.Right)+2,这意味着“旋转”后,B节点的左子树高度与右子树高度相差超越1!

            形似“旋转”对这种状况不凑效了,怎么办呢?

            先来剖析一下不凑效的根因究竟是什么。

            从图9能够看出,作为A节点的右孩子,从一开端,B节点的左子树就比其右子树高了一个头,这个是导致后边旋转不凑效的根因。所以很自然地想到:

            在旋转前,先把B节点的左子树高度下降或许把右子树高度升高。

            那么怎么完成上述方针呢?咱们能使用的仍然是引理12.1:

            先将B节点的左子树打开

            图10

            再对打开的子树做一次旋转:

            图11

            经过以上两步就达成了把原始B节点方位(现在是D节点)的左子树高度下降的意图。

            至此就转化成了了解的老问题。再做一次旋转便能够完全调整成平衡二叉树了:

            对称地,咱们能够用相似的过程来调整下图的非平衡二叉树:

            图13

            过程一(子树煮饺子打开):

            图14

            过程二(一次旋转):

            图15

            过程三(二次旋转):

            综上所述,自顶向下的、单向链表存储式、递归型平衡二叉树调整算法如下:

            为了节约篇幅,自底向上的、单向链表存储式、非递归型平衡二叉树调整算法和自底向上的、数数据结构+算法(第11篇)玩平衡二叉树就像跷跷板相同简略!组存储式、非递归型平衡二叉树调整算法放在下一篇文章里独自列示。


            4. 平衡二叉树的节点刺进算法

            首要平衡二叉树实质是二分查找树,所以刺进新节点时,可遵从《无死角“盘”它!二分查找树》中的节点刺进算法;

            可是平衡二叉树仍是特别的二分查找树,它还要满意左右子树高度相差不超越1的要求。当依照上面的算法刺进新节点之后,可能会不满意这个要求,因而要进行调整。调整算法仍然是章节3介绍的旋转调整算法。


            5. 平衡二叉树的节点删去算法

            首要平衡二叉树实质是二分查找树,所以删去节点时,可遵从《无死角“盘”它!二分查找树》中的节点删去算法;

            可是平衡二叉树仍是特别的二分查找树,它还要满意左右子树高度相差不超越1的要求。当依照上面的算法删去节点之后,可能会不满意这个要求,因而要进行调整。调整算法仍然是章节3介绍的旋转调整算法。


            完毕


            博主还有很优异的技能交流群,许多技能大拿,CTO,活跃度百分八十以上。问题解答百分之90以上。加博主老友后回复【加群 】 ,然后答复技能问题,答对者才干进入,博其他广告主和商勿扰进群介绍当然也会有一些学习资源,群里直接回复资源介绍

            原创系列


            数据结构+算法(第10篇)叉堆“功夫熊猫”的速成之路

            数据结构+算法(第09篇):菜鸟也能“种”好二叉树!

            数据结构+算法(第08篇):史上最猛之递归屠龙奥义

            数据结构+算法(第07篇),动态编程!黄袍加身!

            算法+数据结构(第06篇):再不会“降维冲击”你就出了!

            算法+数据结构(第5篇):小白也能玩转数组和链表啦!

            算法+数据解构(第04篇),空间复杂度你真的懂了吗数据结构+算法(第11篇)玩平衡二叉树就像跷跷板相同简略!?

            数据结构+算法(第03篇)KO!大O--时刻复杂度

            算法+数据结构(第02篇)玩扫雷便是优化算法

            算法+数据结构(第01篇)走下神坛吧!算法



            是不是很棒!共享一下吧,小伙伴们!


            请关注微信公众号
            微信二维码
            不容错过
            Powered By Z-BlogPHP