00:00
各位,我们再来讲数据结构和算法的下一个内容,叫二叉排序数。那二叉排序数它是一个什么样的东西呢?我们仍然先看一个需求,说给了你一个数列,这个数列呢是七、三、十、12、五、一、九,要求能够高效的完成对数据的查询和添加。大家想你怎么实现?你怎么实现好,我们现在呢,来分析一下这个思路,第一种呢,你用数组来实现。对不对,如果这个数组没有排序。如果数组没排序呢,它的优点是我们在数组尾部添加速度比较快,但是缺点呢,查找速度很慢,这个是不是我们在最先前。在我们最先前讲哪个哪个时候的内容,我们讲过数组的这种存储方式的优点和缺点,还记得吧?在哪哪个地方讲的,如果打开我们的这个笔记的话,你会发现我们在讲数结构的时候,其实就已经提出这个概念了。
01:04
大家看我们在讲树结构的时候呢,在这里。对我说嘛,我们说了为什么需要数这种结构,当时呢,我们已经提到数组存储方式和链式存储方式的一个分析,大家还记得吧。诶,那么当时我们就已经提出数组它的。优点是就是我们在尾部添加还是比较OK的,但是呢查找速度还是比较慢,第二点呢,如果说你对它排序了,用二分查找,查找速度是比较快的,但是呢,排序这个过程还是比较慢的,对不对。而且呢,当你找到过后,如果你还要保证有序的话,它还存在一个问题,当你添加新数据的时候呢,找到插入位置后面的数据需要整体移动,甚至还需要扩容,速度比较慢。那当时我们又分析了用链式存储,链式存储呢,它的问题是它的添加速度比较快,但是。但是为什么呢?因为他操作速度还是很慢。但是在当时我们。
02:03
我们已经提出这两种方式,不好的情况下,我们已经提出数存储。数存储方式来解决,但是你们有没有发现我们前面讲的二叉树也好,赫夫曼树也好,我们你们有没有发现,其实我们一直还没有去真正的回答。真正的回答这个问题,说为什么数存储方式它的检索速度就会很快,是不是是不是一直一直我们没有去真正的去解决这个问题。是不是我们讲了二叉树的创建遍历删除,但是呢,我们没有去回答,为什么数存储方式就比较快呢?其实现在我们就要正正式的回答这个问题。因为现在我们已经有数这个结构的。一定的基础了。我们现在告诉大家,有一种数叫做二叉排序数,它就能够让我们的检索、插入、删除、修改的速度。是效率是比较高的。
03:02
所以说现在呢,我们来看一下二叉排序数,到底是一颗怎样的二叉树呢?来看一个幻灯片。所谓二叉排序数呢,它的概念是binary sort tree,有些人把这个S呢翻译成search,叫做二叉。查找数其实都差不多,那么对于二叉排序数呢,它有个特点,它说任何一个非叶子节点,要求左,左子节点的值比当前节点的值小,右子节点的值呢,比当前节点的值要大。说的再具体一点,就是你有一个节点,它的左边,它的左边左子节点要小于它,右子节点呢要大于它,那这里我有个特别的说明,如果有相同的值怎么办呢?如果说当然你要尽量避免它有相同的值,对不对。那如果真的有相同值呢?这时我们可以将该节点放在左子节点的左子节点或右子节点,这个就无所谓,因为他只要要求,呃,这个一定,如果真的有这个相同的情况下,那就没有办法了。
04:06
但是我们要尽量的避免有相同值啊,如果说真的有相同值,那你比如说你有个四对吧,你又来一个四,那怎么办,那就没办法,只能挂到这了,或者挂到左边也行。反正你只要保证,你只要保证你的这个左子节点,左子节点不要去,不要去大于它,而右子节点不要小于它的。这个直接的负节点就可以明白意思吧?好,我们举个例子吧,同学们看。如果这有一,这有一个数,这有个数据是七,三、十,12,五,一,九,那么对应的二叉排序数呢,长的就应该是这个样儿的。它是怎么构建起来的呢?我给大家画一下怎么构建流程,他首先把七放好,他发现三呢,3比7小就挂在它的桌子节点没问题,10比7大挂在他的右子节点也没问题。那么12怎么办呢?12:7,呃,12比7大,首先在它的右子节点去找,又发现这有个十,那么12比这个十还要大,所以放在十这个节点的右子节点,挂这了,我们再看五,5比7小,于是他先到到左子节点去了,发现呢,五比这个三要大,就放在这个三这个节点的右子节点,明白好一呢,怎么办呢?1比7小放在左边,放在左边发现1:3还要小,放在这个三这个节点的左子节点。
05:29
就完了,九呢,9比7大,9比7大首先放在七的右子节点,那再比7:10要小,放在十这个节点的左子节点,这个事儿就完成,呃,九啊九刚才说错了,999比7大吗?9比10小,放这最后这这棵树就是我们的二叉排序数,也就是大家看到这个题目,那么大家有没有发现,如果我们要插入一个二,你发现它速度还是很快的,怎么查呢?它先让这个二跟七比。发现二呢比其小,于是直接照七的左指数去找一下,就折半了。
06:04
让这个二呢,再跟这个三这个节点比,发现2:3还要小。继续在三这个节点的左指数去找,这个时候再比较发现2:1还要2比1大,这个时候呢,同时又发现一的左右子节点已经没有节点了,直接把这个二这个节点挂在一这个节点的右子节点,这事就结束了,就这样子。所以你们有没有发现就是二叉排序数,它的检索速度,其实这个效率还是很高,有点类似于这个二分,而且他找到这个节点过后呢,因为它是链式的一种,它整体还是用指针的方式可以可以挂到他的左或者是右,所以说它并不会导致我们整个这个结构的一个移动。所以说它的插入速度呢,也是非常的,删除速度也是类似。删除速度也是类似,好,那现在呢,我们已经对这个二叉排序数有一个基本的认识,那关于二叉排序数的介绍和它的一个基本的一个原理就给大家介绍到这里。下面呢,我们就来。
07:09
走一段代码给大给大家演示一下二叉排序数的一个什么呀,创建和它的便利,好,那下一个视频为大家走代码。
我来说两句