00:00
好,下面呢,我们就来看多差数中的比较有特性的一个数,叫做二三数。大家知道我在讲二三数了啊,不要把它搞懂,呃搞搞蒙圈了,二三数呢,就是一种比较简单的B数啊,这个简你你不要去管啊,就叫B数字,这个不要写个减。就叫B数,二三数是最简单的B数结构,它具有的特点是什么?注意听这些概念还是要要明白的。二三数呢,它有这么几个特点,第一个二三素的所有叶子节点都在同一层。就是说它只要有叶子节点,那么要求叶子节点必须在同一层。而且这点只要是B数都会满足这个条件,这是第一个特性。第二个有两个子节点的节点叫做二节点,二节点要么没有,要么没有子节点,要么有两个子节点,就说你的二节点不能只有一个,一只有一个节点,比如说你这有个节点,这个节点呢,它左右两边都有是可以的,但是你不能说我只有一边。
01:04
有这个子节点那就错了,要么你就都没有这个也可以,要么两个都要有,你不能只有一边,那个就不叫二节点了。那么二节点是什么意思呢?其实刚才我在讲这个地方就已经提到,看同学们,看这个27。就是一个二节点,而这个节点呢,这个节点就是一个三节点,明白哦,这个三就这个人就是一个三节点,为什么三节点呢?因为它有三个子节点,明白好接着我们往下看啊,不着急。这里面又提到三节点的概念,刚刚刚讲过,不要说我不多说了啊,但是有个要求三三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点,就说你也不能出现我有一个有一个这个节点,它它干什么呢?就在B数里面不允许出现这样一种节点。它是一个三节点,但是这挂了两个数据。这是不允许的,但是挂一个数据也不允许,他要么挂三个,三个时间点,要么一个都没有。
02:04
这个特性会决定,决定我们怎么去构建一棵二三树。当然有,有同学说他为什么要规定这些呢?这个就是就是它的一个要求,一个是他的要求,第二个呢,是更利于我们检索,提高我们效率。好的,那么二三数是一种什么样的数呢?二三数再看这个二,这个二就代表二节点,这个三就代表三节点。说的再具体一点,就是二三数是由二节点和三节点构成的数,注意二节点要满足刚才这个条件,而三节点呢,要满足刚才这个题条件明白了好,当我们有二三数这一个基基本知识过后呢,我们来实际的给大家看,我们来自己构建一棵二三树的案例,大家看。我现在有这么一些数据,这个数据一共有多少个呢?数一下一二三四五六七八九十,十一十二,我现在有12个数据,我现在要求同学们把这12个数据。
03:04
构成一棵二项树,你们能搞定吗?注意啊,二三数。在插入的时候,这个大小顺序还是要满足的,也就是说我们所说的二三数呢,它仍然仍然要满足我们原先讲的。原先讲的叫做这个排序数的特点。排序做的特点是什么呢?大家先往这看啊,先往这看。呃,就是它左边的追,听这这句话,嗯,比我这样讲吧,比如说你这有个二节点A。A,那么它这边有一个左节点叫B,这边有个C,它仍然要求B的这个值或者是全要小于A,而C的这个全呢,干什么呢?要大于A,如果你有一个节点是三节点,要求什么呢?注意听讲。好三节点,那么这还不好画三节点,我这样画一个吧,同学们注意听啊,三节点呢,有这样一个要求,比如说你这有个A,这个是个全值,这个是个B啊,这这个就不能写具体的值了,咱们这样子。
04:11
注意听啊,比如说你这有个12。这是它的数据项,那么这边呢,它的这四个节点,这个节点的左子节点,它可以是什么呢?是个十。它这个地方呢,是个11。它的右子节点呢,是个14 OK,那大家有没有发现,如果你是个三节点,它要求你这个三节点的左节点的值要小于12,它中间这一个,注意听中间这一个子节点,它的值是介于12和13 12和13之间的,而它的这个节点的右节点呢,要大于13。明白这意思吧,也就是说他仍然要满足我们排序数的这个特点。排序排序数的特点好,那现在呢,同学们。
05:00
我们就以这个数列为例,给大家讲解一下如何构建一棵二三数,那么二三数的插入规则,先跟大家聊两把。大家看第一个特,第一个插入规则,二三数的所有叶子节点必须在同一层,必须的第二点有两个子节点的节点叫二节点,二节点呢,要么没有此节点,要么有两个,前面已经说过了,三节点也是一样,刚才讲讲过了,第四一点特别重要。第四一点呢,它是按照规定插入一个数到节点的时候,如果不能满足上面的三个三个条件,就需要拆分,而拆的时候呢,是先向上拆,如果上层满则拆本层,拆完以后仍然要满足前面的第一个,第二个,第三个条件。也就是说,你在。创建这个二三树的时候,一直要保证它是一棵二三树。明白最后第五点,我们要求对于三个它的三个三个节点的指数,三节点的指数的值,当然二级的也是一样,他仍然要遵守这个二叉排序数的规则,就是刚才我讲的着字节点的。
06:12
中间这个子节点的和右边这个子节点的关系,要跟上面是一个。跟那个二叉排序数是一样的一个规则,刚刚我讲过。好,现在这样子,同学们我们就来看怎么去构建,打开一个示意图,因为这个构建过程呢,比较的繁琐,我事先呢已经把这个图给他画好了,我们来搂一圈就可以,好吧,因为你再画一遍呢,太累了,而且也没有必要我跟大家讲清楚就行了。来同学们看现在。现在假如现在有这么一个情况,说我目前有一个数列,我准备把它构建成一棵二三树来,同学们我们一步一步的玩,首先第一步11 16 16直接放在一个二节点就可以了。
07:01
这第一步大家看懂了没有,很简单吧,因为16直接放在一个二节点没有问题,这个是满足我们这个二三数的要求的,它是个二节点,但是左右两面都没有直接点,OK,再来看24 24呢,你怎么放,先跟他找同城放。24直接放在这个六十十六的这个这个同一个同一个节点的后边,那么这样就变成一个三节点。这个没问题吧,第二步又搞定。好,第三步,第三步,第三步这个是个12 12按理说呢,我们应该尝试着往这里面加,但是大家想如果真的放在16前面。行吗?显然不行,因为你放在16前面,那这个就不是一个三节点了,它就变成一个四节点了,因此不能放在这,那就怎么办呢?拆怎么拆呢。16放在这左至节点指向12,右节点指向24,你看搞定。这个是不是仍然是一棵二三树啊?
08:00
好,紧接着我们放32,跟着我的思路啊,32你怎么放呢?首先你找32:16要大,因此在它的左子节点。然后32拿到功能,尝试着往这个32的右边去放。发现OK,所以说这个第这是第三一步成功的,这是第四一步也成功了,下面第五一步,第五一步应该放我们的14 14怎么放呢?来看14,你看这个14其实放在12的后边就可以了,因为因为14呢比16要小嘛。比16小,当然我往这边放A,又比12大,就放在它的这一层,所以这个就搞定了。这是我们的又一步,第五步。好,紧接着我们来存放26 26怎么放呢?按理说这个26呢,同学们想,是不是按理说26应该放在这。可是你能放这吗?你放这的话,这个节点就有三个数据项了,那肯定就不行。那怎么办呢?这个时候就往上猜。
09:00
往上拆分,因为你也不能,你也不能把你你也不能把同学们看啊,你也不不能把这个16挂在它下面,你挂在下这个终结点也不行,因为你如果放在挂在一个终结点,大家知道有什么问题吗?你这个三节点。有只有一个直接点,所以就不满足二三数的要求了,因此你只能往上拆,拆成什么呢?把26顶到上面去,然后把二二十四和32分一下就变成这个了。大家看是不是这样子的。诶,你看这样是不是仍然是满足。一个234的,紧接着我们放哪一个呢?该放我们的34了,34很好放,直接放在32后面就行了。是不是放放在这个32的后面。就完事了,好,紧接着下面该放十了,我现在往下继续走啊,放十。好,我把这个数列呢往下挪一下,大家待会儿呢好看。现在该该放十了,在哪个基础上放十呢?在这个。
10:01
同学们跟着我的思路,这稍微有点麻烦啊。在在这个基础上放十,那么放十的话,理论上应该放哪呢?是不是理论上应该放到这个12的前边。放十是不是理论放在12的前边是,是这样子吧。A,对,我们应该放。啊,你我看看这个地方是啊不是啊,因为你你是在这嘛。同学们,你是在这放,你是在这上面放好,你在这上面放呢,你初始最初想的是不是在12前面放一个,这样行吗?显然不行,为什么不行呢?大家想你放到这,这就变成。四节点了,因此你只能把这个十往下放,但是这样放呢。有问题大家放这样放,有什么问题,大家发现没有说老师没问题啊,你看这个二节点有两个呀,这个是二,这个是2.1个都没有,这个三节点一个都没有,但是有没有发现他违反了另外一个规则。
11:04
因为二三素呢,它是一种B树,B树它是要求所有的叶子节点在同一层,你在同一层吗?你看。这个是叶子节点,这个也是叶子,叶子节点24也是,三二三十四也是,显然他们不在同一层,不在这同一层,你怎么办呢?你就必须把它进行一个调整。怎么调整呢?大家想怎么调整,你显然不能往上走。不能往上走,你现在只能去想办法对这三个数据进行进行一个调整,调整的结果是怎么样调整呢?大家看把。这个26往下挪。然后26呢,26下来过后,把这个24放在26的左子节点,把32和34这个节点放在26的右子节点,完事了。就变成这样子了,所以这当我们插入这个十的时候,你看为什么我标红呢?因为它涉及到一个调整的过程。
12:01
OK,这就是变成了我们这颗。你插入十个变成这样子了,你看我这也也写清楚了,对吧,我就不再看了,紧接着我们看插入这个八数据,八数据好办。八在哪加呀,同学们。你看你在这地方,在这个前十前面加个八不就完事了吗?可以的,好,你看这个八就搞定了,八在这。是不是好搬完了过后该加,加什么?加28,我们看28在这28在这棵树的基础上,你觉得应该加在哪里呢?理论上说应该加在他先跟16比较,发现28比它大,往这走,再跟26比较,发现比26大紧,往往它左指数长,按理说应该加到这个位置,但是你加到这个位置行吗?显然是不行的。为什么不行啊,因为你你放这这个节点就变成三节点了,显然是不可以的,于是怎么办呢?他就往上拆,怎么拆呢,把这一个32拎上去。把三十二零上去,然后呢,让这个不变,让这个32的中节点只用28,让32的后这个右面这个节点只用34就形成。
13:08
大家看到没有,OK,紧接着我们继续看,已已经到这一步了啊,到这一步我们应该加哪一个节点了呢?38 38应该比较easy 38也是从这找,诶38比16大,再比较38:32还大,放在他的右子节点,直接在34后面加个38没有问题,它仍然满足我们二三数的要求,所以说38加完了过后就应该变成了。这样一棵树在哪里?在下面这个图。哎,在下面这个图,也就是大家看到的这个图,38是不是在这啊。是在这好最后一个数啊,最后一个数38的,最后一个数38,下面最后一个数20,好,我们看看。如果要在这棵树上加一个20的话,你怎么你怎么插呢?首先16 20大于16往它的左边找,再看20:26还要小,于是往这边放,诶往这边一放呢,发现20呢还比24小,于是20直接放这搞定。
14:13
是不是样子好,最后这一棵二三树长的样子就是这个样子的。这个就是我们给大家讲解的一个二三树的一个完整的构建,一构建的一个过程的图示,那最终我们得到的这棵二项树就是这棵树。明白这意思了吧?当然有同学说,老师,那这个二三数它的效率会比二二叉数要高吗?显然。显然要高,我们刚才不是讲了,正是因为二叉数它的高度很高,而且它的节点是单相当于一个节点放一个数据箱造成的,因此我们这个二三数它在一定程度上干什么呢?它就可以降低我们数的高度,从而提高我们减,从而从而提高我们操操作的这个效率。明白意思吧,这科还是一个最简单的必输,同学们。
15:03
所以说我们从最简单入手,给大家演示了一下构建二三数的过程,大家看理不理解?OK,那关于二三数和多差数的一个原理的图解,先跟大家聊到这儿。
我来说两句