408数据结构------6.查找
查找算法的效率评价
查找成功的ASL
查找失败的ASL
顺序查找
- 算法思路：从头到尾或者从尾到头，逐个元素与哨兵比较
- 算法实现：引入0位置为哨兵可以减少一次越界判断；加入哨兵在第0的位置并存放要查找的元素，顺序查找的时候从后往前查找，所以就不用进行越界判断
- 无论如何优化都是O（n）
折半查找
- 算法实现：
- 缺点：要有序顺序表（链表不合适呀）
- 时间复杂度：log2n
查找判定树
- 构造
- 特性：
折半查找的判定树是平衡的二叉排序树
只要表中的关键字个数相同，就一定会生成形状相同的判定树
只有最下面一层不满
若有n个关键字，就要n+1个查找失败结点
分块查找
- 算法思想:
索引表中保存每块的最大关键字和分块存储空间
块内无序，块间有序
先在索引表中索引分块（可顺序，可折半）
然后在块内顺序查找 - 性能分析：
ASL=查找索引表的ASL+查找分块的ASL
B树（多路平衡查找树）
- 满足以下性质：
1.每个结点至多m棵子树，至多m-1个关键字
2.若根结点不是终端结点，至少有两根子树
3.除根节点外，所有非叶结点至少有m/2下取整课子树，即至少含有m/2下取整-1个关键字
4.所有叶结点都在同一层次（每个节点的子树高度一致），叶节点不携带信息，类似于查找判定树的失败节点，实际上这些点不存在，指向这些节点的指针为空
一定是平衡的！，且关键字是排序的 - 高度：
高度不包括查找失败的叶子结点，就像上面所说，叶子结点实际上算是不存在的
最小高度：
最大高度： - 插入
根本原则：除根节点之外，所有节点的关键字个数是xx~xx，且每个结点内部关键字有序
情况一：
若插入导致关键字书超过上限：
从中间位置分裂成两个部分，右边部分放在新节点中，左边部分放在源节点中，中点位置插入源节点的父节点；新元素一定是插入到最底层的终端节点，用查找来确定插入位置
情况二：
若导致父节点的关键字也超过上限： - 删除：
情况一：
若被删除的关键字在终端节点：
删除后关键字个数未低于下限，直接删除；
低于下限：
右兄弟够借，用当前节点的后继，后继的后继依次顶替空缺；
左兄弟够借，用当前节点的前驱，前驱的前驱依次顶替空缺；
左右兄弟都不够借，与父节点内的关键字+左兄弟或者右兄弟（所以会产生不同的B树）进行合并，（父节点也要下来当儿子），若导致父节点关键字低于下限，需要继续合并（父结点的父结点下来当儿子）。
情况二：
若删除的关键字在非终端节点：
一定可以转化为终端结点删除；
用直接前驱或者直接后继来替代被删除的关键字，随后删除这个直接前驱或者直接后继。
B+树
- 满足以下性质
散列表
- 概念：
关键字通过hash函数与存储地址直接相关
不同关键字映射到同一个地址，这些关键字就是同义词
同义词的冲突叫冲突。
聚集（堆积）：非同义词的冲突
装填因子（负载因子）：表中记录数/散列表的长度；降低装填因子来减少冲突；直接影响散列表的查找效率(ASL)。
散列表中，ASL平均查找长度与装填因子直接相关，查找效率不依赖已有表项数目或表长。 - 处理冲突的方法
拉链法：
所有的同义词存储在同一个链表中
ASL:
对空节点的查找次数是0
冲突越多，查找效率越低，理想情况下时间复杂度可以是o(1)
链地址法不会产生堆积现象
开放地址法
线性探测法：
- 查找：
同义词和非同义词都要被检查；
空位置的判断也算作一次比较；
越早遇到空位就越早确定查找失败。 - 过程：
hash一下后，一个一个往后查，查到空则停，但空位置也算一次比较 - 删除
不能简单地直接将被删除空间设置为空，否则会截断在它之后填入的同义词结点的查找路径，可以做一个“删除标记”进行删除标记 - 缺点
同义词与非同义词之间的冲突很容易造成聚集现象，影响查找效率 - ASL
平方探测法
- 过程
先hash一下，然后左右跳跃的查找，查到空则停。 - 优点
相比于线性探测更加不会产生聚集现象
再散列法
- 除了原始散列函数之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新的地址，知道不冲突为止
伪随机序列法
- di是一个伪随机数
拉链法和开放地址法的ASL计算：
ASL成功=（每个成功元素比较次数和）/元素个数
ASL失败=（每次hash失败比较次数和）/m
注意 ：
- 拉链法的空不算比较次数，但开放地址的空还算一次比较次数（而且开放地址到空才停止）
- 失败的比较次数注意范围，到%m就可以了，因为%m后面不是每次hash能hash到的，只是散列表的长度而已。
- 分母m是模的值