00:00
各位,我们把讲解的平衡二叉树的内容呢做一个小结。我们看看我们讲了哪些内容。平衡二叉数呢,也是AV l数对不对,我们是怎么引出来的,我们捋一下。首先,我们先提出了一个问题。啊,就说当我们去对一个数列进行呃,创建成二叉排序数的时候呢,它有可能存在这样一个问题,就是什么呢,它的左指数或者右指数他们不平衡。要么是左指数特别特别大,要么是右指数特别高,好在这种情况下呢,这就是我们一个问题所在,因此我们就提出了平衡二叉数的这个概念。好,这是。提出这个问题。是吧?同学们提出这个问题。当时呢,提问题的时候,我们也把它可能的,可能存存在的问题做了一个分析。捋到这里来。这是可能存在的问题的一个分析,大概呢有这么四点。
01:04
捋一捋。然后把这个问题分析完了,完了过后呢,我们就提出了平衡二叉处的这么一个概念。那对平衡二叉树我们做了一个基本的介绍,大概三点说了一下平衡二叉素是什么啊,是什么东西?首先我们可以看到平衡二叉树呢,它又叫平衡二叉搜索树,也被称为AV树,那从这地方可以看到,它首先是一棵二叉搜索树,或者叫做二叉排序树。对,他如果不是二叉搜索数,那这个就不能称其为平衡二叉数了,对不对。那么它有什么特点呢?第一个就是。它是一棵空树,它可以是一棵空树。或者是它的左右两个指数的高度差的绝对值不能超过一,如果它超过一,那就不是平衡二叉数了。OK,并且还要满足左右两颗指数都是平衡二叉树。
02:04
它的左指数和右指数也是平衡二叉数,OK,那么紧接着呢,我们举举了一个例子,让大家来看一下下面三个图案,哪一个是平衡二叉树,我们得出的结论是这个是。这个也是,这个呢,他就不是对不对,这是我们当时举的一个案例,引起大家的一个思考。当我们把这个问题说完了以后呢,我们就直接上代码了,我们就给他讲应用案例,用代码实现,还记得吧。好,这是它的一个应用案例,那么应用案例我首先给大家提出了一个要求,就是我们要干什么事,第二个呢,我们提出了一个思路,第三步我们用代码实现,那这个思路是怎么分析的呢?来这个时候因为时间关系,我直接就把我已经准备好这个图拿出来给他看了,也就是说。这个就是我们进行。左旋转的时候需要进行的操作。
03:02
对吧,我们先讲,因为我们先讲的是。左旋转嘛,对吧,先讲的是左旋转,好把这个稍微放大一点,大家也要看的清晰一点,那具体来说这个左旋转的代码是怎么处理的呢?打开这边。打开这边左旋转的核心代码,左旋转的核心代码,我们通过这个方案来找。这有一个叫做。叫做这个方法叫做na row rot,这个就是我们左旋转的一个步骤。那么我把这这个代码的片段呢,先给朋友们放到这,后面我们有个汇总。好,当我们把左旋转讲完以后呢,我们又提出还有一个右旋转的概念,对不对,那右旋转的概念呢,又是什么时候使用呢?就是当我们的。A,把这个写写清楚啊,当我们这边左左指数的高度比右指数的高度要大于一的时候,我们要进行右旋转,降低左子数的高度,是这样子吧,同学们好,这边仍然是如法炮制,先给同学们讲了一个右旋转的。
04:13
一个图,就是这个图。是这样子的,同学们好,先把它的一个过程给大家做了一个描述。放到这一栏。这是他的一个示意图。好,放这儿吧。这个示意图呢,大家应该也也能看的清楚,我把这个稍微放大一点啊,便于大家以后看,那么紧接着我们用代码实现了这个右旋转,那右旋转呢。它的核心代码在哪里呢?就是这个right rotate,就这段代码。好的,这是我们这一段的代码片段,我也给大家放这紧接着我们又提出一个新的问题,就是说你如果经过在某些情况下呢,你仅仅通过一个单选择是搞不定这个事的,就是你一次单选择是搞不定的,他需要。左右旋转配合,这个就叫双旋转。
05:02
双旋转OK,那这边就提出了这样一个问题。我把这个代码先给大家放到这来,我们提出了双旋转的概念。是吧,那首先我们提出的一个问题,提出这个问题,然后呢,我们对这个问题呢,做了一个分析,就是问题出在哪个地方,然后我们提出解决方案,最后代码实现是这样子的吧。好,那这个问题分析我是怎么给同学们分析出来的呢?其实各位同学,我们这个图就派上用场了。对吧,就是说如果你原先按照这种这个数列来走,如果你仅仅通过右旋转,其实只能拿到。这样这样一个二叉排序数,但是二叉排序数呢,你发现它仍然不是平衡的,因此呢,我们就分析当什么什么情况的时候,我们要进行先进行什么旋转,再进行什么旋转的操作,是这样的吧,同学们好,我把这个图给大家截过来。因为有有讲数据结构啊,同学们如果不画图,几乎是很难把这个。
06:04
讲清楚的。解决思路呢,就是其实就是上面这个图,我把这个步骤给大家解,解决一下,其实就是这个思路。问题问题解决的一个思路,其实按照这个步骤来解决就可以了,好具体来说就是这么几步对不对,那紧接着我们就把这个代码给大家做了一个实现,那具体来说这个代码呢,这次就是汇总的代码,我把整个啊同学们。双旋转其实没有一个单独的方法是配合使用的。那这个时候呢,我就这样子把整个代码统一给大家放到这面,这个也是我们最终最终代码就是汇总的代码,就是这样写,叫做AV l数。数的一个汇总代码。明白就是相当于说是一个完整代码吧。完整代码我写到这里,那么同学们要看的话呢,就看这一段代码就可以了。插出一个表格百搭码放进去,这代码量就稍微大一点哈,因为是把以前的那一部分代码也也拿过来的,但是你们知道双旋转和这个单旋转的区别,主要就是在这里加了一定的判断,好在哪里呢?我把这个大家看一下,就就这把核心代码给它标成一个出题蓝色。
07:21
核心代码就这。是不是就是这地方开始的?是吧,下面又有个条件。对,我们核心代码就是从这里开始的,这样的吧,同学们,然后呢,我把它标成一个粗体,再给一个蓝色,OK。好,同学们,这一部分就说到这,这有这个地方就是我们双旋转了,这边也使用双旋转。好同学们,那关于我们平衡二叉树它的讲解呢,就讲到这里,讲这里,OK,大家好好的理解理解一下,然后呢,把它。做一个深刻的了解,最后能够应用到我们项目里面去。
我来说两句