00:00
同学们,我们来实现一下这一个左旋转的过程,那大家看到左旋转整个这个操作呢,是按这个流程来写的,那现在我们先写这个方法,打开我们的eclipse eclipse左旋转这个方法我们写在哪里呢?各位同学,我们就写在这个节点里边,我们写在这,同学们。就写到最下边好吧。来,我们这儿写一个左旋转。做旋转的方法。那左旋转的方法怎么写呢?咱们就这样写了,Private。Private void void,然后我们叫left,旋转的意思,左旋转。那么怎么来做这个左旋转呢?我们刚才已经讲过,首先第一步我们是要创建新的这个节点,是不是已经分析过了?创建新的这个节点,这个节点呢,它是以当前这个根节点的值作为新的值,以用什么呢?以当前。
01:02
这个根节点,当前根节点,根节点的值啊为为创建的,那这句话就比较简单了,我们就六一个no。No node把什么放进去呢?那就是你当前这个值,因为待会我们是从这个root这个地方开始去进行旋转的,好,这时他返回来一个no,这个no就是我们刚才所说的new node没问题吧?第一个工作我们就做完了,想想我们前面讲的思路,第二句把新的节点,那这样子我们对照这个话啊,第二句把新的节点的左子数设置为当前节点的左指数,好,我们写上这句话,把什么呢?把新的这一一句一句一句一句的来啊,把新的。把新的节点。新的节点的着。
02:01
左指数左指数设置设置成当前这个节点的什么呀。左指数没问题吧,这个千万别写错了,写错到时间整个旋转就会发生大的问题,那就是new,一个ignorede点什么left等于left。因为你当前这个节点的左,呃,左子不就是ne吗。是不是加上下一步该干什么呢?下一步是把新的节点。的什么呀,右指数右指数设置成设置成什么?设置成当前节点的。这个又。右指数的左指数有点绕哈,左指数。是不是这样子的,你看我们这没没没写错啊,把新的节点的右指数设置为当前节点的右指数的左指数,那比较简单,这句话呢,应该这样写6NO。
03:09
点什么呢?Right,它等于什么呢?当前这个节点。的右指数的左指数这个。大家一定要理解是为什么啊,因为我刚才已经给大家演示这个思路分析了,这里我就代码实现就可以下一步该干什么了。好,下一步是把当前节点。把当前节点。的值,把当前节点的值换成。或者替换成都可以啊,替换。替替换。替换成什么呢?同学们替换成幼指数的。幼子数的子还记得吧?柚子数的子,呃,柚子,柚子又不是柚子,数柚应该是什么呀?右子节点的子,又子节点的子,就是这句话。
04:09
是不是这意思吧,把当前节点换成右子节点的子,那就是什么呢?那就是这样写的。轴,呃,那就写value,你当前这个节点的值等于什么呢?Right。别写错了,Right,跟上我的思路啊,大家想一想。是不是这个道理没有问题吧,这个也写完了,下一步不要忘了,还有一步把什么呢?还还要把当前节。点的右子数幼子数设置成,还记得是怎么写的吧,设置成柚子设置成幼。指数的右指数是这样子啊,就把当前节点的右指,右指数设置成当前节点的,应该这样写,当前节点的右指数的右指数,说白了就是让它跳过去,让你这个节点原先呢,它是指向这个呢,现在直接让它指向这个。
05:13
往往往下面挪一位,知道这意思吧,刚才也是这样分析的,那下面应该怎么写呢?这句话是不是应该是right?等于right.right有点绕啊,但是呃,也不是很难,最后一句话该干什么呢?把当前节点的。左指数左指数。左指数设置设呃当前节点的左子节点应该是也可以说是左指数对吧,也可以说是左指数,所以说写成左指数也没有没问题,左指数或者叫左子节点都一样,左子节点设置成什么呢?设置成新的这个节点完事了。新的节点。
06:01
好,这个过程就完事了,怎么写ne等于我们六的这个no。6NO,就是我们新的这个节点嘛,新的这个节点,好,同学们,这个就写完了。这个就写完了,那写完过后你。是不是应该测试一下,看看好不好用?那你什么时候来用这个左旋转呢?同学们是不是在添加的时候,我们发现这个高度发生变化,我们在做你调用它的话,调用它的时机应该是在添加或者添加节点的时候来判断在哪里写,应该在这。往下拉,是不是在我们这边添加完节点过后,我们这应该判断。判断什么呢?如果说在这里当当什么呢?当添加完一个节点后,如果如果什么呀,如果这一个条件满足了,就是我们所说的什么呢?幼这个有点不好说啊,幼指数的高度。
07:08
右指数的高度大比比左,左指数的高度,呃,大大一,嗯,大于一,就是这样子,你这样说吧,嗯,这样说我用过公式就好写了,右指数的高度减去左指数的高度的这个值,这个值它大于了一,是不是我们就要发生一个左旋转,是这样子吧,同学们左旋转。就可以了,那我把这个条件写进去,怎么写呢?就是你以这个节点为主,你的右边的高度减去了左边的这个高度,它大于了一,是这样的吗?同学们刚才是不是也是这样分析的,如果是这样一个条件满足。如果是这样一个条件满足,我们就要进行一个。旋转。我们就要一个旋转,那旋转的时候。
08:03
旋转的时候怎么旋转呢?怎么旋转呢?好,这里面是有一个,这里面是有一个规则的,大家看我把这个规则给他写出来,大家一下就明白了,来写上这句话,如果,如果right。因为你旋转其实也是有条件的是吧,如果你right就是你,你的这个右右子节点不等于空,并且还要满足什么呢?右子节点。对不对。因为你在这个过程要不停去操作,相当于说你右子节点。的。这个向右边右子节点的一个高度干什么呢?小于小于右子节点的。这个有点绕,同学慢慢来啊,Left的高度在这个条件满足的时候。将这个条件满足的时候,我们做件什么事情呢?好,这时我们需要先对。
09:06
先对谁进行旋转,先对右指数。右指数进行进行旋转。啊,进行旋转啊,那这个地方呢,我们得。还好像在这地方还有一个小问题。对吧,我们这还有个小问题,这样子吧,我们先。先这样子做右指数的高度,我们先这样子,先不考虑那么多,好,我们先不考虑那么多,我们上来过后直接就进行一个左旋转吧。看看这个情况能不能得到解决,因为后面的情况还还有很多其他情况,我们再逐一的考虑,先不要一下子考虑那么全,这个就是左旋转嘛。就是左旋转。是不是同学们这个就是左旋转对吧,我们看看现在情况是不是已经可以得到一个一个处理了,因为现在我们先先不要考虑那么多,现在就以这一个情况来来来讲解他,这时只需要进行一个左旋转。
10:08
以这个案例为例的话,只是进一个左旋转,我们来看看效果怎么样,来运行一把。来运行吧,好嗯,现在呢,因为目前我我在添加的时候,其实已经每次都在进行这个平衡处理了,所以说现在已经是处理了。在平衡处理过后,我们看这个数,这个高度是什么样子的,运行一下。好,同学们看,这个时候情况的确发生变化了,看树的高度为三,左指数的高度变成二了,右指数的高度也变成二了,这说明我们这个左旋转其实是生效的,对吧?但是我我要给大家讲哈,我们这里考虑的呢,比较简单。就说我们这方考虑的比较简单,实际上呢,后边还有一系一系列的情况等着我们去解决,那具体还有哪些问题呢?我们在下一个视频就是在产生右旋转的时候呢,再给大家回头还要说这个事情,好关于这一讲先给大家聊到这,大家好好理解一下。
我来说两句