查找

基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
查找表(查找结构)：用于查找的数据集合称为查找表，它由同一类型的数据元素(或记录组成)
关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的(比如学号)

常见操作

  1. 查找符合条件的数据元素
  2. 插入、删除某个数据元素

如果只进行操作1——静态查找表即可
也要进行操作2——动态查找表

评价指标
查找长度：在查找运算中，需要对比关键字的次数称为查找长度
平均查找长度(ASL)：所有查找过程中进行关键字的比较次数的平均值

$\displaystyle ASL=\sum_{i=1}^nP_iC_i$
其中n为数据元素个数，C_i为查找第i个元素的查找长度，P_i为查找第i个元素的概率

ASL的数量级放映了查找算法时间复杂度
评价一个查找算法的效率时，通常考虑查找成功/失败两种情况的ASL

顺序查找

顺序查找，又叫“线性查找”，通常用于线性表(顺序表、链表)
算法思想：从头到尾一个一个对比

顺序查找的实现

// 查找表的数据结构(顺序表)
typedef struct {
    // 动态数组的基址(剩下靠偏移量)
    Elemtypr *elem;
    // 表的长度
    int TableLen;
}SSTable;

// 顺序查找
int Search_Seq(SSTable ST, ElemType key) {
    int i;
    // for循环空语句
    for (i=0;i<ST.TableLen && ST.elem[i] != key; i++);
    // 查找成功，则返回元素下标；查找失败，则返回-1
    return i==ST.TaqbleLen? -1 : i;
}

顺序查找的实现(哨兵)
索引为0空出来存key

typedef struct {
    // 动态数组的基址(剩下靠偏移量)
    Elemtypr *elem;
    // 表的长度
    int TableLen;
}SSTable;

// 顺序查找
int Search_Seq(SSTable ST, ElemType key) {
    ST.elem[0] = key;// 哨兵
    int i;
    for (i=ST.TableLen; ST.elem[i]!=key;i--);
    return i;//查找成功，则返回元素下标，查找失败，则返回0
}

优点在于无序判断是否越界

上面两种的效率都是O(n)

顺序查找的优化(对有序表)
查找表中元素有序存放

查找判定树(其实就是全部只有右子树的二叉排序树)

  • 成功节点的关键字对比次数=结点所在的层次
  • 失败结点的关键字对比次数=其父节点所在层数

顺序查找的优化2(被查概率不相等)
被查找概率大的元素放在靠前的位置

顺序查找的时间复杂度都是O(n)

折半查找

折半查找，又称为“二分查找”，仅适用于有序的顺序表。

一开始

  • low=0,high=TableLen-1，得到mid=(low+high)/2向下取整
  • 将key的元素与mid位置进行比较，然后low或者high赋值为mid-1或者mid+1
  • 重复上面的过程，直到low=high

折半查找

int Binary_Search(SSTable L,ElemType key) {
    int low=0,high = L.TableLen-1,mid;
    while(low<=high){
        //  取中间位置
        mid = (low+high)/2;
        if(L.elem[mid]==key)
            // 查找成功则返回所在位置
            return mid;
        else if(L.elem[mid]>key)
            // 从前半部分继续查找
            high = mid-1;
        else 
            // 从后半部分继续查找
            low = mid+1;
    }
    // 查找失败，返回-1
    return -1;
}

折半查找的查找效率为O(log_2n)
在不考虑失败节点的情况下，折半查找的判定树，右子树结点数-左子树结点数=0或1

折半查找的判定树一定是平衡二叉树
折半查找的判定树中，只有最下面一层是不满的，因此，元素个数为n时树高 $h=\lceil\log_2(n+1)\rceil$

分块查找

特点：块内无序块间有序
比如： 7 10 13 19 16 20 27 22 30 40 36 43 50 48

我们看这个例子看起来无序，但是分成一块一块的确是有序的

索引表中保存每个分块的最大关键字和分块的存储区间

// 索引表
typedef struct {
    ElemType maxValue;
    int low , high;
}Index;

// 顺序表存储实际元素
ElemType List[100];

因此上面那个例子的索引表就是

10 20 30 40 50
[0,1] [2,5] [6,8] [9,10] [11,13]

然后先和索引表中每个块的最大值对比，来确定哪一块

分块查找，又称索引顺序查找，算法过程如下：

  1. 在索引表中确定待查记录所属的分块(可顺序、可折半)
  2. 在块内顺序查找

折半查找要注意可能会low < high，这时候要查low对应的分块，当low超出索引时，说明查找失败

B树

二叉排序树

// 二叉排序树结点
typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

二叉排序树实际上就是通过一个key，把范围分成两份为左右孩子，可以根据这个原理拓展到m叉查找树，例如:5叉查找树

// 5叉排序树的结点定义
struct Node {
    ElemType keys[4]; // 最多4个关键字 
    struct Node * child[5];// 最多5个孩子
    int num; // 结点中有几个关键字
}

若每个结点内关键字太少，导致树变高，要查找更多层结点，效率低
策略：m叉查找树中，规定除了根节点外，任何结点至少有 $\lceil m/2\rceil$ 个分叉，即至少含有 $\lceil m/2\rceil-1$ 个关键字

B树，又称多路平衡查找树，B树种所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的二叉树：

  1. 树中每个结点至多有m棵子树，即至多含有m-1个关键字
  2. 若根节点不是终端结点，则至少有两棵子树
  3. 除根节点外的所有非叶子结点至少有 $\lceil m/2 \rceil$ 棵子树，即至少含有 $\lceil m/2\rceil-1$ 个关键字
  4. 所有的叶子节点都出现在同一层次上，并且不带信息，可以认为是外部节点或类似于折半查找判定树的查找失败结点，实际上这些节点不存在，指向这些节点的指针为空
  5. 所有非叶子节点的结构如下
n P_0 K_1 P_1 … K_n P_n

其中K_i(i=1,2,…,n) 为结点的关键字，且满足K_1< K_2 <…< K_n,P_i(i=0,1,2,…,n) 为指向子树根节点的指针，且指针P_{i-1} 所指子树中所有节点的关键字均小于K_i，P_i所指子树中所有结点的关键字均大于K_i,n为结点中关键字的个数。

m阶B树的核心特征：

  1. 根节点的子树数 $\in[2, m]$，关键字数 $\in[1,m-1]$，其他根节点的子树数 $\in[\lceil m/2\rceil,m]$，关键字数 $\in[\lceil m/2\rceil-1, m-1]$
  2. 对任一结点，其所有子树高度都相同
  3. 关键字的值：子树0<关键字1<子树1<关键字2<子树2<…..

问题：含有n个关键字的m叉B树，最小高度、最大高度是多少?
最大高度：让每个结点包含的关键字、分叉尽可能的少。记 $k=\lceil m/2\rceil$

  最少结点数 最少关键字数
第一层 1 1
第二层 2 2(k-1)
第三层 2k 2k(k-1)
第四层 $2k^2$ $2k^2(k-1)$
… … …
第h层 $2k^{h-2}$ $2k^{h-2}(k-1)$

h层的m阶B树至少包含关键字总数 $1+2(k-1)(k^0+k^1+\cdots+k^{h-2})=1+2(k^{h-1}-1)$
若关键字总数少于这个值，则高度一定小于h，因此 $n\geqslant 1+2(k^{h-1}-1)$，得 $h\leqslant \log_k\dfrac{n+1}{2}+1=\log_{\lceil m/2\rceil}\dfrac{n+1}{2}+1$

B树的插入和删除

插入

这里以5阶B树为例：结点关键字个数 $\rceil m/2\rceil-1\leqslant n\leqslant m-1$，即 $2\leqslant n\leqslant 4$(此处省略失败结点)

25|38|49|60

这个结点已经满了，再插入一个结点80，需要进行一个分裂，变成

   49|||
   /    \
25|38||  60|80||

在插入key后，若导致原结点关键字字数超过上限，则从中间位置 $(\lceil m/2\rceil)$ 将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右节点部分包含的关键部分放到新结点中，中间位置 $(\lceil m/2\rceil)$ 的结点插入原节点的父节点
若此时导致其父节点的关键字个数也超过了上限，则继续进行这种分裂操作，直到这个过程传到根节点为止，进而导致B树高度增加1

核心要求：

  • 对m阶B树：根节点除外，结点关键字个数 $\rceil m/2\rceil-1\leqslant n\leqslant m-1$
  • 子树0 < 关键字1 < 子树1 < 关键字2 <…

新元素一定是插入到最底层“终端结点”，用“查找”来确定插入位置

删除

若被删除关键字在终端结点，则直接删除该关键字(要注意结点关键字个数是否低于下限)

若被删除关键字在非终端节点，则直接用前驱或者后继来替代被删除的关键字
直接前驱：当前关键字左侧指针所指子树中最右下的元素(其实就是左侧子树中“最大”的元素)
直接后继：当前关键字右侧指针所指子树中“最左下”的元素（其实就是右侧子树中“最小”的元素）

若删除关键字所在结点删除后的关键字个数低于下限，且与此结点右(或左)兄弟结点的关键字个数还很宽裕，则需要调整该结点、右(或左)兄弟结点及其双亲结点(父子换位法)(有点像旋转)

例如：

          49|73||
         /   \
   25|38||   70|71|72|

5阶B树的关键字下限为2，因此删除38后，低于下限，得到

          49|73||
         /   \
   25|||     70|71|72|

右兄弟结点关键字个数多于下限，因此旋转，父节点左旋到当前结点，兄弟结点左旋到父节点，得到

          70|73||
         /   \
   25|49||     71|72||

当前结点的后继和后继的后继，借左兄弟关键字类似

兄弟不够借。若删除关键字所在结点删除后的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均 $=\lceil m/2 \rceil-1$，则将关键字删除后与左(或右)兄弟结点及双亲结点中的关键字进行合并

在合并过程中，双亲结点中的关键字个数为减1。若其双亲结点是根节点且关键字个数减少至0(根节点关键字个数为1是，有两棵子树)，则直接将根节点删除，合并后的新结点成为根；若双亲结点不是根节点，且关键字个数减少到 $\lceil m/2 \rceil-2$，则又要与它自己的兄弟节点进行调整或合并操作，重复上述步骤，直至符合B树的要求为止。

B+树

B+树和分块查找很类似

一棵m阶的B+树需要满足下列条件：

  1. 每个分支结点最多有m棵子树（孩子结点）
  2. 非叶根结点（不是叶子的根节点，因为只有一层的时候即时根节点又是叶子）至少有两棵子树，其他每个分支节点至少有 $\lceil m/2 \rceil$ 棵子树
  3. 结点的子树个数与关键字个数相等
  4. 所有叶子结点包含全部关键字及指向相应记录的指针，叶子节点中将关键字按大小顺序排列，并且相邻叶子结点按大小顺序互相链接起来（因此支持顺序查找）
  5. 所有分支节点中仅包含它的各个子节点中关键字的最大值及指向其子节点的指针

在B+树种，无论查找成功与否，最终都一定要走到最下面一层结点

在B+树中，非叶子结点不含有该关键字对应记录的存储地址。可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，树高更小，读磁盘次数更少，查找更快

 || 类比| 关键字与分叉| 结点包含的信息| 查找方式| 相同点|

散列查找

散列表(Hash Table)

散列表(Hash Table)，又称哈希表。是一种数据结构，特点：数据元素的关键字与其存储地址直接关联

如果建立“关键字”与“存储地址”的联系？
通过“散列函数(哈希函数)”：Addr=H(key)

例如：有一对数据元素，关键字分别为{19,14,23,1,68,20,84,27,55,11,10,79}，散列函数为 H(key)= key%13

14%13=1，那14 就存在数组1的位置
如果不同关键字通过散列函数映射到同一个值，则称他们为“同义词”
通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”

解决冲突的方法：拉链法(又称链接法、链地址法)处理“冲突”：把所有“同义词”存储在一个链表中

比如：14%13=1
1%13=1，这样数组1的位置就会冲突，那么就可以，在数组1的位置存储链表的链头

比如数组8的位置没有任何元素，那么查找长度为0(一般当成0，看具体教材)

装填因子=表中记录数、散列表长度
装填因子会直接影响散列表的查找效率

冲突越少，查找的效率越高
常见的散列函数：

  • 除留余数法：H(key)=key%p
    • 散列表表长为m，取一个不大于m但最接近或等于m的质数p(有可能散列表的有些位置永远用不到)
  • 直接定址法：H(key)=key 或H(key) = a*key+b
    • 其中a和b是常数，这种方法计算最简单，且不会产生冲突，适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费
  • 数字分析法：选取数码分布较为均匀的若干位作为散列地址
  • 平方取中法：取关键字的平方值的中间几位作为散列地址

散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低

开放定址法

开放定址法：指可以存放新表项的空闲地址既向它的同义表项开放，又向它的非同义表项开放。其数学递推公式为 $H_i=(H(key)+d) %m$ ,i=0,1,2,…,k，m表示散列表长，d_i为增量序列,i可理解为第i次发生冲突

线性探测法：即发生冲突时，每次往后探测相邻的下一个单元是否为空

查找的时候，先计算散列函数，然后从指定位置向后查找，会有两种情况，找到和找到空位置，找到空位置表示查找失败

我们知道查找失败的判定后，知道删除结点不能单纯的将空间置空，而应当做一个删除标记，使得线性探测可以继续下去

线性探测法很容易造成同义词、非同义词的“聚集(堆积)”现象，严重影响查找效率，产生原因：冲突后，再探测一定是放在某个连续的位置

平方探测法

当 $d_i=0^21^2-1^2,2^2,-2^2,…,k^2,-k^2$ 时名称为平方探测法，又称二次探测法，其中 $k\leqslant m/2$

平方探测法：比起线性探测法更不容易产生“聚集”问题

坑：散列表长度m必须时可以表示成4j+3的素数，才能探测到所有位置

伪随机序列法

$d_i$ 是一个伪随机序列

再散列法

再散列法：除了原始的散列函数 H(key) 之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，知道不冲突为止