查找

顺序查找

又称线性查找，主要用于线性表查找，常常分为一般无序线性表顺序查找和对按关键字有序的顺序查找。

无序表顺序查找

平均查找长度：

1. 成功查找：(n+1)/2
2. 失败查找：(n+1)

有序表顺序查找：

平均查找长度：

1. 成功查找：(n+1)/2
2. 失败查找：n/2+n/(n+1)

折半查找

仅适用于有序表

平均查找长度：$log_2(n+1)-1$

类比成一个平衡二叉树

不适用于链式结构

B树

B树特点

• 树中每个结点至多有m棵子树,即至多含有m-1个关键字
• 若根结点不是终端结点则至少有两棵子树
• 除根结点外的所有非叶结点至少有m/2(向上取整）棵子树即至少含有个m/2 -1关键字
• 所有的叶结点都出现在同一层次上并且不带信息
• B树是所有结点的平衡因子均等于0的多路平衡查找树

B树高度

$$ log_m(n+1)\leq h\leq log_{\lfloor m/2 \rfloor}((n+1)/2)+1$$

散列表

散列函数—个把査找表中的关键字映射成该关键字对应的地址的函数记 冲突:散列函数可能会把两个或两个以上的不同关键字映射到同一地址 散列表:根据关键字而直接进行访问的数据结构 对散列表进行查找的时间复杂度为O(1)

散列函数:

1. 直接地址法

   H(key)=key or a*key+b

   不会冲突。适合关键字基本分布连续情况, 如果不连续容易造成空间浪费

2. 除留余数法

   H(key)=key%p

   简单常用的方法，但是要找好p

3. 数字分析法

4. 平方取中法

处理冲突的方法：

开放定址法：

数学递推公式:Hi=(H(key)+di)%m

增量的取值方法：

1. 线性冲突

   顺序向下一个单元探测 容易实现 但容易发生聚集现象

2. 平方检测法

   d取0 ±n^2(n=1，2…)

   可以避免堆积 但是不能探测所有的单元

3. 再散列法

   用了第一个散列后再用一个散列函数计算增量

4. 伪随机法

   生成一个伪随机序列作为d

拉链法：

用链表把所有散列得到一样关键字的同义词连在一起。

易错点

1. 对于一颗m=5的b树来说，有可能他的所有非根节点都是两个关键字，也有可能每个非根节点都是4个。