一、对半查找

1、伪码：

一定注意：该伪码中元素下标为1，2，3…N。不包括0

算法 B (N,R,K.i)
/*N个记录，R为表中元素，查找目标为K*/
B1[初始化] s = 1. e = N
B2[取中点] i = (s+e)/2
B3[比较并判断]
    IF e < s THEN RETURN -1.//查找失败
    IF Ki < K THEN s = i + 1.
    IF Ki > K THEN e = i - 1.
    GOTO B2

2、二叉判定树举例：

二叉判定树

对于每一个结点：
它的左孩子是它下次查找的起点
它的右孩子是它下次查找的终点

3、查找长度分析：

对于查找成功的情况。他的长度等于路径长度加1
比如以下结点的查找长度：

  • 23 ： 2
  • 12 ： 3
    对于不成功的结点，它的查找长度等于路径长度
    比如以下结点：
  • 38 ： 4
  • 57 ： 3

4、平均查找长度计算

内路径：查找成功的路径（以圆框为终点的路径）
外路径： 查找失败的路径（以方框为终点的路径）
设内、外路径总长分别为、

查找成功的平均比较次数：
查找失败的平均比较次数：

外路径长总是比内路径长大2N

可以推出

对半查找二叉判定树的高度为 (取上界)
若不考虑外结点时的二叉树高度为k，则外结点的高度一定为k或k+1

5、一致对半查找

对比：二分查找时用到了两个数据来确定区间 起点(s)和终点(e)
一致对半查找改用另外两个数据: 中点位置 区间长度。

伪码

算法 U(N,R,K.i)
U1.[初始化] i = N/2(取上界). m = N/2 (取下界)
/*这里的i指的是中点位置，m是区间长度*/
U2.[比较] 
IF K < Ki THEN GOTO U3.
IF K > Ki THEN GOTO U4.
IF k = Ki THEN  RETURN i

U3.[减小i]
IF m=0 THEN RETURN -1.
m = m/2(取下界).
i = i - m.
GOTO U2
U4.[增大i]
IF m=0 THEN RETURN -1.
m = m/2(取下界).
i = i + m.
GOTO U2

其实上面算法的m是可以事先准备好。

二、斐波那契查找

斐波拉契查找与二分查找相似，但构造树的方法不同

二叉判定树

对于k阶斐波拉契树(即包括外结点时层数为k)， 其根节点为.这样很容易确定左子树。
对于右子树，每个结点的值减去根节点的值仍为斐波拉契树。

伪码:

算法 F(N,R,K.i)
F1[初始化].
    i = f[m].//m为阶数 f[m]为第m个斐波拉契数
    p = f[m-1].//p为左子树的根节点
    q = f[m-2].//q为左二子树的根节点，同时也是i与左右儿子结点的差值
F2[比较]. 
    IF K < Ki THEN GOTO F3.
    IF K > Ki THEN GOTO F4.
    IF K = Ki THEN RETURN i.
F3[i减小].
    IF q = 0 THEN TRTURN -1.
    i = i - q.//转到左子树
    t = p.
    p = q.
    q = t - q.
F4[i增大].
    IF q = 0 THEN TRTURN -1.
    i = i + q.//转到左子树
    t = p.
    p = q.
    q = t - q.

斐波拉契树中，左子树高度等于右子树高度-1

三、插值查找

与二分查找的区别仅在于：
二分查找的比较元素 i = (s + e)/2
插值查找的比较元素 i = s + (K - Ks)/(Ke - Ks) (取上界)

四、二叉查找树

即：中序遍历为升序的树

二叉查找树的删除操作:
需要已知：待删结点的父结点 待删结点。

用哪个结点代替被删结点呢？
可以使用右子树的最大值。
具体是右子树的最左端
(左子树的最右端也可以)

五、高度平衡树

1、定义

平衡系数：左右子树高度之差
比如 左子树高m，右子树高n，则平衡系数为m-n
高度平衡树：任意子树的平衡系数绝对值小于等于1

二叉树的存储结点中，有一个值为b(root),它指的是该结点的平衡系数

2、平衡二叉树的调整

定义如下两个结点：
破坏者：平衡二叉树的平衡被破坏时，新插入的结点
发现者：距离破坏者最近的、平衡系数绝对值大于1的结点

RR LL LR RL 旋转的方法？
无非是调整三个结点的顺序，使链式结构改为树形结构。
这三个结点，是从发现者开始向下遍历的连续三个结点。
具体可百度。
并且还需要调整各个节点的平衡系数。

六、B树

详解请戳：《B树、B+树详解》

B树主要用于外查找

1、定义：

B树是一个多叉平衡树。
一个m阶B树满足：

  • 每个结点有不多于m个孩子
  • 除根节点和叶结点外，每个结点有不少于m/2个孩子
  • 根节点至少有两个孩子(除非本身是叶结点)
  • k个孩子的结点，包含k-1个关键词
  • 所有的叶结点都在同一层

（根节点孩子个数也要小于m）
同层的所有元素升序排列
B树
可以看到，父结点的每个元素都参与了孩子结点的划分

2、插入

插入的前提是找到能插入的位置。
查找操作与二叉树类似，不再赘述。
找到插入位置后：

  • 若该节点元素个数小于m-1，直接插入；
  • 若该节点元素个数等于m-1，引起节点分裂；以该节点中间元素为分界，取中间元素（偶数个数，中间两个随机选取）插入到父节点中；
  • 重复上面动作，直到所有节点符合B树的规则；最坏的情况一直分裂到根节点，生成新的根节点，高度增加1；

B树调整时是从枝到根调整。

3、删除

直接删除之后有可能出现：

  • 1） 子树划分问题
  • 2） 当前结点的元素有可能小于m/2 - 1（取上界）

先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；

七、数字查找

注意一下检索表：
检索表

八、散列

1、散列函数

1）压缩法

把一串数据压缩成一个。

比如: 各个位数字相加取平均值：h(378) = 6
h(‘abc’) = ‘b’

2) 除法

h(K) = K mod M
M最好取素数

3） 平方取中

这里的w指的是机器字长，也就是数据长度上限。

是表长

4） 抽取法

也就是仅仅抽取数据中的部分字段作为散列函数的自变量

2、冲突调节

1) 拉链法

即用链表来存储冲突元素

2） 线性探查法

发生冲突时寻找下一顺位
如何删除元素呢？
可以在每个元素上加一个标志位，标记该位置是否有元素。

九、最优二叉查找树

《最优二叉查找树》
重点在于这张图(这是前面那篇博客中的)：
dp表
dp表
do表

十、次优二叉查找树

《次优二叉查找树》
这个也太简单了我就不写了🐶