00:00
同学们,我们来看一下二叉树。呃,首先还是呃老规矩,我们来看一下为什么需要数这种数据结构,基于这么几个原因啊同学们,我们在前面学这种数据结构的时候呢,我们发现我们的数据存储的方式,方式主要有这么两种,一种呢就是用数组来存储。对吧,那么数组存储的这种方式呢,它的优点可以通过下标访问,速度比较快,这是它的一个优点。而而且呢,对于如果是有序数组,同学们如果是一个有序数组的话呢,它还可以使用二分查找来提高检索的速度,那同学们要注意这个二分查找,它在进行这个检索的时候,速度还是非常快的。那呃,大概有多快呢?我我们可以试一下啊,就是说假如你扫描二三十次。那么它大概能覆盖多大一个数据呢?大概11个数据,也就是说如果我们拿这个二分的这种方式来检索速度的话呢,8000万个数据基本上是秒杀,就是零秒就能出数据结果。
01:16
所以说这个数数组的话,我们结合这个排序,再结合二分查找,它的检索还是比较OK的。但是呢,它有一个巨大的缺点,同学们都知道数组它的缺点是如果我们要检索一个具体的值,这个没问题,但是如果我们要按照一个顺序插入一个值,就出现一个问题了,它需要整体移动,效率就比较低,我画个示意图。OK,那么待会呢,这些问题提出来过后,我们就有相应的解决方案,还是在这里画一个,同学们,比如说我这里有一个数组,OK,这个数组,当然这个数组,比如说现在我们这里面放了这么几个数据。
02:01
我就试一下E好吧,比如说我这里有这么大一个数组。假设这个数字有这么大。然后呢,我目前有一个有序有序的这么一个数组已经存在了,比如说是一。是。我。对吧,14567好大概呢,我就有这么多个数据。后面呢,还有一个空间,我们表表示是预留的。那假如现在我有一个什么要求呢?诶,我现在有一个数为三。我要把这个三数据插入到我们这个有序的数组里面去,大家都知道要插入到这个位置。那大家想你插入到这个三这个位置的话,就会做一个什么工作呢?当你把这个三插入到这个位置的时候,你的这这个数据所有的数据要后移,就是你插入到这个位置过后,你的二你你这个四就往后面移动一下,七往后面移动,就是从后面依次往后移,这个代价它是比较高的。
03:11
所以说对于这个数组来说,我们可以通过二分法提高检索。但是它的插入。或者是删除都比较麻烦,效率较低。那我们再来看我们的第二种存储数据的方式,就是链式存储,也就是说我们的链表,那么链表这种方式呢,优点我们是显而易见的,就是说如果用这种方式来进行优化,我们插入一个数值,大家都知道。我们并不需要对整个链表进行移动,对不对?你比如说我们还是画一个示意图,很简单,一个示意图,比如说我这里有一个链表。我就画画四个节点就可以了。那假设第一个是我们的头节点,那现在呢,我们在这有一个数据。
04:00
他们一次这样指定的,对一这样指定。现在这个数据大概是什么?第一个是一,第二个数据为五,第三个数据为六,为七,现在我们要把这个三,比如说现在我有一个节点对,现在比如说我有一个节点为为这个二吧。为二这个节点,我要把这个二节点放到这个有序的链表里面去,很简单。我只需要找到它的前面的这个节点,然后让这个节点,让我们这个二号节点指向五号节点,再让原先一号节点指向我们二号节点,这个事儿就完了。但是大家要注意,对于这个有序链表,虽然它插入或者删除速度比较快,但是它仍然要需要。检索,他这个检索的话,仍然是要从我们的表头一个一个去找。对吧,那这个效率肯定是很低的嘛,因为你这个是线性搜索呀,你得一个个比。
05:02
那这个速度就会非常慢了。就会非常慢,那那有多慢呢?大家可以试一下,如果用一个8000万的一个有序有序的一个链表,你插入一个数据,平均时间呢是很长的。那怎么办呢?就说数组有它的优点,就是它的这个检索还比较快,那么呃,检索还可以,那么对于这个链表呢,不管你是有序还是无序,它插入和删除比较快,但是它的检索速度又很慢,怎么办呢?大家看,我们提出了新的一种存储方式,叫数。那么这个数的存储方式呢?它兼顾了存储和读取的效率。比如我们待会儿会讲一个比较经典的,也就是说经典的一个叫二叉排序数,叫BST,这个BST是怎么全写呢?叫battery。Salt,有些地方可能叫search,都一样啊。
06:01
呃,叫tree。那么如果我们用这种数据结构二叉排序数,既可以保证数据的检索速度,同时也可以保证数据的插入、删除和修改的速度。那我给大家画一个图来描述一下这个数的,呃,这种结构大概它为什么这个存储和读取都比较快,比如说现在我有这么一棵树。同学们来看一下,比如说我有这么一棵树。哦,我就以这棵树为例吧。我我就找一个数啊,同学们,我把这个数呢,给各位同学先放到我们的。这个。啊,这个位置来。假如我们存放数据是这样存的。那如果是这样存的话呢,我们来看一看,如果我们要去检索一个数据,它会有多快。好,我们看对于对对于这个左边的左边的这个数,它是一个什么呢?诶,它是一个BST。
07:08
就是二叉排序数,它的特点大家注意观察,它的特点是什么呢?OK,它的特点是啊,每个每个非叶子节点。叶子。非叶子节点。到这个左左节点的这个值小于当前节点。而它的它的这个又。它的右子节点。又值节点的值干什么呢?大于这个当前节点的值,那比如说你看我们这个情况七,你们注意观察。诶七你看这个七,呃,只要比七小的,通通放在这一大块。
08:01
比七大的通通放在这大块,你看这边三小于70大于七,那对于这个三而言呢。A它也要满足这个要求,你看31比3小,它放在三的左直接点,5比3大放在三的右子节点,这个也是一样,那如果这样的话,我们来看看它的检索速度有多快呢?其实大家发现因为你用BST数来做的话,它的检索速度基本上跟二分查找。完全一样了,看啊,对于大家看,对于这个这个BST。我们待会呢,可以哈,对于这个BST数而言而言。而言它的这个它的检索速度。它的检索。检索速度啊,是基本上是是12分的这个二分的这个这个这个效率。
09:01
效率一样的,你看我打个比方,比如说我们要查找12。那你看你比较几次就可以找到这个数了呢,你首先跟七比较。比如说我们要找12这个数。我们发现12这个数比七大,立马就折半了。我只找这一边,那也就是说这一大块就不需要你再找了。那么如果再让这个12跟十比较,11比较发现12比10大,再找它的右子一点再比就到了,比如说你比较三次就到位了。那它的效率是二分,那么二分效率它大概是个什么样的比例呢?比如说我们我们可以这样算,比如比如我们比较,我们比较30次。我们就能覆盖,我们覆盖多大一个数呢?覆盖的这个数据的量。二四大家可以猜测出来就是二的二的A2的30次方。OK,二的,诶这写错了啊,二的30次方,那二的30次方其实已经是11个数据了。
10:06
10亿啊。这个不是开玩笑的,10亿。那11这个数据30次对于我们来对这个比较来说,大概花多少时间呢?应该是毫秒级的。那有些同学是真的有这么快吗?我们可以简单的来做一个测试,看看是不是有这么快。好的,我们就以我们上一次课写的这个二分查找来进行一个简单的测试,那上一次课我们做了一个sort。扫着呢,我扫,那么我们先整一个这个8000万个数据有序的啊,然后呢,我用这个二分查找来查一把。我们就随便找一个吧,找一个排序,因为时间要稍微快一点,我就找这个,用这个规定排序来玩一把,规定排序刚好已经有8000万个数据了,对不对,那我就来玩一把了啊,那这个排完了过这个到这儿各位。
11:02
是不是到这里,我们这个数组到这里。到这里数这到这数组已经是有序的了,因为你用二分查找它必须是一个有序的是不是好,那么我们来测一下,我们现在测试二分的效率,二分的这个时间或者速度啊。啊,非常简单,我把我们原先写的这个二分查找的这一段代码拿过来,我们就用哪个呢,我们就用这个第二个方法,因为这里面可以找到重复的都能拿到,OK,那现在呢,我把这段这个函数。我把这个函数拿过来。Betty,帮我拿过来。好拿过来过后呢,我把它复制粘贴到我们的merge这边去。好,我就写到这里了啊,我就写到我们这个位置就O了。非常的简单,引进去好,引进去过后呢,我们就调用这个方法来查一把,OK,好,现在我们开始来查啊b research,我们把这个有序数组传进去,然后给它一个左左索引,下面这边我们要找的呢,应该是这个a.N减一。
12:19
然后我们要找哪个数呢?我随便写一个,比如说我找一个这样的数啊。OK,找一个这样的数吧,然后呢,我得到一个结果。我得到一个结果,好,这个结果大家都知道,返回的是一个数组。哦,那这个显示的效果我就不写了,我就把原先写的这这段代码拿回来用一下,就这个。对不对,打印出来看一下,我们看看花费时间大概是多久,好的,我把诶这方为什么错了呢。啊,这个希望完成这个东西就可以了,好那现在这样子啊,因为它排序完了过后打了一个时间,我在这马上再来打一个时间,就是它检索过后,就是搜索后的时间搜索。
13:09
So。诶,这个搜索是吧,搜索后的时间,那我把这个时间应该改成一个新的时间,我们打出来。好,上面这个地方是不是也要改成三呢?OK,好,同学们,现在呢,我们可以来测一下了。就看看我们在一个8000万个数据里边,我们去找,用这个二分查找,大概花费多少时间执行一下。OK运行。运行我们看一下,那理论上来说应该是非常非常短的,基本上是毫秒级的。好,我们来。等一下啊,好,8000万个数据产生,会因因为它排序会花点时间。大概11秒,我们上次是做过测试的,对吧,稍等片刻。
14:02
好排序。诶,为什么这么久啊,可以了,你看排序时间是不是15秒,可能是因为我现在内存用的比较多,但是大家发现他查找时间。看到没有?对吧,一模一样说明它这个时间非常短,它找到多少呢?找到这么多数都是你这个值,所以说我们可以看到二分查找其实已经足够快了。足够快乐可以的啊,那如果说我们这个就是我们所谓的这个后面我们练的这个链表,能够达到这个二分查找的效率,其实已经OK了,就说对于你这个大数据来说应该也没问题,即使即使你这个数据量是十个亿。也无所谓,因为十个亿我只要比较,那大家想我比较100次可能也是秒级,因为比较100次很简单的人比较100次都没有,花不了多少时间,对于数据而言,二的100次方,大家想这个数据有多大,我就不不去演示了,肯定。
15:03
足够你用了,好的,那我们检索速度这么快,那插入速度是不是也很快呢?OK,插入速度呢。插入或者删除的速度。会不会也很快呢?删除其实它的速度也很快。为什么这么说?因为你删除的时候,是不是首先要找到这个节点,你很快就找到了,找到过后我把这个节点删除是不是应该也很快?当然有些同学说,说老师,如果你删除完了过后,你不是还要保证它仍然是一个BST数吗?是的。但是也很简单,我们今天呢,会给大家演示插入和删除,你会看到速度也很简,也也很快,因为比如说我要比如说我要删除这个节点,12号节点。我只要找到这个12号节点的负节点。把这个12号十十二号负节点的右子节点制空,它就没有了。
16:03
当然有些同学又说了,说老师假设你删除的是七呢。也很简单。也很简单,为什么呢?因为根据这个BS技术,大家知道它的特点是所有的非子节点要满足这个条件,那我只需要如果我删除的这个是七。我只需要在它的右。指指数里面找到一个最小值。然后把这个最小值干掉,把这个地方改成最小值是不是就就OK了。大家听懂我在说什么吗?哎,是不是这个速度也很快呀,你不就是两个动作吗?一个查找右子数的最小值,基本上是秒级。删除就是把这线断掉,基本上是毫秒级。改一个值,这有什么难的,说它的插入删除速度也是very OK的。所以这样子的话呢,我们就可以保证将来我们这个缓存也好,包括我们的这个增删改查数的都非常好,只是你在这个做的时候呢,要把这个数做的比较到位,对吧,你比如说要做一个平衡的二次二叉树手术等等。
17:11
那么我们后面会进行这个演示。好不管怎么样,大家。根据刚才老师的描述,大家知道数这个结构,它的确可以解决我们的存储和读取的效率是不是好。那么关于二叉树的一个基本介绍,老师就说为什么要学这个数据结构?老师就讲到这里,我们进行一个简单的板书。好,同学们,我们打开它。打开它。OK,那打开了过后呢,我把刚才我们讲的这一部分进行一个简单板书,来往下拉一下。好。等一下啊,这个刚才打开速度有点慢。比较拉下。好,走一个。那刚才我们讲的是什么呢?二叉树对二叉树。
18:03
那我刚才给同学们讲解了一下,我们为什么要学这种这个数据结构,对吧,原因呢?呃,我通过这个图解的方式啊,说明了一下。第一个呢,我们先给他分析了一下数组存储啊方式的优点和它的缺点,然后呢,我们又讲了链式存储的优点和它的缺点,然后我们提出数这个结构呢,它可以解决对吧的一些问题,好我后面挪一下,那这边呢就是说。数这种存储结构呢,它能够提高我们存储和读取的效率啊,比如说我们会用一个叫二叉排序数来解决,我把这个示意图也给大家拿过来。好的,那刚才呢,我们画了一个非常简单的。这个二叉树。好,保存到我们的笔记中。好,那同学们对他的一个基本介绍,我们就先说到这里。
我来说两句