查找

在算法题中，查找最可能的是出现在收尾部分，利用xx查找找到一个元素。此时需要判断，如果有序，是可以折半，时间复杂度为$O(\log n)$；如果顺序查找，则是$O(n)$。而且注意，在整体复杂度已经很高的情况下，不要求技巧， 有些时候，老老实实顺序查找。

查找

基本概念

1. 静态查找
   1. 顺序
   2. 折半
   3. 散列
2. 动态查找
   1. 二叉排序树
   2. 二叉平衡树
   3. B树、B+树
3. ASL（平均查找长度）

顺序查找

其实就是一个循环

折半查找

1. 仅适用于有序的顺序表（链表是不行的）
2. 折半查找的过程——判定树（是一个平衡二叉树）

折半查找的代码一定要会写！

折半查找判定树

1. 不满的一层一定只在最后一层
2. 注意失败节点个数；注意树高——从而注意时间复杂度

散列查找（哈希）

1. 散列函数： Hash(key) = Addr

2. 散列表

3. 散列函数的构造（有个印象就行）

   1. 直接定址法
   2. 除留余数法
   3. 数字分析法
   4. 平方取中法

4. 处理冲突的方法

   1. 开放定址法

      数学推导公式：$H_i=(H(key)+d_i)\%m$

      如果用$H(key)$计算出来，发现有冲突，则利用上式继续寻找。

      1. 线性探测法（$d_i=0,1,2...n$）✨

         有很多的别名：线性探测再散列法、线性探查法

         就是加一加一地试，试到有个空闲的坑就进去

      2. 平方探测法（$d_i=0,1,-1,4,-4,...,k^2,-k^2$）✨

         避免出现堆积问题

      3. 再散列法

      4. 伪随机序列法

   2. 拉链法

      本质上就是一个数组链表的实现。下图中，红框表示冲突的解决方法：利用链表进行解决。
      

5. 装填因子

   $$\alpha =\frac{n}{m},n=表中记录,m=散列表长度$$

   散列表法的ASL直接依赖于$\alpha$，而不是$n$或者$m$。

6. ASL：对比几次关键字，就算几次。
   要注意有一个坑：在计算失败的平均查找长度时，不可以直接拿一个完整的表总长度进行计算，而是找所mod的数（在之前的叙述中是$m$）。

B树、B+树

B树

1. 是多路平衡查找树

2. n阶：这个n是每一个节点中，子树的最大值。

   1. 每个结点最多有$n$个子树，最多有$n-1$个关键字

   2. 若根不”独立“，则至少有两个子树

   3. 非叶结点——至少有[m/2]棵子树，[m/2]-1个关键字（天花板除）

   4. 叶节点（失败结点，NULL，不带信息）都在同一层节点上

      本质其实就是空指针

   5. 如果根节点有关键字，则必有超过两颗的子树。（连向NULL的指针也算是）

3. B树的高度【磁盘io次数】

   1. 最高（节点数最少）
   2. 最矮（节点数最多）

   （现场推）

4. 查找

   1. 在B树里找节点【磁盘IO】，将其读入内存
      1. 所以这里才是花时间花的最狠的
   2. 在节点里找关键字【内存里】
      1. 顺序或者是折半

5. 插入
   插入 是很有可能考大题的，即画出一颗B树的插入的流程，如下图。准备方法：多画画，多次记忆。

   分裂的时候，取k阶b树的第$\text{int (}k/2)$个位置（向下取整）往上走。

6. 删除

   薅兄弟的羊毛，【父子换位法】

B+树

1. m阶

   1. 分支节点最多m个子树

   2. 叶子结点：不再是最后一层（记记录层），而是下图的红框：
      

   3. 子树和关键字个数一一对应

   4. 结点关键字对应的是其对应子树的是最大值，也就是分块查找的思想

   5. 叶节点按关键字排序，并且用指针串联——有两个头指针：根节点、最小的叶子结点。

2. 对比

   1. b+树，每个关键字对应一个子树，一个记录；b树：m个关键字对应m+1个子树
   2. b+树，非叶结点不保存信息，仅仅起到索引作用：索引关键字对应子树结点的最大值。

特例

B树：

m=4——非根结点：至少1个关键字；至少两个子树

m=5——非根结点：至少2个关键字；至少三个子树

为什么要给出特例？希望你可以每一次做到B树或者B+树的题的时候，可以画出来对应的特例的树；这样在根源上就避免记混了。