00:00
下面我们接着来看一下平衡二叉树的。向右旋转,那向向右旋转又是一个什么情况呢?我们仍然看一个实际的案例,各位同学看这里呢有一个数列。十十二八九七六。那么如果我们用这个数列来形成一棵二叉排序树,那么会出现一个什么情况呢?大家看我这里有张图片,我们打开看一下。同学看。同学们看。如果按照这样一个情况来说的话呢,我们第一个十就在这儿12。它的右子节点八,它的左子节点九,它的它挂在八的右子节点下面,七挂在八的左止节点下面,六挂在七的左止节点下面,那同学们有没有发现这时又出现一个另外一个情况,就是它的左子数的高度为三,而它的右指数的高度。
01:02
为一这样呢,又不是一棵平衡二叉树,那这个时候呢,我们发现谁的高度高呢?显然是左指数的高度高于右指数的高度,那这个时候我们就形形成一个向右旋转,向右旋转的目目目的呢是要降低左指数的高度,从而达到一个平衡,那同学们,我们来看一下它的具体的步骤。具体步骤是这样子的,首先第一步仍然是以当前这个节点,当然这个我们肯定是从root节点开始进行这个处理的,对吧?以当前这个节点来进行处理,怎么做呢?同学们看。它首先创建一个新的节点6NO1,这个时候当建节点是十,那创建一个新的节点,比如说就是十放到这了啊同学们。第一步搞定,第二步把新的节点的右指数设置为当前节点的右指数,也就是把十指向12,因为你当前节点的右指数就是指向12的嘛。
02:06
这是第二步,第三步,把新的节点的左指数设置为当前节点的左指数的右指数,什么意思?左指数的右指数,也就是让十指向九。明白我的意思吧,让十指向九,再下一步。把当前节点的值换成左子节点的值,当前节点值是十,换成左子节点的值是八,把这个八往上移动。好,这个地方形成它了,再下一步。把当前节点的左指数设置为左指数的,左指数说白了就是怎样,它其实就是要把把这个节点抛出去。抛出去,因为我八已经上移了,我移动到新的这个根节点了,明白我的意思吧,好,此时此刻,此时此刻,最后一步把当前节点的右指数设置为新的节点。只用它。
03:00
好,同学们,当这样处理完毕过后,你们有没有发现把这个节点,原先这个节点就已经拿掉了,最后形成了一个什么样的节点,这什么样的一个?什么样的一棵这个二叉树呢?变成这样子了,八在最上面。八下面指向了一个十,没有问题吧,同学们,十的左子节点为九,十的右子节点为12,没问题。八的左子节点是七。七的着止,着止节点为六。没有了,因为这个酒呢,被移动到我们的柚子树了,那也也就是说现在仍然是一棵平衡的二叉树。是不是它降低了原先左指数的高度,由三降为二,而我们的右指数的高度呢?由一增长到了二,这样就平衡。平衡,这就是我们的这么一个操作,那原先这个八呢,大家看原先这个吧,是因为没有不会再有任何引用指向它,它也会成为一个垃圾节点被回收,这个就是我们所谓的右旋转的一个流程,其实它很跟我们左左旋转一比较你就知道了,那同学们我们用代码给大家跑一遍好不好?
04:19
写上我们的代码,代码就在哪写呢,各位,我们就直接写在。写在哪里?我们原先是在这儿写的。网上吧,写到上边去吧。这个是左旋转,下面呢,我们写右旋转。右右旋转好,右旋转这一次呢,我就不写那么多注释了,直接写代码了,同学们,那怎么写就是right。Roate。Right。Rotate,好,那这是我们接着往下做。呃,首先是创建一个新的节点,对不对。No是以当前这个节点的值作为新的节点。
05:03
没有问题吧?同学们好,那同样我们在这写上一个名称叫new no。New node没有问题,同学们好,第一步做完第二一步我们该做什么事情呢?好让来新的这个节点。新的节点的。新的节点的right。它的右子节点指向。当前这个节点的右子节点就不行,不说那么多了啊六。新的节点的左止节,呃,左子节点,左子节点指向哪里呢?指向当前这个节点的左指,左指节点的右子节点。好,这个就写完,紧接着我们继续再写。把这个值改了,把当前这个节点的值改成什么呢?改成它左子节点的这个值,是不是刚才已经说过这个事了,然后再让当前这个节点的左子节点指向它的。
06:07
当前节点左子节点的左子节点好,然后让当前这个节点的右子节点指向新的这个节点完事的代码。这个注释我就不写了,同学们好,现在呢,我们把这个代码来玩一遍,那先做一个测试,各位同学先做一个测试。呃,那比如说我们把这个数组测试数组换成另外一个。换成刚才我们做测试的这个玩意儿,走一个R等于,那刚才我们进行分析的这个数组呢,是这么几个数据。对不对,它会出现一个左指数比右指数要要高,绝对是要高两大于一的这么一个情况,是这样子吧,同学们好格式化一下。那这个时候呢,假如我们没有对右旋转做处理,那这个时候这个高度同学们可以看一下是个什么情况。
07:04
是个什么情况,也就是说目前这个高度呢,在你没有处理的时候,其实他就是刚才我们分析出来的这个情况。怎么把这个图。关掉了呢。好,那就是应该是整棵树的高度为四,它的左子树的高度为三,右子树的高度为一,是这样的吧,同学们好,现在呢,我给大家跑一下,验证一下这个结果。好,同学们,我们看到的确三左指数的高度为三,右指数的高度为一。因为你现在没有做这个处理好,现在呢,我们把刚才这一个右旋转的逻辑加到我们这个代码里面去,就能解决问题,那在哪加呢?在哪加呢?在肯定是在添加的时候加,呃,添加我在这边来找,这有有时候有点不好找,对不对,在这找爱。好在这个方法里边,在这个方法里面呢,我们再加一个条件,加一个怎样的条件呢?OK,就是当添加完,添加完一个节点后,如果什么呢?诶,如果出现了左子数的高度。
08:14
对,减去我们右指数的高度,它的这个差值呢,大于了一。则什么呢?右旋转是这样子吧,同学们右旋转OK,那现在我们把这个条件写上去,你肯定要这个条件满足,你才进行这个右旋转,就是左指数的高度减去右指数的高度怎么样大于一。在大于一的情况下呢,我们就进行右旋转。进行这个右旋转走一个。各位右旋人就是right rotten好,同学们,现在呢,我们处理完毕了,处理完毕我们再来运行,看一下情况如何,现在呢,理论上说这个高度变成三,而这两边都应该是二就对了,是这样的吧,运行一把。好,我们看一下这个结果跟我们想的完全一样,而且可以判断当前旋转完了过后这个根节点,这个根节点就是就是八而不是十了,我们也可以再验证一下当前根节点是不是这样子的,来输一下。
09:15
我们再把根节点给各位同学打出来,当前的根节点等于加起来好AV l这个tree get我们的root,所以啊,这个应该目前应该是几啊,应该是八。运行我们可以看到的确是八说明的确跟我们想的一样进行旋转了,好同学们,那这段代码呢,我们就给大家讲了,讲了一下我们的这个右旋转,并且呢,进行进行了一个测试,好关于右旋转先给各位同学讲到这里。
我来说两句