00:00
删除这个稍微有点麻烦啊,咱们看看删除。删除我们现在必须要考虑,你不能说说哈老师,我们要比如我们要删除十,你把那些书面干掉,那这个肯定就不对了。啊,这个就肯定不行的,来我们看一看二叉排序数的删除情况比较复杂。其实二叉数排序删除都比较复杂,那这个二叉排序数更复杂是在于你必须要保证你删除完了过后,它仍然是一颗。二差倍序数是吧?因为3万过家不对了,那就不行,比如说现在我们考虑三种情况,第一种就是它删除的是叶子节点,比如说二五九十二。这些呢是呃,叶子节点,还有一种情况是删除只有一颗指数的节点,比如一一是不是只有一颗指数。它下面啊,只有一个一个节点就是二,还有一种删除有两颗指数的节点,比如三和十,你看包括企业是。
01:00
当然我也也也有可能把棋干掉,对不对。那就是说,假设我们删除的是这样七这个节点。或者是三这个节点,或者是十这个节点。那么怎么解决?我们现在一个一个一个讲,就先先有这三种情况都要考虑,而且这三种情况他删除的时候还真的不太一样。那么我们就来一个一个的说,我们先来看第一个情况,叫删除叶子节点,我们先说思路。我先把这个写到这边来。好,同样我们我们在这边把他的一个思路给大家捋一捋,这是我的需求。就是。这是我们一个需求。这是我们需求,我给大家来一个底色,这样大家看起来比较清楚一点。好,这是我的一个需求,那么我们要删除的一个数,大家看一下目前这个二是不是我已经加进去了,说这个数呢,目前长的样子应该是这个样儿的。
02:04
我把这个呢也给大家放在XR表。好,同学们,来来,我们来看看这个四应该怎么删啊。应该怎么算?我们先来看这个删除叶子节点的这种需求。失落。嗯,同学们,同学们看,如果我们要删除的是二。各位,你要删除一个这个节点,首先你要明白。我们目前这个二叉排序数是单向的。既然是单向的,大家都知道,一定要找到它这个待删除节点的负节点才能干掉它,对不对,所以你这个地方不要脱离这个前提,所以第一个你要要心里明白,就是说第一个我们的。我们的这个二叉排序数是什么呢?是单向的。单项。
03:01
那既然是单向的呢,我们就必须要去。完成这样一个操作,就是需要在删除。删除时找到找到带就是找到这个,找到这个删除。删除节点的负节点。是这意思吧,所以我们这个思路基本上就已经有了第一步。首先我们要第一步先要找到这个要删除的节点。为什么呢?因为你要删除的节点如果都没有,你肯定就没法删嘛,所以我们第一步先要干什么呢?先检索。先检索到被。先检索到这个待删除的啊,要要删除的吧,要删除的这个节点。这个时候就有可能有两种结果,一个是有,一个是没有。对吧,如果没有是不是就直接。退出去了。好,这边就有两种可能。
04:00
第一种可能就是没有找到。就退出了。如果有。好,如果有的话呢,我们继续往下走。如果我们找到了啊,最近。如果我们找到了,找到要删除的节点了,删除的节点则需要找到。要。需要找到要该节点的该节点的负节点。还要考虑这个节点,假设没有负节点怎么办?比如说你删除七。他就没有负极点。对吧,那这个事你想怎么弄好,我们先把这个,因为现在哦,对,现在我还没不需要考虑,因为现在我考虑是子节点,现在哦,对还不需要,暂时不需要考虑这个东西。啊就是,但是删除还是一样的,就是你在这还不需要考虑它有没有负极点,它一定都都有负极点,因为它是叶子节点,叶子,叶子节点是不是都都有负极点是吧?叶子节点都负点好,然后呢,这个第三步,第三步就删除。
05:10
第三步就删除就可以了,三部曲啊,第一步先找到要删除的节点。第二步,找到要删除节点的附近点。好,第三步删除。删除该节点,删除该节点是要通过什么呢?删除该节点就行了,删除该节点好,我们三部曲。上不去,那现在我们就要开始写代码了。三部曲,那我们先写第一个,首先你要给我提供一个。查找某个节点的方法是不是这个这个要有就是我这写的像这个方法。你看我这写的有search。这个方法还有一个就是search parent这个方法,还有一个就是DD的方法,我们来写一写。好,那就找到这个banner tree啊,就是short tree,我们来写一下啊。
06:02
现在哪写呢?就在这儿写。我们先写一个叫做查找,查找,查找某个节点。啊,当然你是根据什么来查询呢?根据它的值。根据值来查找的。那现在我们就开始写这个代码了,Der ch。是不是你给我一个值吧,Value。Value。然后呢,我们现在都是特类型的。如果你查找到了,或者没有查找到,是不是都应该给我返回一个节点?对吧,那现在查找的时候,大家想你现在是二叉树,你现在是一个排序二叉树,你在查找的时候是不是先应该比较当前节点是不是,如果不是就向左边找,然后再向右边找,试一试吧。好,所以说我们在这个查找的时候呢,我们先来判断。先判断判断当前节点是否为要是否是是否是要删除的。
07:07
是否是要删除的节点?删除的节点。对不对,那这个很简单了,就这样写,如果我们的value,它就等于z.value。是不是这意思,那如果这个条件满足,我们找到了没有。找到了,找到是不是就把这个回去就可以了,谁啊this好,那下面继续写了。那那下面是不是还有一种可能性呢,就是如果你你这个不是。如果不是现在,我们可不可以像l if是吧,标if。LE。如果。你诶这个S,如果你这个节点,你就说你现在要找这个节点,它在哪里呢?它。它小于吧,比如说它小于。它它小,它小于这个,你这个当前节点这个值,我我们说明应该到哪去找呢。
08:07
向左边去找。向左去。递归去查找。去查找。去查找。好,那么你再往左边查的时候,是不是你应该先判断一下,就是你这个左边这个还能不能找是吧,所以你这边应该有个条件,就是你这个。this.left不等于空。哎,这样说吧,如果它等于空,是不是就意味着就没戏了呀?如果这个条件满足是代表什么意思?Return空了就别玩了是吧,就就没意思了,就else是不是说它没不为空不为空是不是就是我们可以呃,Return一个this.left点我们的这个search,把这个value放进去。
09:04
对吧,那是不是他为什么报错,是因为我是不是还有一个条件没写啊,还有一个S,还有一个S是代表什么意思。就是你就是大于别人了嘛,因为三种条件判断完了,等于还有一个小于,还有一个就真的是大于了,对吧,那就是这样子,同样道理是不是首先判断你的right。你的right,如果你的right它等于空,是不是也没戏了?那就直接一个什么呀。Ignore。Now。好,否则。否则是不是我们可以递归向右边查找,哎,否则就是递归递归向右指数查找。你看这边它其实你们看到这就体现出这个二分了,如果怎么样就怎么样,一大腿是吧,Return我们this.right点,然后把这个value放进去。好,代码就写完了。
10:01
非常简单啊,非常简单。那你那你这个节点找到了过后没有用啊,因为你找到过后,你将来要删除还。你你还得有个条件要找到人家的负极点吧,是不是,所以说你在这写完了过后呢,你还要做一个动作叫设PAR。那这个设置拍呢,你在比较的时候,你一定要注意它比较的是这个节点的左左子节点或者是右子节点,能能理解这意思吧,好,那么我们写写代码。好,这是找某个节点,下面是找某个节点的负节点,是这意思吧。好,我们现在还要还要写个方法,就是找找什么呢,某个。某个。节点的什么呀,负节点。因为我们现在是单向的,没有办法你必须这么去干,那就D我们写个search什么呀。对不对,然后你仍然给我一个值嘛,Value。
11:00
诶怎么写成这个玩意儿了,Int对不对,那同样同学们这边是不是他要给我返回一个节点呢,不管有还是没有,你总得有句话嘛,对吧。哪怕是你给我返回一个空呢?那下面这个思路应该是什么样子的,同学们?是不是,是不是首先判断当前吉林的左边。或者右边是不是已经有他了呀。哎,对,你的思路应该是这样子的,先判断,先判断当前节点的左或者右。是否?有这个词是这个词。是这个字。你看这样说,左节点左子节点。或者右子节点是否是这个值,那这个代码对我们来说很简单。怎么简单呢,一幅一句上来过,要做一个判断呢,同学们,首先你要保证你的左边不等于空的情况下才去比较。能理解啊,就是如果这个条件满足的情况下,而且left.no它等。
12:05
不是o value等于你这个value。这个条件满足或者。大家看这个稍微有点绕啊,这个只是判断左边是不是可能跟相等是不是同样道理,你还应该判断右边也有可能是吧。哎,这个条件把它复制过来。复制过来,然后在这边写上一段代码。就是如果它的右边,因为只要有一个条件满足就可以。右边不等于空,并且右边的值等于value。这说明什么问题呢,同学们?说明什么?当这个节点,就是你要找到这个节点,不节点是吧,就什么呀,This代码就写完了。那这个没有,洗完了接着往下走。因为你只考虑了这个当前节点是,那还有一种可能性,它不是啊。
13:00
对吧,那下面的条件就是else了。就是你当前节点不是。人家这个查找节点的负极点。那是不是你要向左边跑或者是向右边跑啊,那就是,那你怎么知道向左边跑还是向右边跑啊。哎,就是这样有条件了,如果。你要查到的这个值。你要查出这个值,它大于。呃,不,我们先写写小于,还是写像左边的话,如果它小于z.Y6。说明你这个要查的值应该是在这个。呃,左边去找是吧,说明。说明像。需要需要向右向向左边对吧,向左边去递归。查找。是这意思吧?那这个条件定了,那你向左边查的时候,我们应该怎么走呢?向左边走的话。
14:02
走左边走的话就。哎,对,咱们就先判断一下你这个z.left先要判断它不要等于空啊,在不等于空的情况下,其实这两个条件可以写在一起。对吧,可以加在一起,所以说这样子我们把它合在一起是不是更更好一点呢?这样写就是如果z.left它不等于空。是是这意思吧,不等于空,并且呢。并且你当前的这个值,呃,就说。诶对,我们这还不对,应该是跟他的。它的应该是跟它的这个值比较吧,不应该是跟它这个当前值比较吧,因为我们是我们是找子节点,是不是说这个这个写的是不是有问题啊,是这个地方应该写什么呀。是不是应该这样写才对啊?
15:00
是这样的吗?是有没有内大学的。有没有啊?有有有没有。有没有left同学们?有没有left?因为你现在找的是。你找的是人家,是你找的是家。负接点是吧,你不能负接点跟它的比,所以你看我原先这个代码里面写的,你看这是不是我们这判断的时候也是也是有这个条件的,就负节点,你看这我写的有z.value大于value,发这我没有写value啊。有没有啊?有还是没有,大家再想想没有。这个和节点。有有没有大家觉得。应该是没有才对吧,应该是没有,确实应该刚才写的是对的啊,没有,如果是没有的话,下面我们就应该向左边递归查找,就是Z点什么呀。
16:02
Left。点search parent,然后把这个纸放进去。因为你你你要找的,因为你要找一点跟这个附件点从往往外去分嘛,对吧,往外去分好同样道理,这个写完了过后,我们这最好有个return。最后一个return。好,然后还有一个条件,就是要死了。对不对。那么如果,如果这个条件。满足就往这边走,那下面呢,我们再来看还有一种情况。就是它的右边。他的他这个条件满足,还有一个就是右边。是不是就是它的这个右边不等于空,Right不等于空,然后呢,同时这个词大于它。那我就应该向右边去进行递归查找,对吧,右边。那我们看看右边,右边去递归查找的话呢,那这边就应该改成点right。
17:04
点search parent,把这个value写进去。好,这个都写完了啊,都写完。呃,这个就还这门,是不是那写还有问题啊。如果说这些条件都不满足。是不是我们这边还应该有一个空返回去。对吧,就是相当于说这是一个条件,这是个条件,如果这些条件都不满足,我们这加个if啊,加个这个加个S,最后返回一个空。Return。一个空。对吧。这样子代码就没问题了,我们看把这个逻辑再走一走。就是说第一个先判断你这个当前节点的左边。或者是右边是不是就等于当前值,如果是就返回。对。如果。如果这个条件不满足,那就说你当前这个节点的左边或者右边不是,那就怎么办呢?就判断你左边是不是等于不为空,如果不为空的情况下,而且你这个值还比我这个值要小,我就在左边去找。
18:13
对吧,如果说你右边不等于空,而且这个值大于它。那么我们就到。右边去找,因为你只有先要满足右边不等于空我才去找嘛。对,那还有一种可能性,就是这个条件呢,应该是这样子的,我觉得应该这样写更好一点。应该是这样的,是这个地方应该是A衣。是这样子才对吧,L if,然后这个地方有个S。这个地方返回一个空,这样写才是对的,为为什么这么说呢?大家想,因为这个条件是在左边没有找到,就是这个条件不满足到左边去找,这个条件不这个满,呃,这个条件满足到左边去找,这个条件满足到右边去了,如果两件条件都不满足,那就说明有可能这个left。
19:08
这就没有了。应该这个条件这样写才是正确的,是这样子吧。啊,不然的话,你到时间这个就有可能代码是是错的啊错的。好,那么这个写完了以后呢,我们来做一个测试,就现在呢,我们写了它的。子节点又起了,查到它的负节点,就差一个方法了,就什么呢?删除这个方法。
我来说两句