00:00
同学们,我们用代码的形式呢,来给大家。创建一棵平衡二叉树。各位同学,那么在讲这个平衡二叉树的时候呢,我们先借助一个数列,就是以前面这个数列就436578来构建一棵平衡二叉树。嗯,首先跟他讲构建一棵平衡二叉树呢,相对来说是还是有些难度的,就是说它这里,它这里面涉及到一个左左旋转,右旋转和双旋转的问题,就是左旋右旋双旋。嗯,在不同的情况下呢,我们会去考虑不同的旋转。不同的旋转,好,那现在呢,我就以一个实际的案例给各位分析,把什么叫做左旋转,左旋转呢?它是如果我们只使使用左旋转,那那它就属于单旋转了,大家看这里有个数数组数列,叫436578。
01:00
各位好,现在呢,我们先来做一个思路分析,思路分析完了过后,我们再用代码把这个左旋转实现一下。打开这里有一张图,这张图呢,我已经给各位朋友画好了。我们已经画好了,来看一下这张图是什么意思。首先同学们看。这有一个数列叫436578。如果说我们按照。按照以前的方式来构建一棵二叉排序树,或者叫二叉搜索树,那么它应该是这样建的,先放一个四,3比4小放在它的左子节点,6比4大放在右。然后呢,五放在这个节点。七放在六的右子节点,八放在七的右子节点,同学们可以看到,当我们创建好这一颗。二叉排序数过后呢,我们发现它一左边的这颗组指数。
02:02
左指数它的高度为一,而它右边这一棵指数,它的高度为几呢?为三,也就是说,此时此刻这一棵树已经不是我们所谓的平衡二叉树了。那这个时候我们会采用一个什么方案来处理呢?各位,我们会使用一个左旋转。何为左旋转,大家先不要去看下面的文字,这个文字呢,我已经给大家整整理了有六步,但是呢,你们先不要去看,大家先跟上我的思路,就说如果是这棵树,我们。怎么样让它变成一棵平衡二叉树呢?那这里面就因为你这边是我们的左指数,就说现在是我们的左左,我们的右指数对我们的右指数的高度较高,因此要产生左旋转,降低我们右子数的高度,明白我的意思吧,好,那现在具体来说应该怎么做呢?同学们跟上我的思路。
03:00
它的具体的步骤是这样子,先创建一个新的节点,这个新的节点呢,以当前这个节点的值。作为新节点的值,也就说大家要想象在我们当前这个节点就是指的这个是这个节点。对,那这个时候他会怎么做呢?他先创建一个节点,比如说这个节点是四。OK,说创建新的节点值等于当前根节点的值,根节点现在是四对不对,好创建好了第一步,第二步把新节点的左子数设置为当前节点的左子数,什么意思?就是让四指向三。理解吗?因为你三是。这个原先根节点的左指数,先让它使用它好下一步把新节点的右指数。哪个是新节点呢?就是这个节点右指数设置为当前节点的右指数的左指数。
04:00
那么你当前节点的右指数的左指数是不是它呀。是不是,那所以说就让四指向五理解哈,不要着急,一会会儿一会儿我们会看到这个效果,下面再第四一步,把当前节点的值换为右子节点的子,当前节点是不是这个,我们说当前这个根据点是它吧,把它换成右子节点的值,右子节点是不是六,于是把这个换成六。看清楚了啊。好。下一步,下一步。把当前节点的右子数设置为幼子数的幼子数,什么意思?就是把你这个当前节点的幼子数设置为右子数的幼子数,那相当于是指向了它。是不是样子,同学们?因为你的六呢移上去了。OK,最后一步,把当前节点的左指数设置为新的节点,也就是说让它在指向它。
05:02
同学们可以看到,此时此刻,我们通过这一个左旋转的六步操作,我们就得到了一棵什么树呢?我们就得到了这样一棵树,我给他画过来。我要换过来。六是我们新的根节点。好,六下面呢,有一个四。四下面有一个三和五,看清楚了,同学们,三五没问题啊,同学们,七下六下面有它的右子节点为七。七下面还有一个八,各位同学请看,这就是我们的新的平衡进行了左旋转过后得到的一颗平衡二叉树,为什么这是一棵平衡二叉树呢?大家有发现没有,首先它的节点并没有减少,它原先有五个节,原先有五个节点,现在哦,原先有六个节点,现在还是有六个节点。而且它仍然是什么呢?仍然是一棵二叉排序树,你看六这边都是比六小。
06:04
这边都比,都是比六大,同样是3比4小,5比4大,这边呢,8比7大,而且大家有没有发现此时此刻,此时此刻你们有没有发现它的右指数,就这这个指数它的高度已经变成了二,而它的呃,左刚才说左指数啊,说错了,左指数的高度变成了二而。这颗新的平衡二叉树的右子树的高度也等于二。平衡了。平衡了,对,那当然当然有同学说,那这个六呢,这个六看啊,其实他原先这个六还在,只是这个六呢,你看平衡过后,这个六已经它没有任何节点在指向它,因为这条线已经断掉了,所以说你原先这个六这个节点呢,会干什么呢。会被当做一个垃圾被回收。所以说最后这个六。这个六相当于移动上去上去了,原先这个六呢,这个节点就被销毁了。是这样子的吧,好,这个就是我们的操作过程,那么大家看这个是我们的原始树,这是我们的一个过程,最后得到的就是这个树,这个树,这一棵平衡二叉树,就是我这画的,看六指向四,四指向三和五,六右右指节点指向七,七指向八,那这还有一个六,原先这个六六节点怎么办呢?大家看这个六,这个节点其实已经没有任何引用指向它了,根据Java这个垃圾回收机制,当有一个对象没有任何引用指向的时候,这个节点就会被销毁,实际上你也访问不到它,因为我们在遍历一棵树的时候,我们本身也是从根节点开始便利,其实你看到六。
07:39
他虽然指向别人,但是没有,没有别人指向它,因此它就会被销毁,明白意思吧,好,同学们,这个就是左旋转的。一个操作步骤,大家看理解了吗?说的再直接一点,什么时候进行左旋转呢?就是当你的右指数的高度比你的左指数的高度要高的时候,我们发我们我们进行这个左旋转,左旋转的目的是要降低右指数的高度,是这意思吧。
08:09
好,那大家看这个理解了啊,如果同学们理解了,那现在呢,我就准备用代码给大家实现一把。给大给大家实现一下,先把这几个流程先看清楚,123456,好,关于这个左旋转的思路分析和图解呢,就给同学们先讲到这里。
我来说两句