查找的基本概念

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

对查找表的常见操作：

  • 查找符合条件的数据元素
    • 静态查找表
    • 仅关注查找速度即可
  • 插入、删除某个数据元素
    • 动态查找表
    • 除了查找速度，也要关注插/删操作是否方便实现

查找算法的评价指标：

  • 查找长度：在查找运算中，需要对比关键字的次数称为查找长度
  • 平均查找长度（ASL, Average Search Length ）：所有查找过程中进行关键字的比较次数的平均值
  • ASL的数量级反应了查找算法的时间复杂度
  • 评价一个查找算法的效率时，通常考虑查找成功、查找失败两种情况的ASL

image-20220701013406670

顺序查找

定义：

顺序查找，又叫“线性查找”，通常用于线性表。

算法思想：从头到尾依次往后找

顺序查找的实现：

image-20220701151536879

顺序查找的实现（哨兵）：

image-20220701151827383

优点：无需判断是否越界，效率更高

image-20220701152837860

顺序查找的优化（对有序表）：

image-20220701153017046

用查找判定树分析ASL：

  • 一个成功结点的查找长度 = 自身所在层数
  • 一个失败结点的查找长度 = 其父结点所在层数
  • 默认情况下，各种失败情况或成功情况都等概率发生

顺序查找的优化（被查概率不相等）：

image-20220701153410901

折半查找

算法思想：

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

查找成功：

注意：下面的mid向下取整

image-20220701154001670

image-20220701154106771

image-20220701154125509

image-20220701154142034

查找失败：

image-20220701154301062

代码实现：

image-20220701154531085

查找效率分析：

image-20220701155215243

折半查找判定树的构造：

  • 如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分比右半部分少一个元素
  • 如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等
  • 折半查找的判定树中,mid = [(low + high)/2]则对于任何一个结点，必有：右树结点数-左子树结点数=0或1
  • 折半查找的判定树一定是平衡二叉树
  • 折半查找的判定树中，只有最下面一层是不满的因此，元素个数为n时树高h = [log2(n + 1)]
  • 判定树结点关键字：左<中<右，满足二叉排序树的定义
  • 失败结点：n+1个（等于成功结点的空链域数量）
  • 折半查找的时间复杂度 = O(log2n)

分块查找

算法思想：

image-20220701161411895

  • 特点：块内无序、块间有序
  • 分块查找，又称索引顺序查找，算法过程如下：
    • 在索引表中确定待查记录所属的分块（可顺序、可折半）
    • 在块内顺序查找

用折半查找查索引：

若查找目标与索引表值相同：

image-20220701162344652

若查找目标与索引值不同：

image-20220701162417131

  • 若索引表中不包含目标关键字，则折半查找索引表最终停在 low>high，要在low所指分块中查找
  • 原因：最终low左边一定小于目标关键字，high右边一定大于目标关键字。而分块存储的索引表中保存的是各个分块的最大关键字

查找失败的例子：

image-20220701163152577

查找效率分析：

image-20220701163439336

image-20220701163509514

B树

m叉查找树：

  • 实际上就是二叉查找树的拓展，结点多少有多少个分叉就是多少叉查找树
  • 每个结点关键字的查找可以用顺序查找也可以用折半查找

image-20220701185854247

如何保证查找效率：

  • 若每个结点内关键字太少，导致树变高，要查更多层结点，效率低
    • 策略：m叉查找树中，规定除了根结点外，任何结点至少有⌈m/2⌉个分叉，即至少含有⌈m/2⌉ − 1 个关键字
    • 为什么不能保证根结点至少有⌈m/2⌉个分叉：如果整个树只有1个元素，根结点只能有两个分叉
  • 不够“平衡”，树会很高，要查很多层结点
    • 策略：m叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同。

B树的定义：

  • B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树：
    • 树中每个结点至多有m棵子树，即至多含有m-1个关键字。
    • 若根结点不是终端结点，则至少有两棵子树。
    • 除根结点外的所有非叶结点至少有⌈m/2⌉棵子树，即至少含有 ⌈m/2⌉-1个关键字。
    • 所有非叶结点的结构如下：
      • image-20220701194711998
      • 其中，Ki（i = 1, 2,…, n）为结点的关键字，且满足K1 < K2 <…< Kn；Pi（i = 0, 1,…, n）为指向子树根结点的指针，且指针Pi-1所指子树中所有结点的关键字均小于Ki，Pi所指子树中所有结点的关键字均大于Ki，n（⌈m/2⌉- 1≤n≤m - 1）为结点中关键字的个数。
    • 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

B树的高度：

image-20220701194945614

image-20220701194956469

最大高度的另一种推导方法：

image-20220701195441735

B树的插入删除

B树的插入：

  • 新元素一定是插入到最底层“终端结点”，用“查找”来确定插入位置
  • 在插入key后，若导致原结点关键字数超过上限，则从中间位置（⌈m/2⌉）将其中的关键字分为两部分
  • 左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（⌈m/2⌉）的结点插入原结点的父结点
  • 若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1。

B树的删除：

  • 若被删除关键字在终端结点，则直接删除该关键字（要注意结点关键字个数是否低于下限 ⌈m/2⌉ − 1）
  • 若被删除关键字在非终端结点，则用直接前驱或直接后继来替代被删除的关键字
    • 直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
    • 直接后继：当前关键字右侧指针所指子树中“最左下”的元素
  • 若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法）
    • 当右兄弟很宽裕时，用当前结点的后继（比当前结点大一位）、后继的后继（比当前结点大两位）来填补空缺
    • 当左兄弟很宽裕时，用当前结点的前驱（比当前结点小一位）、前驱的前驱（比当前结点小两位）来填补空缺
  • 若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=⌈m/2⌉ − 1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并

B+树

定义和性质：

image-20220701213751590

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

  • 每个分支结点最多有m棵子树（孩子结点）。
  • 非叶根结点至少有两棵子树，其他每个分支结点至少有⌈m/2⌉棵子树。
    • 可以理解为：要追求“绝对平衡”，即所有子树高度要相同
  • 结点的子树个数与关键字个数相等。
  • 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
  • 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。

B+树的查找：

B+树中，无论查找成功与否，最终一定都要走到最下面一层结点，因为只有叶子结点才有关键字对应的记录

B+树和B树区别：

image-20220701224013446

  • 典型应用：关系型数据库的“索引”（如MySQL）
  • 在B+树中，非叶结点不含有该关键字对应记录的存储地址。
  • 可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，树高更矮，读磁盘次数更少，查找更快

散列（哈希）查找

定义：

  • 散列表（Hash Table），又称哈希表
  • 是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关
  • 通过哈希函数建立关键字和存储地址的联系
  • 若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词”
  • 通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”

处理冲突的方法——拉链法：

image-20220701232012606

image-20220701232730522

image-20220701232658855

  • 用拉链法（又称链接法、链地址法）处理“冲突”：把所有“同义词”存储在一个链表中
  • 最理想情况：散列查找时间复杂度可到达O(1)
  • “冲突”越多，查找效率越低
  • 实际上就是顺序表和链表的结合结合两者优点，比如顺序表的随机存取，然后用链表的解决冲突问题，又规避了顺序表的一系列缺点
  • 在插入新元素时，保持关键字有序，可微微提高查找效率

常见的散列函数：

  • 散列函数的设计目的：
    • 让不同关键字的冲突尽可能的少
    • 散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。
  • 除留余数法：H(key) = key % p
    • 散列表表长为m，取一个不大于m但最接近或等于m的质数p
    • 质数又称素数。指除了1和此整数自身外,不能被其他自然数整除的数
    • 用质数取模，分布更均匀，冲突更少。参见《数论》
    • 注意：散列函数的设计要结合实际的关键字分布特点来考虑，不要教条化
  • 直接定址法 ： H(key) = key 或 H(key) = a*key + b
    • 其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
    • 例如：存储同一个班级的学生信息
  • 数字分析法：选取数码分布较为均匀的若干位作为散列地址
    • 设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；
    • 而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。
    • 例如：以“手机号码”作为关键字设计散列函数
  • 平方取中法：取关键字的平方值的中间几位作为散列地址。
    • 具体取多少位要视实际情况而定。
    • 这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
    • 例如：要存储整个学校的学生信息，以“身份证号”作为关键字设计散列函数

处理冲突的方法——开放定址法：

  • 所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为：
    • Hi = (H(key) + di) % m
    • i = 0, 1, 2,…, k（k≤m - 1），m表示散列表表长；di为增量序列；
    • i 可理解为“第i次发生冲突”
  • 线性探测法
    • di = 0, 1, 2, 3, …, m-1；即发生冲突时，每次往后探测相邻的下一个单元是否为空，为空则可以插入数值
    • 查找也是类似，先通过公式得到Hi再依次往后查找，若遇到空的位置则说明查找失败，所以越早遇到空位置，就可以越早确定查找失败
    • 删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个“删除标记”，进行逻辑删除
    • 线性探测法由于冲突后再探测一定是放在某个连续的位置，很容易造成同义词、非同义词的“聚集（堆积）”现象，严重影响查找效率
  • 平方探测法
    • 当di = 0^2, 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2时，称为平方探测法，又称二次探测法，其中k≤m/2
    • 比起线性探测法更不易产生“聚集（堆积）”问题
    • 注意：负数的模运算，(-3)%27 = 24，而不是3
    • 模运算的规则：a MOD m == (a+km) MOD m , 其中，k为任意整数
    • 散列表长度m必须是一个可以表示成4j + 3的素数，才能探测到所有位置
  • 伪随机序列法
    • di 是一个伪随机序列，如 di= 0, 5, 24, 11, …

处理冲突的方法——再散列法：

  • 除了原始的散列函数 H(key) 之外，多准备几个散列函数
  • 当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止：
  • Hi = RHi(Key)
  • i=1,2,3….,k

笔记完整PDF

百度网盘提取码：l3ja

赏