Please enable JavaScript.
Coggle requires JavaScript to display documents.
查找 (B树, 散列表, 树形查找, 静态查找表：查找或检索某个数；
适合查找方法：顺序、折半、散列, 动态查找表：需要插入或删除；
…
查找
B树
-
特征：任意结点的子树高度相同，叶节点不带信息；
根节点子树数[2,m],关键字数[1，m-1];
其他节点子树数[(m/2)向上取整，m]关键字数范围减一；
关键字值：子树0<关键字1<子树1<关键字2.。。。
-
-
-
散列表
处理冲突方法
开放定址法
Hi=(H（key）+di)
线性探测法：di=0,2,3...
会造成大量元素堆积，查找效率降低；
-
-
-
-
-
-
查找效率取决于三个因素：散列函数、处理冲突的方法、装填因子；
装填因子=表中记录数n/散列表长度m
平均查找长度直接依赖于装填因子，不直接依赖于m,n;
装填因子越大，发生冲突的可能性越大；
-
-
-
-
折半查找：又称二分查找，要求线性表必须有随机存取的特性，仅适用于有序的顺序表
过程可以用二叉树来描述，称判定树；是一颗平衡树；
查找时的比较次数不会超过树的高度h，h=log2(n+1)向上取整；
时间复杂度O（log2n）;
分块查找：又称索引顺序查找，既有动态结构，又适于快速查找；
块内和索引表中均采用顺序查找，
平均查找长度=s方+2s+n/2s;
s=根号下n,则平均查找长度取最小值（根号下n）+1