00:00
同学们,我们来完成。最后一种情况就是删除有两颗指数的这种节点。那关于删除。有两颗指数的这个节点的思路,是不是前面我们已经分析过了,大概分成这么几步,第一步呢?第二步还是一样的。那么第三步,从target的右指数找到一个最小的节点,其实要找右子数的最小节点,它应该是从右指数一直往左边找,是不是这个道理,然后呢,用个临时变量把它保存起来,删除这个最小节点,并且呢,这个在重置,把最小节点的那个值重置,呃,付给我们target no.value这个事就结束了。好,那听起来听起来还是比较简单的,我们来写一写,那我现在先编写一个方法。我编写一个方法,这个方法干什么呢?这个方法完成两件事情。第一件事情。注意听这一句话啊,第一件事情干什么呢?就是返回我我我先把这个方法方法这个他的一个签名写出来。
01:08
Public。Delete。Right right。Mini。好,那到时候呢,我要求他给我传一个节点进来。那现在呢,我把这个方法的几个参数说一下,大家知知道这个方法要完成什么任务了?这个node呢,就是。你传入的这个节点,传入的这个节点。这个节点呢,是当作,当作什么呢?当注意听啊当作。新的就是当作,要当作一,当作一颗二叉,二叉。排序,排序数的根节点。根据岭。那么返回的是什么呢?返回的是注意听啊,返回的是以注意听以no为根节点的二叉排序数。
02:11
的最小节点的值。啊,有点绕,是不是有点绕,但是待会洗大家就不会呃,不会觉得很呃,很郁闷了。那它的功能其实就是要返回以no为根节,根节点的二叉排序数的最小节点的值。呃,但是呢,他同时还要完成删除这个节点,因为刚才我们不是讲了吗,还要把这个最小节点删除,因此他还有一个任务,就是还要干什么呢,我再写到这啊。第一个就是要返回这个值,第二第二个呢,还要删除,注意听还要删除这个删除以漏为根据点的二叉排序数的最小节点。
03:00
这个大家知道我在说什么没有好,那你写一下代码,你们就清楚了。首先我要用一个变量,临时的变量,先把它保存起来,比如说叫target或者叫临时的都可以啊,我要保存起来,保存起来的目的就是待会呢我需要返回这个值。好,现在我要干什么呢?循环的循环的查找,查找什么呀,着子节点。左。应该是这样子循环的,查找左节点。做界定。那么就会找到最小。最小值是不是,那我就写了啊Y循环。就一一一直找到他。一直找,找到他。往往左找一直找,那什么时候找呢,只要这个target。它的left,它不等于空。只要这个不等于空,我就一直向左找,就让target等于target,大家知道这句话是什么意思吗?
04:04
也就是说当这个while循环结束以后,我们这个target它就指向了以no为根节点的二叉排序数的这个最最小值了,因为他一直往左找嘛,假设你这个节点只有一颗,那就是那就是自自己了。明白我的意思吧,这句话大家一定要循环的查找,查找这个no的,嗯,查找这个左子节点。那么就会找到最小值,因为它一直往左边找,往左找直到左边没有,呃,直到左边。某一个节点为空,就退出,那这个时候target就指向了最小的节点,好,这时注意听这句话啊,这时这是什么呢?Target就指向。就指向。了最小节点,这个大家应该能理解,这个时候呢,我们就调用。Delete node,把这个最小节点的值拿进去。
05:03
啊,大家看这句话是不是挺简单的,Target not.value。删掉了。这个时候他给的一位子用它,这时呢,我们就删除这个最小节点。这点大家应该很好理解吧,因为我找到这个最小节点的,然后再把最小节点的值,呃,以这个值传进去,把它删掉,删掉完了干什么?返回不要忘了,因为这儿还要返回这个最小的。节点对应的值,那这个值其实刚才呢,这个漏我没有动过,因为我要我没有动,我是让他帮助我们在完成,因此呢,我现在用load,诶我想一想啊。他可能弄的不动哦,那这样子这样返回也可以。这样返回也可以,就像target.value也可以,对不对?那这样子的情况就是相当于这个漏洞呢,我没动它,就我我没去动它,我相当于做了一个辅助的节点来做这个事情一样的。
06:02
啊,一样的,没有任何问题,没有任何问题,好,那这样做完了以后,其实我们就已经完成了这个任务。是不是我们就已经完成这个任务了?那完成这个任务以后呢?下面我们就回到这段代码。是不是这种代码,那应该怎么写呢?其实代码就比较简单了,咱们可以这样写。调用刚才我们写的delete right mini,我们把这个值给它传进去,就是哪一个值呢,就是我们。呃,应该是这样写的,Target。点。Right。因为你要向右指数去找嘛,所以说我把。这个target节点的右子节点传给它,它就以右子节点节点为根节点完成一个任务,最后是不是返回了一个最小值啊,我就写到这了,迷。Value。这个就是它返回的最小值,大家能看懂吧。
07:02
那返回这个最小值过后不要忘了把这个最小值。付给我们这个target.load的value重置一下,这事就over了。这件事情就搞定了,看到没有?这事就搞定了,那么我们这边这个地方呢,其实还有一个思路,待会我再讲,如果你不愿意从右边找最小的,你也可以从左指数找最大的,思路也是一样。好,此时此刻我们就已经完成这个事情了,来,同学们,我们来测试一下。那打开。我们的这个代码我们直接来测试,现在呢,我们测试删除有两颗指数节点,我们删了一个呢,删七或者删三,删除三或者删删除十都可以。我现在给大家演示一个删除。删除七的吧,给大家直接演示删除七的bary tree short tree.delete77,它有。
08:00
两颗指数,那我一删,我们看效果,看看七有没有删掉。这时我们发现,七呢的确是被删除掉了。对吧,那现在我们再换一个节点。再换一个。再换哪一个节点呢?我们随便找一个吧,十十这个节点呢,它有两个子节点,相当于有两颗指数,好,我们30看看行不行,来走一个balance short tree delete,十。那么我们运行一把,看看十有没有被干掉,我们发现十呢的确也被干掉了,没有毛病吧,好的,那说明这个没有问题,没有问题的话呢,同学们,现在我们这个代码就。OK。整理一下我们二叉排序数讲解的内容,好,那二叉排序数我们讲了哪些内容呢?我们来简单的回顾和整理一下。二道排序述,我们是从这里开始讲解的,对吧?我们一边讲一边给大家整理一下。二招牌居数首先我们提出了一个需求。
09:03
对不对,我们说假如有这么一个序列,有有一个这么一个数数列,要求大家能够高效的对他进行对数据的解查询和。添加,那这个时候就引起我们思考,那思考的时候呢,首先我们提出了一些解决方案。我们提出的解决方案呢,先是提出了这么呃数组的方案。宿主这个方案呢,被我们否掉了,因为宿主呢,他对这个。呃,检索如果你没有在排序之前呢,没有他这个检索速度其实并不快。第二个呢,你如果即使是你排序了过后,你要往里面添加数据呢,也会涉及到数组的整体移动性能呢,也是有影响的,接着呢,我们尝试着去使用。面试。存储就表链表呢也有个问题,他添加和删除确实很快,但是它检索还是很慢的,因为它是从头一个一个比较,于是我们就提出二叉树这个概念,好,那就引出了我们二叉树,那于是就先给同学们说一下二叉树是个什么东西。
10:13
是这样子吧,我们就提出二叉树这个概念,那二叉树是什么呢?我们先对二叉树做了一个说明,二叉排序,二叉排序数呢,它的这个要求是任何一个非叶子节点。它的左子节点值要比当前的这个节点值要小,右子节点的值要比当前这个子大,如果说在某个特殊的情况下,你有相同的值呢,可以将这个节点放在左侧节点或者右子节点。啊。那针对这个情况呢,我们就。把刚才的这个数列对应的这个二叉。二叉排序,二叉排序数给他画了一遍,是这个图对不对。是这样一个图。
11:00
那大家呢,这时就对二叉排序数有个基本的认识,紧接着呢。我们就先给大家讲的是二叉排序数的一个便利,呃,创建和便利。是这样子的吧,我们先讲的是二叉排序数的创建,然后呢,再给他讲的是二叉排序数的便利,二叉排序数的便利呢的创建,你一定要按照二叉排序数的一个规则来做便利,其实就跟我们以前普通的二叉排序数的便利是一样的,我们这里用的是中序,为什么用中序呢?因为中序它刚好。对这个数组是一个有序的,就是便便利出来,对这个二排序数呢,刚好是个有序的,所以说我们是这样写的,那这里呢,有一些局部的代码,我们也放在这里。好,大家可以去参考啊,后面呢,我们我们汇总,再把所有的代码放在一起就可以了。把二叉排序数的创建和便利讲完了,我们又讲了什么呢?诶,我们又讲了二叉排序数的这一个删除,呃,大家可能会说,诶老师你二叉排序的添加没有讲创建就是添加明白吧啊,便利就是整个便利点查找也很简单了,查找这个我相信每个同学我便利都会查找,肯定没问题。删除是什么意思呢?删除这个地方情况稍微复杂一点,因为二叉排序数的删除呢,他必须要考虑到这么三种情况。
12:25
对,因为你在删除完了过后,你一定要保证它仍然是一棵二叉排序树,所以说这边就会有三种情况,一种情况是删除的是叶子节点,还有删除的是只有一颗指数的节点,还有一颗一个是删除有两颗指数的节点,是这样子的吧。诶,那么我们分别做了这个探讨,先是做了一个操作的操作的思路分析。思路分析,那么这个分析是不是我们是写在了这么一个文文档里边是吧,所以说我们针对这个删除呢,我们实际上是先做了分析,然后再动手的,那具体分析的这个流程我也给大家拿到这。
13:10
在哪里呢?其实就是我们这个表里面的东西,是不是,那我就拿过来了。分析呢,我就放在一个表格里面去,我写一下就是对删除节点的各种情况情况的一个思路分析。我就拿到这儿啊,偷个懒。那分析完毕以后,是不是我们就走代码了,那代码我们是怎么走的呢?我们先演示的是删除叶子节点,再删除演示,演示的是删除有一个。有一个子节点的节点,然后呢,再演示的是有两个子节点,或者叫两颗指数的这种节点,那么。我们就直接写完了,写完过后,最终这个代码呢,我就把它放在这里,这是我们最后代码,我给大家拿过来。小字儿。
14:01
好,下面呢,我们把这个稍稍微整理一下,这里就直接写啊,就是二叉排序数,排序数删除节点的代码。代码实现。代码实现,那我统一的就放在这一个章节,好吧,我就不分开写了,因为分开写太麻烦了,放这。那放到这呢,我这还有个作业需要同学们去做一下,最后呢,有个作业哪里呢,就是我希望同学们在老师的基础上呢,完成第二一种删除。这个有两个子节点的这个这个作业,那这个作业是这样要求的,同学们看。我写到这,这是一个作业练习。嗯,什么情什么情况呢?就是我们先前删除有两颗子节点的思路是从右子树找到最小的。是吧,那现在呢,我要求同学们完成从左指数,就是要求同学们从左指数找一个最大的,是不是也可以啊。
15:08
最大的也可以,所以说这个呢,同学们自己去完成就行了。OK。那关于这个作业呢,大家可以去考虑,呃,如果如果我们从左指数。左子数找一个,找到最大的。找到。找到。A、找到最大的一个节点。对吧,然后呢,然后按照前面的思路完成。前面的思路完成。
我来说两句