常用查找算法

顺序查找

存储结构为顺序存储或链接存储的线性表

查找的时间复杂度为 $O(N)$

二分查找

元素必须是有序的

每次将目标值与中间节点的值进行比较,再判断其落入中间节点的左侧或右侧。

可以使用迭代或递归实现。

插值查找

二分查找进阶

联系查字典,将二分查找中的 $mid = \frac{low + high}{2}$ 修改为自适应的 $mid = low + (key - a[low]) / a[high] - a[low]) * (high -low)$ 及将二分查找中的比例 0.5 改为自适应的值,根据关键字在表中的位置,让下一次查找更靠近关键字,从而减少了查找的次数。

插值查找一般适用于表长较大,同时关键字分布较为均匀的表。

复杂度:$O(log_2(log_2n))$

斐波那契查找

类比二分查找,当表长等于某斐波那契数时使用。

最坏情况时间复杂度为 $O(log_2n)$,期望复杂度 $O(log_2n)$

二叉树查找

二叉搜索树的特点是左子节点小于父节点,父节点小于右子节点。

此方案的查找效率较高,但是需要维护二叉树,并且在查找树严重不平衡时退化为“链表”。

将二叉搜索树进行优化,可以参考平衡二叉树、红黑树。

平衡查找树

2-3 Tree

每个节点保存1个或2个值(对应可以拥有2个或3个子节点)

性质:在一个完全平衡的2-3查找树中,根节点到每一个叶节点的距离都相同。

红黑树

红黑树的思想是对2-3查找树进行编码,特别是对其中的3-node节点添加额外的信息。

红黑树

可以想像两个红色边链接的节点对应2-3查找树中的3-node。

红黑树的定义:

  • 红色节点向左倾斜;
  • 一个节点不可能有两个红色连接;
  • 根节点到每个叶节点的黑色链接个数相同。

红黑树的应用:

  • Java: Java.util.TreeMap, Java.util.TreeSet;
  • C++: STL::map, STL::multimap, STL::multiset;
  • .NET: SortedDictionary, SortedSet

B树

B树可以看作是2-3查找树的拓展,其每个节点允许有M-1个子节点

B树的定义

  • 根节点至少有两个子节点
  • 每个节点有M-1个key,并以升序排列
  • 其他节点至少有 M/2 个子节点

基本操作演示动画:

btreebuild

B树的优点:

  • 每一个节点包含 key 和 value, 因此经常访问的元素可能距离根节点更近,可以更快访问。

B+树

B+树的定义

  • 有 k 个子节点的节点必然有 k 个关键码
  • 非叶节点仅具有索引作用
  • 叶节点存放记录相关的信息
  • 树的所有叶节点构成一个有序链表,可以按照关键码排序的次序遍历全部记录

试想一下,在文件系统中,若该文件在磁盘上的分区恰好不属于同一个父节点,此时B+树与B树的性能差异

290050048129679

如下为B+树的操作动画:

Bplustreebuild

B+树的优点:

  • 内部节点不含数据信息,内存页可以存放更多的key。
  • 数据存放紧密,具有更好的空间局部性,访问叶节点关联的数据具有更高的缓存命中率。
  • 叶节点构成有序链表,对整棵树的遍历更快。
  • 便于区间查找与搜索。(非同父节点时优势明显)

B树/B+树的应用:

  • Windows: HPFS
  • Mac: HFS, HFS+
  • Linux: ResiserFS, XFX, Ext3FS, JFS
  • 数据库: ORACLE, MySQL, SQLServer

分块查找

每一块中数据不必有序。 但快间数据有序。 (类比快排的中间步骤)

算法步骤:

  • 选取各块中的最大关键字构成索引表
  • 二分查找确定索引块
  • 索引块内顺序查找目标值

哈希查找

哈希函数:使关键字分散到指定大小的顺序结构的转换关系。

算法流程:

  • 使用哈希函数构造哈希表
  • 解决地址冲突
    • 拉链法
    • 线性探测法
  • 执行哈希查找