00:00
好,同学们,我们再来看。一个双旋转的情况,那么同学们有没有发现就是前面的两个数列呢?我们进行一次单旋转。不管是左还是右,一次旋转就可以将这个非平衡二叉数转成平衡二速,对不对?但是在某些情况下呢,单旋转不能完成平衡二叉数的转换,比如说同学们看我现在呢,有这么一个数列。你们可以看到,如果我这个数列,或者说这个数轴,你发现用原先的代码,你可以看到并没有变成AV l数,我们来先看一下这个效果,然后待会呢再解决。好,同学们,我把这个注销。我把这个注销,我换成这样一个数组,各位同学请看。在于它,诶这地方。对,把它换一下。大家看这个时候呢,你们有没有发现我是十十一七六八九,跟他不一样,同学们看我现在这个代码没有做任何变化,我运行一把,当我运行完了过后,你会发现很奇怪的事情发生了什么样?你看树的高度为四,左指数的高度为一,而右指数的高度为三。
01:14
为什么呢?来,我们来分析一下他的问题所在,注意听。同学们注意听讲哈,那么他的问题呢,其实是在这个地方,我已经做了一个分析。看问题在哪里。同学们看。这个呢是我换成另外一个颜色,这个地方是我们原始的这个二条素,也就是说呃,如果我们没有旋转的时候呢,它它第一次填个十,然后这是七,这是十就是六是八,好,当他填九的时候,这就不平衡了。那这个时候其实它是满足什么条件呢?满足我们左边的这个指数的高度,它大于右边这个指数的高度,而且呢,已经大于一了,这时按理说我们应该符合右旋转的规则。
02:00
那如果是右旋转的话呢,它就变成了这样一棵树。大家有没有发现,当它旋转完了过后,你会非常奇怪的发现它仍然是一个。非平衡二叉树为什么会这样呢?同学们想你的右旋转。实际上最终是把这个。是吧,八和九挂到了我们的。这个。挂到我们新的这棵平衡二叉树的右边,但是你是八和九啊,问题就严,问题就没有得到解决,是这样子的吧,所以你做完了过后仍然是这么一一个非平衡二塔数,那么针对这个情况应该怎么解决呢?注意听。好,我把这个呢给大家画一下,你们就明白了。呃,这个时候其实是这样一个情况。我嗯,我看看怎么说大家应该容易理解一点,干脆这样子,我把这个图呢,给各位朋友放到我们这边好吧,放到这边大家应该就我这好好画一下,来同学们看一下。
03:01
对不对,我们就就放这,大家看这个时候我们之所以会出现这个情况的根本原因是什么?先把这个问题解决,呃,先把这个问题说出来,然后我们再说解决方案好不好,先说问题所在问题。问题分析,因为这个时候我们发现什么呢?就是当符合,当符合这个又。旋转又旋转的条件时,注意这是第一个,第二个当当什么呢?当这个符合右旋转条件的时候,如果它的左指数注意听。如果它的它的它的左指数的左指数的右指数高度大于大于什么呢?大于它的它的幼子数的高度。
04:02
高度你看这个时候是不是这样一个情况,就是它的左,就是它的左子数是这这颗这颗指数吧,这个指数呢,它的右子数。是二,而它这颗左指数的左指数的高度呢?是一,就符合这个条件,当它的左指数的右指数的高度大于它的。大于它的右子数的高度时,这个时候我们应该先干什么事情呢?需要先对注意听,先对当前这个节点注意听啊,当前这个节点,当前这个节点的。对,当前这个节点的。左左节点就是这个节点。这个节点进行什么呢?进行进行这个向左旋转,也就是先要向左旋转。
05:00
向左旋转,这个向左旋转的目的是要降低这个,呃,这个它的左指数的右指数的高度。先要进行向左旋转,然后,然后再。这先把这个写完啊,向左旋转。这个有有点绕,大家不要怕啊,我待会还要说的,把这个做完了以后再干什么呢,再对。再对,诶不要听了,再对当前节点,当前节点进行什么呢?向右旋转的操作,进行右旋转的操作即可。那这样子大家可能有点不太明白了,呃,怎么回事,我现在给他画一下,前面这个都不说了,现在已经满足向右旋转,那这个时候他也满足他的左指数,它的左指数的右指数的高度为二大于它的。右指数的高度大于它啊,这写错了,大于它的左指数,这写错了啊,不好意思。左指数就是它的右指数的高度大于它的左指数,它的左子数不不为一吗?对吧?诶这里呢,大家再看一下。
06:06
它现在它的它的左指数的右指数的高度为二,它的左指数的左指数左指数的左指数的高度为一,现在是不是满足这个条件了。是吧,在这种情况,我们需要先对这个当前节点的左节点,就是它进行一个。先对它进行一个什么呢?左旋转,左旋转会变成什么样子,同学们,来我们捋一捋,是不是先在这边建一个七。注意听啊,这个有点绕七,让这个七这个新节点指向。这个七这个节点的这个左,呃,左指数是这样子的吧,然后再干什么事情,同学们下一步该干什么事情呢?然后让这个七这个节点指向。这个新的这个节点指向当前这个节点的右指数的左结,呃,右指数的左指数是不是空了,也就这边是不用再指了,这事就做完了,然后该干什么事情让这个八。
07:07
就是让这个八这个纸替代。这个位置,然后让它的右指数指向这个九,然后让这个呃,当前节点的左指数指向这个七,这事就完了,那也也就是说经过我们这也当对当前这个节点的左节点进行一个旋转后呢,就变成这样一个数了,变成什么样个数呢?来再画一遍,变成十,注意听啊。八这个有点绕,同学们八七这七。六没问题吧?然后这边呃,这个十面变,然后这边呢,是什么呀,这边仍然是11好八下面还挂了一个什么八,下面还挂了一个九。大家现现在可以看到,呃,通过第三步这个操作呢,他是不是已经变成这个样子了。变成这样子过后再对当前节点,当前节点仍然是它。
08:02
以这个节点进行右旋转就可以操作,那么右旋转过后会变成什么样子呢?来,我们再画一条线。这个地方我换另外一个颜色,注意听啊,这个有点绕,同学们不要着急。呃,进行右旋转,应该怎么旋转,根据刚才老师讲的规则,应该怎么旋转?是不是我们先要去建一个新的节点,以当前节点这个值建新的节点是十?时先指向哪里呢?十的这个右右右指右指数应该指向这个11还记得吧。再让,再让什么,再让这个新的节点的左指数左左或者叫左节点指向当前这个节点的一,当前这个节点的左指数的右指数是不是就应该指向九啊。是不是这样讲的?对,没问题,然后把这个八它的左当前这个节点的左节点。左左左子节点这个值来替代这个八。
09:00
没问题吧,啊,替代替换它,然后让这个让什么让这个八就是当前节点的左止节点指向它左左子节点的左子节点。然后让这个把在它的右子,右子节点指向这个新的节点。是是这样子吧,同学们好,这样处理完了后,会得到一个什么样的数组呢?呃,什么样的一个数,这个这个数呢,就变这样的八,变成根节点,它的下面有一个十,十下面左边是九,注意听右边是11没问题吧,八下面是七。七的左边16就写完了,也就是说经过这样的一个操作呢,它就变成了这样一棵树,这个树大家看仍然是一棵二叉排序树,并且的确是平衡的。的确是平衡的。是不是这样子的好,这个呢,有有一点点绕啊,有一点绕,但是没有办法,必须给大家讲,那这个图我一定要给它保留起来,我先把这个图先截一下。
10:03
放到这里啊,因为有些同学可能需要看,我把这个图先留在这,待会儿呢,我需要给大家放到笔记里面去,好吧。好,呃,那么有了这个思路以后,同学们,那这个时候我们就不啰嗦了,就直接走代码。直接走代码打开,我们这个代码主要是在哪里写呢。也就是说主要我们是要在前面这个进行处理的时候来增加一段业务逻辑,哪里还是在爱的里面写,嗯,这不好找,我们还找到爱的方法,好在这里打开。嗯,也就是在这个条件,当它这个进行右旋转的时候呢,我们先要判断判断什么呀,刚才我是不是写了一句话,如果。诶,这是不是这句话,如果它的左子数的。就是在满足这个条件情况下,它左子数的。它的左指数的右指数的高度大于它的左指数的高度,在这种情况下,我们先要进行左旋转,然后再右旋转,是不是这样说的,那就把这个条件写清楚,呃,应应该怎么写呢?
11:12
应该怎么写呢?那就这样写的,如果left。对不对,你首先要left不等于空,我们才去做这个操作,不等于空的情况下,同时满足left对left。呃,点他的右。它的呃,它的,它的右子数对右子数的高度大于了,大于了它的。左指数的,左指数的呃,左指数的左指数的高度。在这种情况下呢,我们先要进行向左向什么呀,先。先对先对。这个当前节点的左节点,左节点其实也就是我们所说的左指数。
12:00
左节点有点绕啊,左节点也也就是我们所说的这个左,左指数是不是大的左指数先要进行什么旋转呢?先要进行左旋转。是不是要进行左旋转啊?左旋转应该怎么写?一定是注意啊,是当前节点的左节点进行左旋,左旋转也就是left的点什么呢?Left。这个大家能理解吧,然后再进行右旋转。这个旋转是针对当前节点进旋转的,明白吧,这个千万别搞错了,再对当前节点节点进行什么呢?进行这个右旋转。那如果这个条件不满足。那如果不满足的情况下呢,那说明什么问题?OK,那说明。那说明你这个就直接进行一个右旋转就可以了,是这是有直接进行这个右旋转。又旋转即可。对不对,那直接运用雄转,那就right rotten就可以了。
13:01
代码就写完,那同样你上面这个满足左旋转的时候,是不是也是一样的这个逻辑啊,是不是也要写一下啊,来各位跟上我的思路。跟上我的思路,呃,这个条件是右大于左对吧,右大大于左,如果相相等的情况下,那就那就无所谓啊,那就无所谓。啊好,那现在我们来写吧。我把这个条件。那这个条件这样写是没问题,那接着写吧。现在呢,如果如果他的又来写啊,如果他的幼子数看啊,就是如果他的柚子树。的什么呢?如果他的幼子数的。呃,我想想应该怎么写它的右指,右指数的左指数哈,应该是他的右指数的左指数的高度,如果大于大于它的。
14:04
呃,他的应该是什么呢?应该是。如果它的就是当前这个节点,它的右指数的左指数的高度大于它的右指数啊,它的右指数的。柚子数的什么呢?幼指数的高度,幼指数的高度。好,这个时候呢,我们需要先干什么呢?先先进行这个右旋转,右旋转再进行左旋转啊,当然右旋转是对谁进行右旋转呢?先进先对。先对先对他的右。右子节点或者叫右指数啊,右子节点。进行右旋转,然后再对,注意听啊,然后再对。当前节点节节点进行左旋转。
15:01
大家能绕过来吗?可能有些同学已经停停蒙圈了是吧?那我写一下,大家看看能不能看懂,首先right呢,肯定是不能为空,我们才去进行这样操度,并且还要满足就是它的右指数的左指数的高作大于它的右指数的右指数的高度,好,那这样就行了,那么就是。右指数的它的左左,左指数的高度na he。干什么呢?大于了,大于了对不对,大于了什么呢?它的幼子数的幼子数的高度。好在这种情况下呢,我们要进行这样一个处理。怎么处理呢?哎,就是刚才老师在这写的这段代码,相对它的右子节点,右子节点显示right是不是。第二什么呢?进行右旋转。Right rot,然后再对当前节点进行左旋转,待会就写完了,那还有一种情况就是如果说。
16:00
如果说。呃,如果什么呢,如果说你在这个条条条件不满足对吧,如果不满足的话呢,没有关系,那这个时候呢,你还干什么呢,你就直接,否则啊就直接。注意听这句话啊。直接。直接进行什么呢?进行这个左旋转就可以了,左旋转即可,那左旋转这直接写成left rot就行了,代白先写完了。那么大家写完这里面我们有一个风险,大家有发现我的代码有一个地方特别容易出问题。特别容容易出问题。什么出问题呢?就是。你如果这个条件满足的话,你把这个事情做完了,你把这个事情做完了,因为你来一次就处理一次,你千万不要在下面再去判断明白吧。也就是说,如果你这个条件满足,而且你已经处理了这地方,就马上。因为你你是加一个处理一个,如果你这不的话,它还往下走。
17:02
那就那就是非常危险的,说这个必须要。我不知道大家能不能理解这句话的意思,因为你想啊,你加一个加一个条件,你这做了处理,他已经平衡了,他一平衡过后,你又接着往下继续判断,那这个没有意义,一是没有意义,没准还发生其他的情况,是不是,所以说呢,这个呢,一定把它加上去发生一个,好,现在我把这个条件加,加上过后呢,我们再来玩一把,看看目前这个情况是不是一样,那么我们来验一下。如果说他真的没有问题,它就应该满足我们分析的这样一个情况,首先呢,整棵树的高度变成了三左边。左边这个左边这个指数呢应该是二,右边这个指数的高度也为二,而且根节点现在是八。是不是好,我们来玩一把,现在是不是跟我们想的一样呢?好,已经还是这个数据啊,我们玩一把不知道,如果有问题我们调一下。好,同学们可以看到完全的一样,看啊,树的高度为三,左指数为二,右指数为二,当前根节点为八,我们可以再验一下,就是,呃,有些同学可能还有点怀疑,就是那我们看一下八的八的这个左左节点是不是七,八的右右子节点是不是十,我们可以验一下啊。
18:20
因为因为这个地方呢,可能大家有有些这个怀疑嘛,我就给大家简单的点一下好,呃,我我就直接说啊,根节点的左。这样写。着子节点。左左节点吧,左子节点。好,左之间我们我们看看是是否能够拿到AV l。IVLIVL点翠,先把这个根据点拿到,再拿到它的。它的左左边这个。好,这个是不是组啊,如果没有没有什么问题的话,它应该输出的是,呃,多少呢?应该输出的是七。
19:04
应该输出是七,我们看看是不是七。好,我们发现的确是七,好,我们可以再验一下,呃,就是七下面这个是不是六呢?再看一下七下面是不是六,如果再来一个left,那么就应该是几啊,应该是六,看对不对,我验一下就可以了。好就是六,那如果说你再来一个就不行了啊,再来一个那就变空了,好就讲不去,我们再试一下它右边我就我就简单啊,它右边我们这个刚节点的右边这个节点呢,我们分析出来应该是十好看看是不是十。验一下,因为。因为验证的过,大家心里面就更更放心了嘛,十好,没有问题,十的左左边是九,右边是11好,我们再来印一下,十的左边是九。现在应该是九,对不对?各位同学应该是九,如果是九,说明我们这个分析对,的确是90的右边。
20:02
十的右边应该就是我们的11。是不是11啊,是11好正确,那如果你在这个基础上,你再来玩一个left,好,这个就应该是什么呀,是空。对不对,那就是这这个就是空,果然是空,好了同学们,那关于这个验证,老师就给大家说到这里。那么同学们注意,这个就是我们讲的这个双双旋转呢,是有一点难度的,但有点难度,希望同学们去好好的理解一下,尤其是我画的这个图,大家要去深刻的理解,就是说你一定要明白左旋转和右旋转的含义是什么,然后呢,你才有可能去理解我们这段代码,就是为什么要。这么去写,就是刚才我们说的爱的方法,为什么要这么去写啊,是有一点难度,但是还好,也不是说,也不说完全超出大家一个理解能力,对不对,就是这写的爱。爱的。这边这地方我们是怎么写的呢。
21:01
就是先判断,然后再进行相应的处理,那么就这样子,OK,同学们,那关于我们双旋转。关于我们avl数的双选者呢,就给同学们介绍到这里。
我来说两句