8.查找

查找 又称检索. 当问题所涉及的数据量很大时, 查找效率就格外重要. 整个查找过程都在内存中进行即内查找, 反之, 称为外查找.

查找的主要操作是关键字的比较, 因此通常把平均比较次数/平均查找长度作为衡量效率的标准.

顺序表的查找

本章假定顺序表采用一维数组来表示.

顺序查找 / 线性查找

1. 从开始元素顺序扫描顺序表, 比较每个记录的关键字和查找值 k. 若等于 k, 则查找成功, 返回该记录的下标
2. 直到所有记录都比较完, 仍未找到与 k 相等的记录, 则查找失败

二分查找 / 折半查找

要求线性表必须有序 (设为递增).

1. 将查找值和有序表中间位置的记录关键字比较
2. 若相等则查找成功
3. 若小于中间记录, 继续在左子表中进行二分查找
4. 若大于中间记录, 继续在右子表中进行二分查找

索引顺序查找 / 分块查找**

要求表是 分块有序 的, 是介于顺序查找和二分查找之间的查找方法:

1. 分块有序: 将表 R[1..n] 均分为 b 块, 每块各 n/b 个结点 (最后一块可能不足). 每块中的结点不一定有序, 但前一块中的最大关键字必须小于后一块的最小关键字
2. 构建索引表 ID[1..b], ID[i] 中存放着第 i 块的最大关键字及该块在 R 中的起始位置. 显然 ID 是按关键字递增有序的
3. 先在索引表中利用二分或顺序查找, 确定所在块
4. 然后在块中进行顺序查找

树表的查找

二叉排序树 (Binary Sort Tree, BST) / 二叉查找树

BST 具有下列性质:

1. 若它的右子树非空, 则右子树上所有结点的值均大于根结点的值
2. 若它的左子树非空, 则左子树上所有结点的值均小于根结点的值
3. 左, 右子树本身又各是一颗二叉排序树
4. 由上面三个性质可推出, 它的中序遍历序列是一个递增有序序列

插入新结点:

1. 若 BST 为空, 则把新结点作为根结点插入到空树
2. 若 BST 非空, 比较新结点和根结点:
   • 相等, 说明已经有此结点, 无需插入
   • 新结点较小, 插入到左子树
   • 新结点较大, 插入到右子树
3. 在子树中插入过程同上, 如此进行下去

查找关键字: 将 BST 看成有序表, 与二分查找类似:

1. 若 BST 为空, 查找失败
2. 若待查找关键字等于根结点的关键字, 查找成功
3. 若待查找关键字小于根结点的关键字, 继续在根结点的左子树查找
4. 若待查找关键字大于根结点的关键字, 继续在根结点的右子树查找

删除结点: 假设删除结点 p, 删除之后仍要满足 BST 性质:

1. 若 p 是叶子结点, 则直接删除
2. 若 p 只有一颗子树, 直接用 p 的子树取代 p
3. 若 p 既有左子树又有右子树, 任选以下方式之一处理
   • 用 p 的直接前趋结点 (左子树中最大的结点, 位于左子树中最右边且没有右子树) 代替 p
   • 用 p 的直接后继结点 (右子树中最小的结点, 位于右子树中最左边且没有左子树) 代替 p

BST 的算法性能取决于其深度, 所以有很多动态平衡的方法, 使得向树中插入或删除结点时, 通过调整树的形态来保持树的平衡, 使其既满足 BST 的性质, 又保证树的深度始终是 O(logn), 这种 BST 就是所谓的平衡二叉树.

B 树

B 树 是一种平衡的多路查找树, 它在文件系统中非常有用. 一颗 m(m>=3) 阶的 B 树或为空树, 或为满足以下性质的 m 叉树:

• 每个结点至少包含下列信息域: (n, p0, k1, p1, k2, ..., kn, pn)
  • n 为关键字的个数
  • k 为关键字
  • p 为指向子树根结点的指针, 且 p 所指向的子树中所有结点均大于其前邻的 k, 小于其后临的 k
  • 注意, p 的个数总是比 k 的个数多 1
• 每个结点至多有 m 棵子树
• 若树非空, 则根结点至少有 1 个关键字, 至多有 m-1 个关键字
• 所有的叶子结点都在同一层次上, 并且不带信息 (可看做外部结点或查找失败的结点)
• 除根之外的所有非终端节点所包含的关键字个数满足: ⌈m/2⌉-1 ≤ n ≤ m-1, 故至少有 ⌈m/2⌉ 棵子树, 至多有 m 棵子树

插入新结点

1. 先在最底层的某个非终端结点中添加一个关键字
2. 若结点中关键字个数仍不超过 m-1, 插入完成
3. 否则要产生结点 "分裂"
   1. 把结点分成两个, 将中间的一个关键字拿出来插入到该结点的双亲结点
   2. 如果双亲结点已有 m-1 个关键字, 则导致双亲结点继续分裂
   3. 这一过程可能波及 B 树的根结点, 引起根结点的分裂, 从而使 B 树长高一层

删除结点

1. 首先找到要删除的关键字所在的结点
2. 若该结点不在含有信息的最后一层, 则将该关键字用其后继关键字替代, 然后再删除其后继关键字信息. 因此, 最终始终是要删除一个最下层结点中的关键字, 此时:
   • 若结点中关键字数目不小于 ⌈m/2⌉, 只需删除关键字和响应指针即可.
   • 若结点中关键字数目等于 ⌈m/2⌉-1, 即数目已经是最小值, 直接删除会破坏性质:
     • 若结点左 (或右) 邻兄弟结点关键字数目不小于 ⌈m/2⌉
       1. 将其兄弟结点中最大 (最小) 关键字上移至双亲结点
       2. 将双亲结点中相应的关键字移至被删关键字所在结点中
     • 若结点相邻左右兄弟结点中关键字数目都等于 ⌈m/2⌉-1:
       1. 需将被删结点与某个兄弟结点**"合并"**
       2. 这一过程可能波及根, 引起对根结点中关键字的删除, 从而可能是 B 树高度降低一层

查找关键字: 类似 BST, 但需要经过与多个关键字比较后才能处理完一个结点, 故称 B 树为 多路查找树

1. 设查找给定值 K, 将每个结点的 key[0] 作为哨兵存储 K 值
2. 若 B 树非空, 则先取出树根结点, 将 K 一次从右向左与根结点中每个关键字比较, 直到找到一个小于等于 K 的关键字, 此时:
   • 若找到的关键字与 K 相等, 且不是 key[0], 则表明查找成功
   • 否则, 继续在所找到的关键字对应的子树中继续查找即可

B⁺ 树

B⁺ 树是一种常用于文件组织的 B 树的变形. 一颗 m 阶的 B⁺ 树与 B 树的区别在于:

• 有 k 个孩子的结点中含有 k 个关键字.
• 所有叶子结点中包含了全部关键字的信息, 及指向含有这些关键字记录的指针, 且叶子结点本身依照关键字从小到大顺序链接.
• 所有非终端结点可看成索引部分, 结点中仅含有其子树 (根结点) 中的最大 (或最小) 关键字.

因此, 可以对 B+ 树进行两种查找运算:

• 一种是从最小关键字其进行顺序查找
• 另一种是从根结点开始进行随机查找

散列表查找

散列存储的基本思想: 以线性表中每个元素的关键字为自变量, 通过一种函数 H(key) 计算出函数值, 把这个函数值解释为连续存储空间的单元地址, 将该元素存储到这个单元中.

• 其中使用的函数称为散列(哈希)函数, 它实现关键字到存储地址的映射
• 得到的函数值称为散列(哈希)地址
• 使用的数组空间是线性表进行散列存储的地址空间, 称为散列(哈希)表

多个元素经过散列函数计算, 可能得到相同的散列地址, 这种现象称为散列(哈希)冲突. 具有相同散列地址的关键字称为同义词. 冲突的频度与下列因素相关:

• 设计不良的散列函数. 因此设计散列函数时, 要考虑避免或尽量减少冲突
• 散列表中已占用的单元数和散列表表长之比, 称为 装填因子. 装填因子越大, 冲突机会越大

常用的散列函数有:

• 直接地址法: H(key) = key + C. 适合关键字分布基本连续的情况, 否则空号较多, 造成空间浪费
• 数字分析法: 假设每个关键字由多位数字组成, 提取数字分布比较均匀的若干位作为散列地址
• 除余数法: H(key) = k % p. 其中 p 最好选取小于或等于表长的最大素数
• 平方取中法: 取关键字平方的中间几位作为散列地址. 因为乘积的中间几位和乘数的每一位都相关, 故散列地址较均匀
• 折叠法: 将关键字分割成位数相同的几段, 段的位数等于散列地址的位数, 然后所有段的叠加和为散列地址

处理散列冲突

散列冲突一般不可避免, 因此需要处理冲突:

开放定址法: 根据探查序列逐个单元查找, 直到找到空闲单元. 设初始探查地址为 d:

• 线性探查法: 将散列表看成循环向量, 依次探查, 直到循环到初始探查单元的前一单元
• 二次探查法: 探查序列为 d+1^2, d-1^2, d+2^2, d-2^2, ...
• 双重散列法: 探查序列为 d, (d+1*h(key))%m, (d+2*h(key))%m, ... 其中 h 是不同于 H 的散列函数

拉链法: 每个地址都有对应的一条链表, 把同义词放到同一单链表中.

性能

• 仍然有一个与关键字比较的过程, 但是比顺序查找小得多, 比二分查找也小
• 平均查找长度不是结点数的函数, 而是装填因子的函数. 只要装填因子选择合适, 平均查找长度就是一个常数