00:00
那么我们前面讲的这个二叉树呢,大家也可能没有感觉到这个树到底有什么好处,对吧?就是二叉树的,它这个应用,它有不同的数,就很多很多数,待会呢,我们再做一些其他数的一个简单的说明,那我们现在看一个就是比较,呃,就是。跟我们这个搜索还有插入这个关系比较密切的一种数叫什么数呢?叫做二叉排序数,有些地方叫二叉搜索数。都一个意思,那我们先来看一个需求吧,我们还是一个需求来解决,说给了你一个数组,对吧,这个数组,这个数组呢,要求能够高效的完成对数组的查询和添加。大家都知道宿主这个玩意呢,就说你你你查询这个是没问题的,就是你只要把它。做成一个有序的,然后用二分来查找,而且你都能查得到,但问题是人家还要说数组的添加也要高效,你这个就比较郁闷了。
01:05
为什么呢?因为你这个你这个数,你这个数组要添加,如果数组你原先开的假设这个数组还不是可变的,就是buffer,呃,就是。那你如果在在这个,呃,在这个添加的时候,即使你开一个很大的空间,我就就算你开的空间很大啊。你插到中间是不是整体往后移是吧,那个那个代价也是非常高的。同学们可以去试一下,假设你有一个数组是8000万,然后你要加的时候刚好加第二个位置,你要移动多少次,你自己想一想。8000万减二。那么多次。你你你头都大了是吧,那你想想这个东西没法玩,人家等到你排,等到你把这个数添加进去过后,你还还没让你新新创建这个空间呢,这个都跑不起来了。所以这个时候呢,我们要想个办法来解决的问题,那么现在我们就用二叉排序数,各位,那么我们来看看二叉排序数呢,它是什么数,刚才其实我已经讲过了啊,使用数组不行,使用面试,面试存储链表呢,速度也很慢,我在开篇就已经把这个说了,这就不再说,我们来看如果这个数组我们能够形成这样一棵树就特别的棒了,形成一个什么样的树呢?好。
02:20
其实这个数我已经在前面有了,我把这个数再,诶不是这个数啊。这个数是不是在。这个地方好像有有一个就他就他。好,我们打开这个,然后我就直接放到这,假如我们能够把这一个数组。啊,当然这个数组呢,你怎么放都行哈。把这个数组能够形成这样一棵树就特别的棒。大家看我把这个七。比如说我在行成的,我这样放来一个七,我就放在这儿,我看这个三。这个三如果比这个七小,我就扔到它的左子节点。
03:00
如果这个十比它大,我就放在右子节点,这个没没问题,因为这个很好很好很好实现,然后我看12 12它比七大,所以就放到七这边的右边,右边有了过后再跟12跟十比较,发现12:10还大,就放到这个节点。它始终是能挂上去的,对吧,然后再看55:7怎么样,小五比七小,往它的左边一找,发现左边节点有一个三,再让三跟五比较。发现这个5比3大就挂在这个山的右边。同样一,1比7小,一往下,往下走有个三节点,一跟三比较,1比3小放这儿。那么九九呢,这个地方九比它大,九如果是九的话,跟十比较,比十要小一点,放到这个节点,你看这样我们就形成了一个二叉素,这个二叉树呢,我们在进行这个比较的时候就会比较快。因为你看假如我要查找我,我在挂的时候也很也很好挂,呃,那么我在查的时候也很快,因为比如说我要查九,我一查把这边就拨出去了,然后把这个放到这,因为他已经相当于用了二分。
04:12
对吧,那效率肯定是非常不错的。当然有些同学可能说,诶,假设特殊情况形成一个数,它的高度很高怎么办呢?那还有别的方案可以解解决的啊,好,现在我们先来针对这个数组来做一个处理,好,刚才我们已经讲讲了,那现在我们直接来看啊。所谓二叉排序数呢,也叫BST数,叫batterary salt,啊,Salt这个tree也叫search。对于二叉排序数的任何一个非叶子节点,要求左子节点的值比当前节点值小,就小的往右边,左边放,右子节点的值呢,比当前节点值大,就是大的往右右右右子出发。特别说明,如果你在做的时候有相同的字怎么办呢?其实有相同的值,你可以把这个节点放在左直节点,或者右右直节点,因为它它没它不能放在同一层嘛。
05:09
啊,所以说这个地方严格的说,只要不比他小就不比他小就行。那比如说现在我前面这个数组就可以形成这样一个,形成这样一个啊。二叉排序数,那二叉排序数如果我要插一个二,比如说我在后面有一个二,我要怎么插进去呢?我同样也很简单,我我就找到这个位置,先让这个二跟七比。发现2:7要小,一定放在这边的,让二跟三比。2:3还要小,跟它下面左子间隙,发现2比1大,就放在它的左边,发现下面没有了,就放在这个节点,所插入的速度也还算可以的。至少我在插入的时候,我只是比较,而没有整体移动。对吧,即使你这个数很大,我刚才已经讲过了,只要你这个二叉树做的比较均衡。
06:01
那么你30次的一个比较可以覆盖11个数据说找到这个位置呢,也是很快的,插入也是很快的,所以说这个二叉树呢,是可以这么去玩的,好明白这个基本介绍过后呢,下面我们就来完成这个二叉树的。创建便利添加和删除好二叉树基本介绍我先说到这儿。
我来说两句