00:00
下面我们用代码来逐一的实现这个平衡二叉树,嗯,大家有没有发现在我们整个这个分析的过程中。在我们整个这个分析过程中,这个高度就是它的左指数的高度和它的右指数的高度是一个非常关键的。呃,判断标准,也就是说你什么时候发生旋转。什么时候发生旋转,并不是说你加入一个值你就发生旋转,是不是因为只有满足它的。左指数和右指数高度的差值的绝对值是大于一的时候,我们才去进行这个左旋转或者是右旋转,是不是?那么同学们,那既然如此,是不是我们首先要完成第一件事情,就是能够统计出。一棵树的高度还能够统计出这棵树的左子树的高度和它的右子树的高度,这几个方法是特别核心的,大家知道我在说什么吧?
01:02
也就是说我们现在必须完成第一件事情来写看写,就说我们首先要把一棵树的高度,还有这棵树的左子树和右子,右子数的高度能够计算出来,那同学们,我们现在开始写代码。我们这个地方就取个名叫AV l,没问题吧,同学们。好的,那现在呢,我们取个名字。取个类AV l tree。DEMO。啊,OK,那现在写好了以后呢,我们现在首先有一些东西,我们是可以复用的,不用。全部重写,是不是这个漏的节点就是大家看我们在写。我们在写二叉排序数的时候,其实很多方法呢,我们并不需要完全重写,比如说这个漏节点几乎就可以拿来用。我把这个录的几点先拿过来,同学们跟上我的思路。把这个漏的节点拿过来,拿过来过后呢,我要在这个node节点上边增加新的方法干什么呢?我要写这这么几个方法要返回。
02:11
注意听返回当前节点,这个节当前点的高度,就说你给我一个节点,我能够把这个节点的它这个节点的高度就是它当然应该是准确的讲是返回以当前这个节点为根节点,根节点的这棵树的高度这样说啊,以该节点。该节点。该节点为根节点,根节点的这棵树的高度能理解树的高度。好的,那我这就写完了哈,写完过后呢,下面呢,我们就来写,写出这个方法,Public返回一个int,那我叫had。对不对,然后怎么写这个方法呢?其实特别的简单,没有大家想的那么难,就return return什么呢?
03:07
N的高度是不是同学们数的高度是不是就就是应该是什么呀?是它的左指数和右指数里面比较大的那个值。是不是也就是说它应该返回左指数和右指数里面比较大的,因此呢,我想这样写,大家看能不能看懂max.ma。好,这个A呢,我这样写,大家看到没有,如果left等于空。打一个问号。它等于空吗?如果它等于空,我就返回零。是不是否则呢,否则我让他递归的去进行一个计算,就left head。是不是这边就能够统计出它的这个主子数,就是它下面的主子数,然后呢,再再去比如果它的right等于空。对不对,和前面一样的道理,零,然后呢,向right na点。
04:06
是不是这个道理,但是要加一个一,为什么加一呢?因为你这个地方只是统计出这个节点的左指数右指数的那个最大值,那你本身还你本身是不是你本身这个节点要算一层,所以说要加一,这就写完了。大家看能看懂吧,这边就是这个地方,就是返回该节点的就是哪个节点呢?你给我的那个节点对吧,你给我的这个数其实就是按照这个节点来统计的嘛,你给我的。就是这个漏,你你你统计的时候,我我把这个节点用这个节点来来调用。这个节点的它的nap就左指数的高度,这是它的右指数的高度,返回它最大的。那个字再加上一,因为它本身自己还要占一层,写完了,写完过后呢,同学们,我们紧接着再写干什么呢?返回左指数的,左指数的高度,这个就比较好写了,怎么写呢?Public int ne hi he。
05:11
这个方法咱怎么写呢?好,这样写,如果left。他等于空。说明呢,诶这个高度它的左子数的高度就应该是啥呀零。是这样子吧A,否则怎么样呢?否则诶我就这样写了,我就用left调用它的he就可以了。这还特不是已经写好了吗?这是左指数的高度,我们再写返回,对返回右指数的。几个叫柚子树。柚子树的高度。那么右子数的高度呢?跟刚才其实很像,就这样写right hi。走怎么写呢,如果说它的右指数。为空,对不对?那么我们就返回一个零。
06:04
否则我们就用柚子树。又,诶,这写错了。就是right,点它的height就返回它的右子数的高度就可以了。OK,代码写完,这边就是返回右指数的,呃,左指数这边是返回右指数高度,这边是返回以这个节点以就是返回当前节点的节点的高度,以该节点为根节点的数的高度。啊,那这样写,返回这样写啊。返回什么呢?返回以该节点为根,节点的竖的高度大家应该能看懂,现在呢,我们来测试一下这两个方法,这三个方法写的对不对?来,各位同学,我们来玩一把。我们来玩一把,怎么写呢?我们就以这个数组为例,同学们看啊。因为啊,对,我们还还有这个数,我忘写了创建AV l tree。
07:00
那我就写了class AV l这个。这棵树,这个。AV l这个萃呢,萃AV l萃它其实跟我们前面的前面写的这棵二叉排序树其实很像,只是我们要增加功能嘛,因此呢,我可以把原先这个代码拷贝过来。大家看能不能理解啊,好,我现在从从这开始拷贝。一直往下拉。啊,一直往下拉,拉到什么地方呢,拉到这。理解啊。他该有的,就是说我们AV l数只是在。只是在这个就是平衡二叉树的基础上增加一个功能嘛,对不对。那所以说他原先的代码,其实我是可以复用的,我就粘过来了。没问题吧,你看粘过来呢,也没有什么,没有什么问题,只是把这个名字呢,我们改了一下,把这个代码咱们格式化一下,好看一点。
08:03
对不对,好看一点好,现在呢,我们把这个数组给它写出来,我们刚才说的这个数组是怎样的一个数组呢。就是同学们看到的这个数组。对,同学们看一下啊,不着急,这个一步一步来就行了,这个是我们准备利用这个数组来构建一棵树啊,这个地方怎么又来一个节点,不要它。好,那下一步我们是不是就创建。创建一个。创建一个什么样的对象?AV l,这个tree对象很简单,六一个AV l。是不是啊,同学们。好,我们拿到这个萃,拿到萃和萃以后,拿到这个萃以后,是不是我们要构建叫添加节点,添加节点,那添加节点显然我仍然用原先写的这个for循环I小于R点单没问题吧,同学们I加加写完,那加的时候显然就用原先写的一个方法叫艾,现在我们还没有去,我们现在还没有进行进行这个旋转操作啊。
09:13
我们还按以前的方式在走的。因为待会儿呢,我们要改变过后才能看出效果,好给他一个I值。给他一个I字,好,同学们这这样就创建好了,创建好了过后呢,我们便利一把,中续便利来走一个。走一个system,把我们当前建的这个数。显示出来,这叫中序遍历,那么中序遍历调用哪个方法呢?就是AV l这个数点它的。中序遍历方法,我们先来看看代码有没有问题运行。好,我们可以看到代码呢,是012345,诶这个怎么会这样子呢?012345是不是运行错了呀。
10:00
找一个。012345,这个就呃说错了,不好意思,这地方应该是取的A位AR里面的I,这样才对,对不对,同学们不着急写一下就改一下就行了,345678正确,那现在呢,我们主要的目的啊,想去测试一下我们刚才写的这个方法,哪个方法呢?一个是求以传入的这个节点,这个节点为根,节点的竖的高度。对吧,然后呢,我们还有一个就是求这一颗一个节点左指数的高度和它的右指数的高度,我们测一下。来我们测一测,因为待会儿呢,我们只有通过这个方法才能才能够证明我们写的这个平衡就旋转操作到底有没有效,OK,那我写一句话。在没有平衡,在没有旋转之前,或者在没有。在。没有做旋做旋转之前,我们或者说在没有做平衡处理之前。
11:06
平衡。平衡处理前情况是什么样子的呢?我们来走一把,我们来走一把,好,各位同学,我打出当前这棵树的高度,那这棵树的高度呢?AV l AV l tree。我得到它的根节点,再调用它的height,这个就是它的。树的高度,OK,写到这里。竖的高度没有问题吧,同学们,我运行一把,它应该返回几呢?诶,这个不对,我们看看哪里有问题,竖的高度get它的height,我们看这里。我们看哪里有有问题,我们先定位到这个方法去。我们先定位到这个方法去,同学们看一下。好,这个地方怎么写成哈西扣了呢?啊,这个是不对的,这个地方是写的不对的,怎么调成这个方法了,点它的什么呢?Height啊不好意思改一下就可以了。
12:09
是害的,不是哈西扣,怎么写成哈西扣了再来执行一下,如果不出什么问题的话,大家想,其实你们都知道,目前这个数的高度应该是四,如果不出问题的话,它应该返回四。运行时我们发现的确树的高度是四,没有问题吧,同学们是四好,现在呢,我们来统计当前这个没有平衡处理的这棵树,它的左指数的高度和右指数的高度。树的镯子树。对着指着指数的高度。左指数它的左子数的高度应该是怎样的呢?同学们看,那就应该是这样写。点它的left height,它的右指数的高度呢?来,我们也写下来右指数的高度。右。
13:00
右诶写到这里右指数的高度,那右指数的高度呢,我们也来测一下点什么呢?Right。还那如果不出什么问题的话,它的左指数的高度应该是等于一,右指数的高度应该等于三,这个是一,这个是三,上面这个是四来运行,我们可以看到这个结果呢,我们想的一样,一个是四,一个是一,一个三,对不对,所以说大家看此时此刻,左指数和右指数高度的差值其实已经是二了,超过一,因此我们要进行。这个左旋转进处理。因为为什么是左旋转,是因为是你的右指数的高度你大于别人吗。是不是你比你你是高的嘛,所以说我们要进行这个。左旋转,那么左旋转的代码是应该怎么写呢?各位同学,左旋转的整个这个方案其实就按照我们刚才写的六步将其实现就可以了。其实也并不难,那一会呢,我们就把这个代码给大家实现一下。
我来说两句