Chapter 8. Search

第 8 章 查找

查找概论

  • 查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。

  • 关键字（Key）是数据元素中某个数据项的值（键值），对应某个数据项，称为关键码

  • 若从关键字可以唯一地标志一个记录，则称此关键字为主关键字（Primary Key），对应数据项为主关键项

  • 对于那些可以识别多个数据元素（或记录）的关键字，我们称为次关键字（Secondary Key），对应次关键项

查找就是根据给定的某个值，在表中确定一个其关键字等于给定值的数据元素（或记录）。

查找表按照操作方式可分为两种

  • 静态查找表（Static Search Stable）：只作查找操作的查找表。

  • 动态查找表（Dynamic Search Stable）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

顺序表查找

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找出所查的记录；如果知道最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

顺序表查找优化

常见的算法是利用数组循环进行if判断。

可以优化为利用while和数组首项进行返回值判断......（略）：哨兵技巧

  • 利用数值的变化来取代if判断

时间复杂度为 O(n2)

有序表查找

折半查找

又称二分查找（Binary Search）技术，它的前提是线性表中的记录必须是关键码有序（通常从小大大），线性表必须采用顺序存储。

折半查找的基本思想就是每次与中间值比较，以此确定下一次比较的区间（中间值），直到查找成功，或所有查找区域无记录，查找失败为止。

时间复杂度为O(logn)

插值查找

插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心在于插值公式 (key-a[low]) / (a[high]-a[low])

斐波那契查找

线性索引查找

索引是把一个关键字与它对应的记录相关联的过程

所谓线性索引就是将索引项集合组织为线性结构，也称为线性表

稠密索引

线性索引中，将数据集中每个记录对应一个索引项

对于稠密索引来说，索引项一定是按照关键码有序排列的

分块索引

分块有序是把数据集的记录分成了若干块，并且这些块需要满足以下两个条件：

  • 块内无序：通常不追求，会浪费更多的时间和空间计算性能，性价比低

  • 块间有序

最大关键码

块长

块首指针

存储每一块中的最大关键字

存储块中的记录个数

用于指向块首数据元素的指针

倒排索引

索引项的结构：

  • 次关键码

  • 记录号表

其中记录号表存储具有相同次关键字的所有记录的记录号（可以指向记录的指针，或者是该记录的主关键字），这样的索引方法是倒排索引（inverted index）

二叉排序树

希望同时实现高效率的插入删除和查找

二叉查找树（Binary Sort Tree），可以为空树，若不为空，须满足：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值

  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

  • 它的左、右子树也分别为二叉排序树

二叉排序树的删除操作

查找、插入操作都运用了递归函数的思想，而删除操作比较麻烦

需要保证删除后仍满足二叉排序树：

  • 若删除元素为叶子结点，操作较为简单

  • 若删除元素只有左、或只有右子树，也很简单，子承父业

  • 若删除元素同时拥有左、右子树：需要考虑让结点的前驱结点继承位置......

平衡二叉树（AVL树，重点！！！）

平衡二叉树（Self-Balancing Binary Tree或Height-Balanced Binary Search Tree）是一种二叉排序树，其中每个结点的左子树和右子树的高度差不多，达到高度平衡

  • 我们将二叉树上做结点的左子树的高度减去右子树的高度的值称为平衡每一个因子BF（Balanced Factor），那么平衡二叉树的BF，只能说是-1,0,1。

  • 距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。

多路查找树（B树）

（Multil-Way Search Tree），其结点的孩子数可以多于两个，且每个结点处可以存储多个元素。

2-3树

  • 其中的每一个结点都具有两个孩子（称为2结点）或三个孩子（称为3结点）

  • 一个2结点包含一个元素和两个孩子（或没有孩子）

  • 一个3结点包含一小一大两个元素和三个孩子（或没有孩子）

2-3-4树

是2-3树的拓展，包括了4结点的使用，一个4结点包含小中大3个元素和4个孩子（或没有孩子）

B树

B树（B-Tree）是一种平衡的多路查找树，结点大的孩子数目称为B树的阶（order），因此2-3树是3阶B树，2-3-4树是4阶B树

B+树

散列表查找（哈希表）概述

  • 存储位置=f（关键字）

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每一个关键字key对应一个存储位置f（key）

对应关系f称为散列函数，又称为哈希（Hash）函数，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash Table）

  • 散列技术既是一种存储方法，也是一种查找方法

  • 散列技术最适合的求解问题是查找与给定值相等的记录

编号

姓名

地址

1

张三丰

体育馆

2

爱因斯坦

图书馆

散列函数应该让冲突尽量少

散列函数的构造方法

要点：

  1. 计算简单

  2. 散列地址分布均匀

直接定址法

取关键字的某个线性函数值为散列地址

f（key）=a*key+b（a、b为常数）

适合表较小且连续的情况

数字分析法

抽取关键字的一部分来计算散列存储位置的方法

适合处理关键字位数比较多的情况

平方取中法

例：关键字1234，平方为15522756，取中3位227，作为散列地址

适合不知道关键字的分布，而位数又不是很多的情况

折叠法

将关键字从左到右分割成位数相等的几部分，然后叠加求和，取后几位作为散列地址、

适合事先不需要知道关键字的分布，关键字位数较多的情况

除留余数法

最常用的方法，对于散列表长为m的散列函数公式为：

f（key）=key mod p（p<=m）

随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址

选择不同散列函数的参考因素

  1. 计算散列地址所需时间

  2. 关键字的长度

  3. 散列表的大小

  4. 关键字的分布情况

  5. 记录查找的频率

处理散列冲突的情况

相当于两个自变量对应同一个函数值，散列函数发生冲突

开放定址法

一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入

fi（key）=（f（key）+di）MOD m（di=1，2，3……，m－1）

解决冲突的开放定址法称为线性探测法

堆积现象：可能要连续使用好几次开放定址法才能找到空位存下，大大降低了存入和查找效率

处理堆积现象的探测法

  • 增加平方运算的目的是不让关键字都聚集在某一块区域。称为二次探测法

fi（key）=（f（key）+di）MOD m（di=12，-12，22，-22，……，q2，-q2，q<=m/2）

  • 另一种方法是，在冲突时，对于位移量di用随机函数rand来计算得到，称为随机探测法

fi（key）=（f（key）+di）MOD m（ di=rand() ）

再散列函数法

在遇到除留余数法发生冲突时，换称折叠法，换成平方取中法等等，总有一个方法可以把冲突解决掉，使得关键字不产生聚集

链地址法

直视冲突，冲突发生时，不妨建立一个链表，遇到冲突就增加结点，提供了绝不会出现找不到地址的保障（通过地址的一对多实现）

公共溢出区法

创建两个表变量（基本表、溢出表）

将发生冲突的关键字存储到另外溢出表中，在查找时，现在基本表查找，再在溢出表查找

适用于有冲突数据很少的情况

散列表查找实现

散列表查找的性能分析

时间复杂度为 O(1)

相关因素：

  1. 散列函数是否均匀

  2. 处理冲突的方法

  3. 散列表的装填因子

PreviousChapter 7 DiagramNextChapter 9 Sorting

Last updated