查找思想

查找表的逻辑结构是集合。
静态查找表:只进行查找、读取元素的操作的查找表。我们不关心查找表的创建。
动态查找表:在查找前,我们要先根据原有集合创建这个查找表,并且在创建过程中需要查找,当查找不到元素时插入。

查找长度即是比较次数,平均查找长度ASL,是每个元素查找需要的比较次数*其查找概率,之和。每个元素查找概率相等即1/n。

线性表查找

1.顺序查找,ASL=(1+…+n)/n=(n(n+1)/2)/n=(n+1)/2。
平均时间复杂度 O(n)。
岗哨的位置在要查找的元素外,所以在查找不成功时,与关键字的比较次数是n+1。
2.二分查找,也称折半查找,要求线性表是按关键字有序顺序表,只适用于静态查找表。
中间点位置=⌊(low+high)/2⌋,在和中间点位置值比较后,得出的左右两段都不再包含此中间点位置。
二分查找过程用二叉树来描述,称为描述二分查找的判定树,或比较树。
ASL=((n+1)/n)*lg(n+1)-1≈lg(n+1)-1。
树深度=⌈lg(n+1)⌉。
平均时间复杂度 O(lgn)。
3.分块查找,又称索引顺序查找,性能介于顺序和二分查找之间。安要求线性表分块有序。
它的索引表是由各块中的最大关键字及块起始位置组成的有序表。
先查找索引表,确定块,再在块内顺序查找。

树表之二叉排序树

二叉排序树,又称二叉查找树。中序遍历一棵二叉排序树可得到键值的升序序列。ASL介于O(lgn)和O(n)。
从键值序列生成二叉排序树:挨个把序列中的元素接入树中的左小右大的适当位置,每次增加的新结点都是树上的新的叶子结点。
从整体看,排序树只是用来排序,它的状态不一定有序。
运算:插入、生成、删除、查找。
平衡二叉树是指任一结点的左右子树的高度大致相同。
同一些关键字的不同序列,可能会得到相同的二叉排序树。这些序列的基本特征是开头字符相同,然后接着是全部右枝中的点或全部左枝中的点。
二叉排序树与二分查找类似,关键字比较的次数不超过二叉树的深度。

B-树

读作B树,即Balance Tree,多路平衡查找树。度为m的B树称为m阶B树。度数大则高度小,较大的度数使结点中的关键字较多,相比减小了磁盘访问次数。
一般地,文件中查找性能,受到的磁盘IO的次数的影响,远大于内存中比较的次数的影响。B树用于对较大的,存放在外部存储器上的文件内查找,是一种尽可能降低磁盘IO次数的文件组织方式。Mysql的数据索引存储即是基于Hash表或者B+树。
非根结点关键字数j:⌈m/2⌉-1<=j<m-1。

https://www.sohu.com/a/154640931_478315

散列(Hash)技术

和排序类似,要突破lgn的下界,就不能只依赖比较。
将结点按关键字的散列地址,存储到散列表中的过程,称为散列。
散列函数的作用是压缩待处理的下标范围|U|到m=O(|K|),即|K|的线性阶数量级,|K|<= m <|U|,所以从所有情况来看,冲突总会出现。
散列函数的标准是简单和均匀。有平方取中法、除余法、相乘取整法、随机数法。
处理冲突的方法:开放定址法(线性探查法、二次探查法、双重散列法)、拉链法。
地址单元为空的地址称为开放地址。
开放定址是当冲突发生时,用某种探查法在散列表中找到一个地址来放置这个冲突的结点。
散列表上的查找:
1.在散列表中查找散列地址h(K),若其单元为空,则查找失败。
2.比较其单元和K值是否相等,若相等则查找成功。
3.按冲突处理方法计算下一个散列地址h(K)。
堆积:是非同义词之间对一个散列地址的争夺现象,我理解为二次冲突、后继冲突,即解决冲突而给出的地址仍然已被占用了。

发表评论