第七章查找

第七章查找

7.1 查找的基本概念

查找 —— 在数据集合中寻找满⾜某种条件的数据元素的过程称为查找

查找表（查找结构）—— ⽤于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成

关键字 —— 数据元素中唯⼀标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的

对查找表的常⻅操作

①查找符合条件的数据元素 ②插⼊、删除某个数据元素

只需进⾏操作① —— 静态查找表仅关注查找速度

也要进⾏操作② —— 动态查找表除了查找速度，也要关注插 / 删操作是否⽅便实现

适合静态查找表: 顺序查找, 折半查找, 散列查找

适合动态查找表: 二叉排序树, 散列查找, 二叉平衡树和 B 树都是二叉排序树的改进

查找算法的评价指标

查找⻓度——在查找运算中，需要对⽐关键字的次数称为查找⻓度

平均查找⻓度（ASL, Average Search Length）—— 所有查找过程中进⾏关键字的⽐较次数的平均值

7.2 顺序查找和折半查找

7.2.1 顺序查找

顺序查找，⼜叫 “线性查找”，通常⽤于线性表

ASL 成功 =(n+1)/2 ASL 失败 = n+1

7.2.2 折半查找（二分查找）

折半查找，⼜称 “⼆分查找”，仅适⽤于有序的顺序表。

折半查找判定树的构造

如果当前 low 和 high 之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等

如果当前 low 和 high 之间有偶数个元素，则 mid 分隔后，左半部分⽐右半部分少⼀个元素

折半查找的判定树中，若 mid = ⌊(low + high)/2]，则对于任何⼀个结点，必有： 右⼦树结点数 - 左⼦树结点数 = 0 或 1

折半查找的判定树⼀定是平衡⼆叉树

折半查找的判定树中，只有最下⾯⼀层是不满的因此，元素个数为 n 时树⾼ h = ⌈log 2 (n + 1)⌉

折半查找的时间复杂度 = O (log 2 n)

7.2.3 分块查找

分块查找，⼜称索引顺序查找，算法过程如下： ①在索引表中确定待查记录所属的分块（可顺序、可折半） ②在块内顺序查找

特点：块内⽆序、块间有序

算法思想：

1. 分为若干子块, 块内可以无序, 块之间有序
2. 第一块中最大关键字 < 第二块中所有记录, 以此类推
3. 建立一个索引表, 含有各块最大关键字和各块第一个元素的地址, 按关键字有序排列

若索引表中不包含⽬标关键字，则折半查找索引表最终停在 low>high，要在 low 所指分块中查找

Low 超出索引表范围，查找失败

设索引查找和块内查找的平均查找⻓度分别为 LI、LS，则分块查找的平均查找⻓度为 ASL=LI + LS

7.3 树型查找

7.3.1 二叉排序树 BST

二叉排序树，又称二叉查找树（BST，Binary Search Tree）

二叉排序树可用于元素的有序组织、搜索

具有如下性质：左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字。左子树和右子树又各是一棵二叉排序树。

左子树结点值 < 根结点值 < 右子树结点值

进行中序遍历，可以得到一个递增的有序序列

二叉排序树的删除：① 若被删除结点 z 是叶结点，则直接删除，不会破坏二叉排序树的性质。

② 若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替代 z 的位置

③ 若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）替代 z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况

查找效率分析：

1. 平均查找长度 ASL=(每层个数 * 对应层数)/ 总个数
2. 最坏情况: 类似有序单链表 O (n)
3. 最好情况: 平衡二叉树 O (㏒₂n)
4. 查找过程: 与二分查找类似, 但二分查找的判定树唯一

7.3.2 平衡二叉树 AVL

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL 树）——树上任一结点的左子树和右子树的高度之差不超过 1

结点的平衡因子 = 左子树高 - 右子树高

平衡二叉树的插入：从插入点往回找到第一个不平衡结点，调整以该结点为根的子树，每次调整的对象都是 “最小不平衡子树”

1. LL 平衡旋转（右单旋转）。由于在结点 A 的左孩子（L）的左子树（L）上插入了新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。将 A 的左孩子 B 向右上旋转代替 A 成为根结点，将 A 结点向右下旋转成为 B 的右子树的根结点，而 B 的原右子树则作为 A 结点的左子树

   

2. RR 平衡旋转（左单旋转）。由于在结点 A 的右孩子（R）的右子树（R）上插入了新结点，A 的平衡因子由 - 1 减至 - 2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。将 A 的右孩子 B 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，而 B 的原左子树则作为 A 结点的右子树

   

3. LR 平衡旋转（先左后右双旋转）。由于在 A 的左孩子（L）的右子树（R）上插入新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后再把该 C 结点向右上旋转提升到 A 结点的位置

   

4. RL 平衡旋转（先右后左双旋转）。由于在 A 的右孩子（R）的左子树（L）上插入新结点，A 的平衡因子由 - 1 减至 - 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后再把该 C 结点向左上旋转提升到 A 结点的位置

   

含有 n 个结点的平衡二叉树的最大深度为 O (log 2 n) ，平衡二叉树的平均查找长度为 O (log 2 n)

7.3.3 红黑树

平衡二叉树 AVL：插入 / 删除很容易破坏 “平衡” 特性，需要频繁调整树的形态。如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大），再进行 LL/RR/LR/RL 调整

红黑树 RBT：插入 / 删除很多时候不会破坏 “红黑” 特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成

平衡二叉树：适用于以查为主、很少插入 / 删除的场景

红黑树：适用于频繁插入、删除的场景，实用性更强

红黑树是二叉排序树左子树结点值 ≤ 根结点值 ≤ 右子树结点值

定义

①每个结点或是红色，或是黑色的

②根节点是黑色的

③叶结点（外部结点、NULL 结点、失败结点）均是黑色的

④不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色）

⑤对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同 (每个结点的左右子树中黑结点的层数是相等)

结点的黑高 bh —— 从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数

性质： 从根节点到叶结点的最长路径不大于最短路径的 2 倍，有 n 个内部节点的红黑树高度 h ≤ 2 log 2 (n+1)

红黑树查找操作时间复杂度 = O (log 2 n)

红黑树的插入

插入过程

7.4 B 树和 B + 树

7.4.1 B 树

B 树，⼜称多路平衡查找树，B 树中所有结点的孩⼦个数的最⼤值称为 B 树的阶，通常⽤ m 表示。⼀棵 m 阶 B 树或为空树，或为满⾜如下特性的 m 叉树：

1）树中每个结点⾄多有 m 棵⼦树，即⾄多含有 m-1 个关键字。

2）若根结点不是终端结点，则⾄少有两棵⼦树。

3）除根结点外的所有⾮叶结点⾄少有 m/2 棵⼦树，即⾄少含有 m/2-1 个关键字。

4）所有的叶结点都出现在同⼀层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）

5）所有非叶结点结构：关键字递增排列，左子树所有数 <对应关键字, 右子树所有数> 对应关键字

m 阶 B 树的核⼼特性：

1） 根节点的⼦树数∈[2, m]，关键字数∈[1, m-1]。其他结点的⼦树数∈[ , m]；关键字数∈[ -1, m-1]

2）对任⼀结点，其所有⼦树⾼度都相同

3）关键字的值：⼦树 0 < 关键字 1 < ⼦树 1 < 关键字 2 < ⼦树 2<…. (类⽐⼆叉查找树左 <中 < 右)

B 树的高度 算 B 树的⾼度不包括叶⼦结点（失败结点）

B 树的插入

1. 一定插入在最低层的某个非叶结点内

2. 在插⼊ key 后，若导致原结点关键字数超过上限，则从中间位置（ m/2）将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（ m/2）的结点插⼊原结点的⽗结点

3. 若此时导致其⽗结点的关键字个数也超过了上限，则继续进⾏这种分裂操作，直⾄这个过程传到根结点为⽌，进 ⽽导致 B 树⾼度增 1

   

B 树的删除

结点关键字个数 ⌈m/2⌉ − 1 ≤n≤m-1

1. 若被删除关键字在终端节点，则直接删除该关键字（要注意节点关键字个数是否低于下限 ⌈m/2⌉ − 1）

2. 若被删除关键字在⾮终端节点，则⽤直接前驱或直接后继来替代被删除的关键字

   直接前驱：当前关键字左侧指针所指⼦树中 “最右下” 的元素

   直接后继：当前关键字右侧指针所指⼦树中 “最左下” 的元素

3. 兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该结点、右（或左）兄弟结点及其双亲结点（⽗⼦换位法

   父子换位法: 兄弟结点中的一个关键字进入父结点, 父结点中的一个关键字进入被删结点, 然后删除关键字

   本质：要永远保证 ⼦树 0 < 关键字 1 < ⼦树 1 < 关键字 2 < ⼦树 2

4. 兄弟不够借。若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均 =⌈m/2⌉ − 1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进⾏合并

   在合并过程中，双亲结点中的关键字个数会减 1。若其双亲结点是根结点且关键字个数减少⾄ 0（根结点关键字个数为 1 时，有 2 棵⼦树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到，则⼜要与它⾃⼰的兄弟结点进⾏调整或合并操作，并重复上述步骤，直⾄符合 B 树的要求为⽌

7.4.2 B + 树

⼀棵 m 阶的 B + 树需满⾜下列条件：

1）每个分⽀结点最多有 m 棵⼦树（孩⼦结点）。

2）⾮叶根结点⾄少有两棵⼦树，其他每个分⽀结点⾄少有棵⼦树。

3）结点的⼦树个数与关键字个数相等。(与 B 树的最大区别)

4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按⼤⼩顺序排列，并且相邻叶结点按⼤⼩顺序相互链接起来。

5）所有分⽀结点中仅包含它的各个⼦结点中关键字的最⼤值及指向其⼦结点的指针。

B + 树的查找：从最小关键字顺序查找 / 从根结点多路查找

B + 树中，⽆论查找成功与否，最终⼀定都要⾛到最下⾯⼀层结点

7.5 散列表

7.5.1 散列表的基本概念

散列表（Hash Table），⼜称哈希表。是⼀种数据结构，

**特点：**数据元素的关键字与其存储地址直接相关

若不同的关键字通过散列函数映射到同⼀个值，则称它们为 “同义词”

通过散列函数确定的位置已经存放了其他元素，则称这种情况为 “冲突”

处理冲突的⽅法——拉链法（⼜称链接法、链地址法）：把所有 “同义词” 存储在⼀个链表中

7.5.2 散列函数的构造方法

1. 除留余数法 —— H (key) = key % p

   P 的选取: 不大于 m (散列表长) 但最接近或等于 m 的质数

2. 直接定址法 —— H (key) = key 或 H (key) = a*key + b

   其中，a 和 b 是常数。这种⽅法计算最简单，且不会产⽣冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费

3. 数字分析法 —— 选取数码分布较为均匀的若⼲位作为散列地址

   设关键字是 r 进制数（如⼗进制数），⽽ r 个数码在各位上出现的频率不⼀定相同，可能在某些位上分布均匀⼀些，每种数码出现的机会均等；⽽在某些位上分布不均匀，只有某⼏种数码经常出现，此时可选取数码分布较为均匀的若⼲位作为散列地址。这种⽅法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数

4. 平⽅取中法——取关键字的平⽅值的中间⼏位作为散列地址

   具体取多少位要视实际情况⽽定。这种⽅法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布⽐较均匀，适⽤于关键字的每位取值都不够均匀或均⼩于散列地址所需的位数

5. 折叠法——关键字分割成位数相同的几部分, 取叠加和作为散列地

   适用于位数很多且每位上数字分布大致均匀

7.5.3 处理冲突的方法

1. ⽤拉链法（⼜称链接法、链地址法）处理 “冲突”：把所有 “同义词” 存储在⼀个链表中

2. 开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，⼜向它的⾮同义词表项开放。

   其数学递推公式为：Hi = (H (key) + di) % m

   I = 0, 1, 2,…, k（k≤m - 1），m 表示散列表表⻓；di 为增量序列；i 可理解为 “第 i 次发⽣冲突 “

   ①线性探测法—— di = 0, 1, 2, 3, …, m-1；即发⽣冲突时，每次往后探测相邻的下⼀个单元是否为空

   线性探测法很容易造成同义词、⾮同义词的 “聚集（堆积）” 现象，严重影响查找效率

   产⽣原因——冲突后再探测⼀定是放在某个连续的位置

   ②平⽅探测法。当 di = 02, 12, -12, 22, -22, …, k 2, -k 2 时，称为平⽅探测法，⼜称⼆次探测法其中 k≤m/2

   优点: 可以避免出现堆积问题，缺点: 只能探测一半单元

   ③伪随机序列法。Di 是⼀个伪随机序列，如 di= 0, 5, 24, 11, …

   

注意：

1. 不能随便物理删除已有元素, 会截断其他相同散列地址元素的查找地址
2. 可做删除标记, 逻辑删除
3. 副作用: 多次删除后, 表面上散列表很满, 其实还有很多位置未用, 需定期维护

7.5.4 散列查找及性能分析

查找效率：

1. 取决于: 散列函数, 处理冲突的方法, 装填因子
2. 装填因子 (α): 定义一个表的装满程度 α= 表中记录数 n / 散列表长度 m
3. 平均查找长度依赖于α, 不直接依赖于 n 或 m

易错点：

1. K 个同义词采用线性探测填入散列表, 需要探测 K (K+1)/2 次
2. 冲突产生的概率与装填因子的大小成正比越满越容易冲突
3. 不能用随机数函数构造散列函数, 无法进行正常的查找

注意点:

1. ASL 成功查找次数 = 冲突次数 + 1
2. 根据散列函数确定一共需要的查找的位置, 对每个位置查找直到为空时结束, 不为空时用相应的冲突处理方法再进行查找, 为空时也需要比较一次