查找的基本概念

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

查找表：用于查找的数据集合称为查找表

静态查找表：若一个查找表的操作仅涉及查找，无须动态修改，则称为静态查找表

动态查找表：需要支持插入或删除等修改操作的查找表称为动态查找表

关键字：数据元素中唯一标识该元素的某个数据项的值称为关键字

查找长度：指该次查找中关键字比较的次数

平均查找长度（ASL）：所有查找操作中关键字比较次数的加权平均值

顺序查找、折半查找和分块查找

顺序查找

顺序查找（又称线性查找）适用于顺序表和链表

一般线性表顺序查找

查找过程

1. 用户提供要查找的目标值 target
2. 从顺序表的第一个元素开始，依次比较每个元素是否等于 target如果找到：
3. • 通常返回该元素所在的位置（位序）
   • 也可能返回该元素的引用或指针
4. 如果遍历完整个表都没有找到：
   • 返回一个特殊值表示查找失败（如 -1 或 0）

平均查找长度

ASL_成功 = (n + 1)/2（这里假设每个元素的查找概率相等，即P_i = 1/n）

ASL_失败 = n + 1

有序顺序表顺序查找

查找过程

1. 初始化：从第一个元素 L[0]L[0] 开始，i=0i=0
2. 比较：
   • 如果 L[i]==targetL[i]==target：查找成功，返回位置
   • 如果 L[i]<targetL[i]<target：目标值可能在后面，继续向后查找
   • 如果 L[i]>targetL[i]>target：目标值小于当前元素，但当前及后面的元素都 ≥ 当前元素，因此查找失败，提前结束
3. 继续或结束：
   • 若 i 到达表尾仍未找到，查找失败

平均查找长度

ASL_成功 = (n + 1)/2（这里假设每个元素的查找概率相等，即P_i = 1/n）

ASL_失败 = n/2 + n/(n+1)

折半查找

折半查找也称二分查找，它仅适用于关键字有序的顺序表

查找过程

1. 首先将给定值key与表中中间位置的元素进行比较，若相等，则查找成功，返回该元素存储位置
2. 若不相等，则待查元素只能位于中间元素以外的前半部分或后半部分，随后在缩小范围内重复上述过程，直到找到目标元素，或确定表不存在该元素为止

注：在选取中间结点时，既可以采用向下取整，也可以采用向上取整，但是每次查找必须使用相同的取整方式

平均查找长度

ASL_成功 = log₂(n + 1) - 1（在等概率情况下）

ASL_失败 = log₂(n + 1)

分块查找

分块查找也称索引顺序查找，基本思想是：将查找表划分为若干子块，块内的元素可以无序，但块间必须有序，同时，建立一个索引表，其中每个元素包含对应块的最大关键字和该块的起始地址，索引表按最大关键字有序排列

查找过程

1. 在索引表中确定待查记录所在的块（可采用顺序查找或折半查找）
2. 在目标块内进行顺序查找

平均查找长度

平均查找长度等于索引查找的平均长度与块内查找的平均长度之和

当块大小 s = n^1/2，取最优值

树形查找

二叉排序树

二叉排序树定义

二叉排序树又称二叉查找树、二叉搜索树，是一种特殊的二叉树，它满足以下性质：

对于二叉排序树中的任意结点 pp：

1. 左子树条件：若 pp 的左子树非空，则左子树上所有结点的值都小于 pp 的值
2. 右子树条件：若 pp 的右子树非空，则右子树上所有结点的值都大于 pp 的值
3. 递归性质：pp 的左子树和右子树本身也分别是二叉排序树

二叉排序树的查找

1. 从根结点开始，将目标值 kk 与当前结点值 pp 比较
2. 若相等：查找成功，返回该结点
3. 若 k<pk<p：到左子树中继续查找
4. 若 k>pk>p：到右子树中继续查找
5. 若子树为空：查找失败，返回空

二叉排序树的插入

1. 若树为空：直接将新结点作为根结点
2. 若树非空：
   • 从根开始，将待插值 k 与当前结点值比较
   • 若 k < 当前结点值且左子树为空，则 kk 作为左孩子插入
   • 若 k < 当前结点值且左子树非空，则进入左子树继续比较
   • 若 k > 当前结点值且右子树为空，则 kk 作为右孩子插入
   • 若 k > 当前结点值且右子树非空，则进入右子树继续比较
3. 重复值处理：若 k 等于某结点值，可按约定不插入或插入到某侧

二叉排序树的删除

• 若被删结点是叶节点，则直接删除即可，不会影响二叉排序树的性质
• 若结点仅有一棵非空子树（左子树或右子树），则将其唯一的子树上移，作为该节点的父节点的新子树，从而代替该结点的位置
• 若结点同时具有左右两棵子树，则可用该结点的直接后继或直接前驱来代替该结点，再从树中删除该结点的直接后继（或前驱）。由于直接后继（或前驱）至多只有一个子树，这样就转化为上述的两种情况

平均查找长度

二叉排序树的查找效率主要取决于树的高度

平衡二叉树

平衡二叉树，又称 AVL树，是一种特殊的二叉排序树，它在满足二叉排序树性质的基础上，增加了平衡性要求。（左子树高度 - 右子树高度 = -1/0/1）

最小不平衡子树：在插入或删除操作中，从新插入结点向上回溯，第一个平衡因子绝对值超过 1 的结点

平衡二叉树的插入

AVL树的插入分为两步：

1. 先按普通BST的方式插入新结点
2. 从插入位置向上回溯，检查平衡性，若失衡则进行调整

调整方法

LL平衡旋转：右单旋转

RR平衡旋转：左单旋转

LR平衡旋转：先左后右双旋转

RL平衡旋转：先右后左双旋转

平衡二叉树的删除

AVL树的删除比插入更复杂，分为三步：

1. 先按普通BST的方式删除结点
2. 从删除位置向上回溯，检查平衡性
3. 对每个失衡结点进行调整，可能需多次调整

平衡二叉树的高度与性能

深度为 h 的平衡二叉树中所含的最少结点数满足以下递推公式：

N(h)=N(h−1)+N(h−2)+1

其中N(0) = 0；N(1) = 1；N(2) = 2；N(3) = 4；N(4) = 7；N(5) = 12

有 n 个结点的平衡二叉树最大深度为O(log₂n)，因此平均查找时间复杂度为O(log₂n)

红黑树

红黑树是一种自平衡的二叉排序树，它在每个结点上增加一个存储位表示结点的颜色（红色或黑色），通过对任何一条从根到叶子的路径上各结点的颜色约束，确保没有一条路径会比其他路径长出两倍，因而接近平衡。

黑高（Black Height）

• 从某个结点出发（不含该结点）到达一个叶子结点的任意一条路径上，黑色结点的个数称为该结点的黑高，记为 bh(x)
• 性质5保证了红黑树的平衡性

红黑树的性质

一棵合法的红黑树必须满足以下五个条件：

1. 结点颜色：每个结点要么是红色，要么是黑色
2. 根结点性质：根结点是黑色的
3. 叶子结点：所有叶子结点（NIL结点，即空结点）都是黑色的
4. 红色结点性质：红色结点的两个子结点都是黑色的（即不能有两个连续的红色结点）
5. 黑色高度性质：从任意结点到其每个叶子结点的所有路径都包含相同数目的黑色结点（这一数目称为该结点的黑高）

口诀：左根右，根叶黑，不红红，黑路同

红黑树的插入

红黑树的插入分为三步：

1. 按BST方式插入新结点，新结点着色为红色（这样不会破坏性质5）
2. 检查是否违反红黑树性质（性质4：不能有连续红结点）
3. 通过旋转和变色进行调整，恢复红黑树性质

违反情形

情形1：叔结点为黑（LR型，先左旋再右旋）

• 条件：z 的叔结点 y 是黑色，且 z 是其父结点的右孩子，其父结点是其祖父结点的左孩子
• 操作：
  1. 对 z 的父结点进行左旋
  2. 对 z 的祖父结点进行右旋
  3. 将 z 染黑，将原祖父结点染红

情形2：叔结点为黑（RL型，先右旋再左旋）

• 条件：z 的叔结点 y 是黑色，且 z 是其父结点的左孩子，其父结点是其祖父结点的右孩子
• 操作：
  1. 对 z 的父结点进行右旋
  2. 对 z 的祖父结点进行左旋
  3. 将 z 染黑，将原祖父结点染红

情形3：叔结点为黑（LL型，右单旋）

• 条件：z 的叔结点 y 是黑色，且 z 是其父结点的左孩子，其父结点是其祖父结点的左孩子
• 操作：
  1. 对 z 的祖父结点进行右旋
  2. 将原父结点染黑，将原祖父结点染红

情形4：叔结点为黑（RR型，左单旋）

• 条件：z 的叔结点 y 是黑色，且 z 是其父结点的右孩子，其父结点是其祖父结点的右孩子
• 操作：
  1. 对 z 的祖父结点进行左旋
  2. 将原父结点染黑，将原祖父结点染红

情形5：叔结点为红

• 条件：z 的父结点为红色，z 的叔结点 y 为红色，z 的祖父结点为黑色
• 操作：
  1. 将 z 的父结点染黑
  2. 将 z 的叔结点 y 染黑
  3. 将 z 的祖父结点染红
  4. 将 z 的祖父结点作为新的 z（即向上传递），继续检查是否违反红黑树性质

B树和B+树

B树

B树是一种平衡的多路搜索树，专门为磁盘等直接存取的外存储设备设计。它的结点可以拥有多于两个子结点，从而降低树的高度，减少磁盘I/O次数。

B树的阶

B树的阶 mm（m≥3m≥3）定义了树的结构：

• 每个结点最多有 mm 个子结点
• 每个结点最多有 m−1m−1 个关键字
• 除根结点外，每个结点至少有 ⌈m/2⌉⌈m/2⌉ 个子结点（即至少 ⌈m/2⌉−1⌈m/2⌉−1 个关键字）

B树的性质

一棵 mm 阶B树满足以下性质：

1. 根结点：
   • 要么是叶子结点
   • 要么至少有 2 个子结点（当根不是叶子时）
2. 内部结点（非根非叶）：
   • 至少有 ⌈m/2⌉⌈m/2⌉ 个子结点
   • 至少有 ⌈m/2⌉−1⌈m/2⌉−1 个关键字
   • 至多有 mm 个子结点
   • 至多有 m−1m−1 个关键字
3. 叶子结点：
   • 所有叶子结点在同一层
   • 关键字数量范围：⌈m/2⌉−1≤k≤m−1⌈m/2⌉−1≤k≤m−1
4. 关键字排序：
   • 结点内的关键字有序排列（升序）
   • 子结点指针介于关键字之间

B树的高度

最小高度情形：h >= log_m(n + 1)

最大高度情形：h <= log_⌈m/2⌉((n + 1)/2) + 1

B树的查找

1. 从根结点开始，当前结点指针 p 指向根
2. 在当前结点中顺序查找目标值 k：
   • 若找到等于 k 的关键字：查找成功
   • 若找到第一个大于 k 的关键字 Ki：进入 Pi−1 指向的子树
   • 若所有关键字都小于 k：进入 Pn 指向的子树（最后一个指针）
3. 若 p 为空（到达叶子且未找到）：查找失败

B树的插入

第一步：查找插入位置

• 按查找方式找到目标关键字应插入的叶子结点

第二步：插入关键字

• 将关键字按序插入叶子结点

第三步：检查并处理溢出

• 若插入后结点关键字个数 ≤ m−1m−1：插入完成
• 若插入后结点关键字个数 = mm（溢出）：进行分裂

第四步：结点分裂

1. 将溢出结点从中间位置 ⌈m/2⌉⌈m/2⌉ 拆分为两部分：
   • 左结点：前 ⌈m/2⌉−1⌈m/2⌉−1 个关键字
   • 右结点：后 m−⌈m/2⌉m−⌈m/2⌉ 个关键字
2. 中间位置的关键字（第 ⌈m/2⌉⌈m/2⌉ 个）上升到父结点
3. 父结点增加一个关键字和两个子结点指针
4. 若父结点也溢出，继续向上分裂，直到根结点

注：若根结点溢出，分裂后产生新的根结点，树高增加1

B树的删除

第一步：查找被删关键字

• 找到关键字 kk 所在的结点

第二步：分情况处理

情况1：kk 在叶子结点中

1. 直接删除 kk
2. 若删除后结点关键字个数 ≥ ⌈m/2⌉−1⌈m/2⌉−1：删除完成
3. 若删除后结点关键字个数 < ⌈m/2⌉−1⌈m/2⌉−1（下溢）：进行借或合并

情况2：kk 在内部结点中

1. 找到 kk 的前驱或后继关键字（一定在叶子结点）
2. 用前驱或后继的值替换 kk
3. 删除叶子结点中的前驱或后继（转化为情况1）

第三步：处理下溢

当结点关键字个数不足 ⌈m/2⌉−1⌈m/2⌉−1 时：

方法1：向右兄弟借（左旋）

• 若右兄弟关键字个数 > ⌈m/2⌉−1⌈m/2⌉−1：
  • 父结点中相应关键字下移到当前结点
  • 右兄弟中最小的关键字上移到父结点

方法2：向左兄弟借（右旋）

• 若左兄弟关键字个数 > ⌈m/2⌉−1⌈m/2⌉−1：
  • 父结点中相应关键字下移到当前结点
  • 左兄弟中最大的关键字上移到父结点

方法3：与兄弟合并

• 若兄弟结点也处于最小关键字状态：
  • 将当前结点、父结点中相应关键字、兄弟结点合并为一个结点
  • 父结点关键字数减1
  • 若父结点也下溢，继续向上处理，直到根

B+树

一棵 mm 阶B+树满足：

1. 内部结点（索引结点）：
   • 最多 mm 个子结点
   • 最少 ⌈m/2⌉⌈m/2⌉ 个子结点（根除外）
   • 有 kk 个子结点则有 kk 个关键字（B树是 k−1k−1 个）
   • 关键字是子结点中最大值（或最小值）的副本
2. 叶子结点（数据结点）：
   • 所有叶子在同一层
   • 包含所有关键字及指向数据记录的指针
   • 关键字数量范围：⌈m/2⌉≤k≤m⌈m/2⌉≤k≤m
   • 叶子结点之间通过指针链接成有序链表
3. 根结点：
   • 可以是叶子（空树或单结点）
   • 或至少有 2 个子结点

散列表

散列表的概念

散列表（Hash Table），又称哈希表，是一种根据关键字直接进行访问的数据结构。它通过一个散列函数将关键字映射到表中的某个位置，以实现快速插入、删除和查找操作

散列函数构造方法

除留余数法

公式为：H(key)=key mod p

设散列表长度为m，选取一个不超过m且尽可能接近m的质数p

直接定址法

公式为：H(key)=a * key + b

适用于关键字分布基本连续的情形（例：学号）

数字分析法

分析关键字各位数字的分布，取分布均匀的若干位作为散列地址

平方取中法

取关键字平方后的中间几位作为散列地址

公式为：H(key) = 取 key² 的中间若干位

处理冲突的方法

开放定址法

当冲突发生时，按照某种探测方法在散列表中寻找下一个空闲位置。所有记录都存储在表内，不额外分配空间。

通用公式：H_i = (H(key)+d_i) mod m

线性探测法

增量序列：d_i=1,2,3,...,m−1

缺点：容易产生聚集现象（连续冲突的区块），导致查找效率下降

平方探测法

增量序列：d_i=1²,−1²,2²,−2²,...

优点：缓解聚集现象

缺点：不一定能探测到所有位置，要求 mm 是形如 4k+34k+3 的素数

双散列法

增量序列：d_i=i×H₂(key)

公式：H_i=(H₁(key)+i×H₂(key))  mod  m

特点：使用两个散列函数，第一个计算初始地址，第二个计算探测步长

优点：分布更均匀，聚集最少

伪随机法

增量序列：伪随机数序列

实现：预先确定一个伪随机数生成器，按顺序取随机数作为增量

特点：理论上分布均匀，实际取决于随机数质量

拉链法

将所有同义词存储在一个线性链表中，散列表的每个位置存放对应链表的头指针。

操作过程

• 插入：计算地址，将新结点插入对应链表（可头插或尾插）
• 查找：计算地址，在对应链表中顺序查找
• 删除：在链表中删除指定结点

散列查找及性能分析的应用

散列表的查找效率主要取决于三个因素：散列函数、冲突处理方法、装填因子

散列表平均查找长度

散列表的性能用平均查找长度衡量，分为：

ASL成功

• 查找表中已有记录的平均比较次数
• 计算时只考虑成功查找的情况

ASL失败

• 查找不在表中的记录的平均比较次数
• 计算时需要考虑所有可能失败的位置

装填因子

α = 表中记录数n / 散列表长度m

散列表的平均查找长度主要依赖于装填因子，而不直接依赖于 n 或 m