查找

在计算机科学中定义为：在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。也就是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。

查找

• 基本概念
  • 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
  • 查找表：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成
    • 静态查找表
      • 只需要查找操作
      • 顺序查找、折半查找、分块查找
    • 动态查找表
      • 除了查找，还需要增删数据元素
      • 二叉排序树、平衡二叉树
  • 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
  • 平均查找长度（ASL：Average Search Length）:在查找的过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值
    • 查找成功
    • 查找失败
    • 查找长度可能为0
    • ASL的数量级反应了查找算法的时间复杂度
• 顺序查找
  • 分析
    • 顺序查找(线性查找)，主要用于在线性表中进行查找。
    • 时间复杂度为O(n)
  • 算法思路
    • 从查找表的一端开始，顺序扫描查找表，依次将扫描到的关键字和待查找的值key进行比较。如果相等，则查找成功。如果扫描结束仍然没有发现相等的数据元素，则查找失败。
  • 代码
    • • 加哨兵则无需判断是否越界,效率更高
  • 优化
    • 若表中元素有序
      • 当前关键字大于（或小于）目标关键字时，查找失败
      • 优点：查找失败时ASL更少
      • 查找判定树
        • 成功结点的关键字对比次数=结点所在层数
        • 失败结点的关键字对比次数=其父节点所在层数
    • 若各个关键字被查概率不同
      • 可按被查概率降序排列
      • 优点：查找成功时ASL更少
• 折半查找
  • 分析
    • 折半查找，⼜称“⼆分查找”，仅适⽤于有序的顺序表。
    • 时间复杂度为O(logn)
  • 算法思路：
  • 代码
  • 扩展
    • 折半查找判定树
      • 对于折半查找，查找的比较次数就是从根结点到该结点经历的结点数
      • 构造
      • 特性
        • 折半查找的判定树是平衡的二叉排序树（左<中<右）
        • 折半查找判定树，只有最下面一层是不满的
        • 若查找表有n个关键字，则失败结点有n+1个
• 分块查找
  • 分析
    • 分块查找又称为索引顺序查找，数据分块存储，块内无序、块间有序
    • 由于分块查找实际是进行两次查找，所以整个算法的平均查找长度是两次查找的平均查找长度之和。即ASL分块=ASL折半+ASL顺序
    • 对索引表进行折半查找时，若索引表中不包含目标关键字，则折半查找最终停在low>high，要在low所指分块中查找
  • 算法思路
    • 索引表中记录每个分块的最大关键字、分块的区间
    • 先查索引表（顺序或折半）、再对分块内进行顺序查找
      • ①确定待查找值在哪个块（折半查找或顺序）②在确定的块中查找待查找值（顺序查找）
• B树和B+树
  • 2-3树
    • 2-3树是一种多路查找树：2和3的意思就是2-3树包含两种结点
      • 1)2结点包含一个元素和两个孩子(或者没有孩子)。 ①左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值 ②2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子
      • 2)3结点包含一大一小两个元素和三个孩子(或者没有孩子)。(两个元素按大小顺序排列好) ①左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。 ②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子
      • 3)2-3树所有叶子结点都在同一层次
  • 2-3-4树
    • 2-3-4树也是一种多路查找树：2和3和4的意思就是2-3-4树包含三种结点
      • 1)2结点包含一个元素和两个孩子(或者没有孩子)。 ①左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值 ②2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子
      • 2)3结点包含一大一小两个元素和三个孩子(或者没有孩子)。 ①左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。 ②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子
      • 3)4结点包含小中大三个元素和四个孩子(或者没有孩子)。 ①左子树包含的元素小于该结点最小的元素值，第二个子树包含大于最小的元素值小于中间元素值的元素，第三个子树包含大于中间元素值小于最大元素值的元素，右子树包含的元素大于该结点最大的元素值。 ②4结点要不有四个孩子，要不就没有孩子，不允许有一个或两个或三个孩子
      • 4)2-3-4树所有叶子结点都在同一层次
  • B树
    • B树也是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，我们把树中结点最大的孩子数目称为B树的阶。通常记为m。一棵m阶B树或为空树，或为满足如下特性的m叉树：
      • 1）树中每个结点至多有m棵子树。（即至多含有m-1个关键字) ("两棵子树指针夹着一个关键字")
      • 2）若根结点不是终端结点，则至少有两棵子树。(至少一个关键字)
      • 3）除根结点外的所有非叶结点至少有 ⌈m/2⌉棵子树。（即至少含有⌈m/2⌉-1个关键字）
      • 4）所有非叶结点的结构如下：
      • 5）所有的叶子结点出现在同一层次上，不带信息。(就像是折半查找判断树中查找失败的结点)
    • 1.B树的查找操作
      • 查找过程：①先让待查找关键字key和结点的中的关键字比较，如果等于其中某个关键字，则查找成功。 ②如果和所有关键字都不相等，则看key处在哪个范围内，然后去对应的指针所指向的子树中查找。 Eg:如果Key比第一个关键字K1还小，则去P0指针所指向的子树中查找，如果比最后一个关键字Kn还大，则去Pn指针所指向的子树中查找。
    • 2.B树的插入操作
      • 分裂的方法：取这个关键字数组中的中间关键字(⌈n/2⌉)作为新的结点，然后其他关键字形成两个结点作为新结点的左右孩子。
    • 3.B树的删除操作
      • B树中的删除操作与插入操作类似，但要稍微复杂些，要使得删除后的结点中的关键字个数≥⌈m/2⌉-1 ，因此将涉及结点的“合并”问题。由于删除的关键字位置不同，可以分为关键字在终端结点和不在终端结点上两种情况。
        • 1）如果删除的关键字在终端结点上（最底层非叶子结点）： ①结点内关键字数量大于⌈m/2⌉-1 ，这时删除这个关键字不会破坏B树的定义要求。所以直接删除。 ②结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中存在关键字数量大于⌈m/2⌉-1 的结点，则去兄弟阶段中借关键字。 ③结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中不存在关键字数量大于⌈m/2⌉-1 的结点，则需要进行结点合并。
        • 2）如果删除的关键字不在终端结点上（最底层非叶子结点）：需要先转换成在终端结点上，再按照在终端结点 上的情况来分别考虑对应的方法。
          • 相邻关键字：对于不在终端结点上的关键字,它的相邻关键字是其左子树中值最大的关键字或者右子树中值最小的关键字。
          • 第一种情况：存在关键字数量大于⌈m/2⌉-1 的左子树或者右子树，在对应子树上找到该关键字的相邻关键字，然后将相邻关键字替换待删除的关键字。
          • 第二种情况：左右子树的关键字数量均等于⌈m/2⌉-1 ，则将这两个左右子树结点合并，然后删除待删除关键字。
  • B+树
    • B+树是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构
    • m阶的B+树与m阶的B树的主要差异在于：1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有(n+1)棵子树。2）在B+树中，每个结点（非根内部结点）关键字个数n的范围是 ⌈m/2⌉≤n≤m（根结点1≤n≤m），在B树中，每个结点（非根内部结点）关键字个数n的范围是⌈m/2⌉ -1≤n≤m-1（根结点：1≤n≤m-1）。3）在B+树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。4）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。
• 散列表
  • 分析
    • 散列表(哈希表)：根据给定的关键字来计算出关键字在表中的地址的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。
    • 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。
    • 散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为“冲突”，这些发生碰撞的不同关键字称为同义词。
    • 散列表的查找性能：和装填因子有关。
      • α越大，表示装填的记录越“满”，发生冲突的可能性就越大，反之发生冲突的可能性越小
    • 典型的空间换时间的算法
  • 构造散列函数的tips：
    • 1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
    • 2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间，从而减少冲突的发生。
    • 3）散列函数应尽量简单，能够在较短的时间内就计算出任一关键字对应的散列地址。
  • 1.常用Hash函数的构造方法：
    • 1.直接定址法：直接取关键字的某个线性函数值为散列地址，散列函数为H(key)=a×key+b。式中，a和b是常数。这种方法计算最简单，并且不会产生冲突它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
    • 2.除留余数法：假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为H(key)=key % p除留余数法的关键是选好p，使得每一个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性
    • 3.数字分析法：设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，则应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合
    • 4.平方取中法：顾名思义，取关键字的平方值的中间几位作为散列地址。具体取多少位要看实际情况而定。这种方法得到的散列地址与关键字的每一位都有关系，使得散列地址分布比较均匀。适⽤于关键字的每位取值都不够均匀或均⼩于散列地址所需的位数。
    • 5.折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以短一些），然后取这几部分的叠加和作为散列地址，这种方法称为折叠法。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到散列地址。
  • 2.常用Hash函数的冲突处理办法：
    • 1.开放定址法：将产生冲突的Hash地址作为自变量，通过某种冲突解决函数得到一个新的空闲的Hash地址。
      • 数学递推公式
      • 方法
        • 1）线性探测法：冲突发生时，顺序查看表中下一个单元（当探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。
        • 2）平方探测法：设发生冲突的地址为d,平方探测法得到的新的地址序列为d+12，d-12，d+22，d-22......平方探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
        • 3）再散列法：又称为双散列法。需要使用两个散列函数，当通过第一个散列函数H(Key)得到的地址发生冲突时，则利用第二个散列函数Hash2(Key)计算该关键字的地址增量。
        • 4）伪随机序列法：当发生地址冲突时，地址增量为伪随机数序列，称为伪随机序列法。
    • 2.拉链法：对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。拉链法适用于经常进行插入和删除的情况。
    • 3.散列表的查找过程：类似于构造散列表，给定一个关键字Key。 先根据散列函数计算出其散列地址。然后检查散列地址位置有没有关键字。 1)如果没有，表明该关键字不存在，返回查找失败。 2)如果有，则检查该记录是否等于关键字。 ①如果等于关键字，返回查找成功。 ②如果不等于，则按照给定的冲突处理办法来计算下一个散列地址，再用该地址去执行上述过程。