7.1 查找的基本概念

• 关键字 (Key)：唯一标识记录的属性，主关键字唯一，次关键字可重复。
• 平均查找长度 ASL：ASL = Σ(Pᵢ × Cᵢ)，Pᵢ 为查找第 i 个记录的概率，Cᵢ 为比较次数。
• 静态查找表：仅作查询操作，如顺序/折半/分块查找。
• 动态查找表：可插入或删除，如 BST / AVL / B 树。

7.2 静态查找表

1. 顺序查找

从第一个元素开始逐个与关键字比较，直到找到或遍历完毕。

• ASL_成功 = (n+1)/2
• ASL_失败 = n+1（含监视哨写法）
• 时间复杂度 O(n)；对表的有序性无要求。

int SeqSearch(int a[], int n, int key){
  a[0]=key;                      // 监视哨
  for(int i=n; a[i]!=key; i--);
  return i;
}

2. 折半查找（二分查找）

每次与中间元素比较，缩小一半查找范围。

• 判定树：比较次数不超过树高 ⌊log₂n⌋+1
• ASL ≈ log₂(n+1) − 1（成功时）
• 时间复杂度 O(log n)。

int BinarySearch(int a[], int n, int key){
  int low=1, high=n, mid;
  while(low<=high){
    mid = (low+high)/2;
    if(a[mid]==key) return mid;
    else if(a[mid]>key) high = mid-1;
    else low = mid+1;
  }
  return 0;
}

3. 分块查找（索引顺序查找）

将表分成若干块，块内无序但块间有序。先查索引表确定块号，再在块内顺序查找。ASL = 查索引 + 块内查找。

7.3 动态查找表

1. 二叉排序树 (BST)

• 查找：平均 O(log n)，最坏 O(n)（退化成链）。
• 插入：先查找失败位置再插入新叶。
• 删除：叶子直接删；单孩子子承父位；双孩子用中序后继（或前驱）替换。

2. 平衡二叉树 (AVL)

插入失衡时，通过旋转恢复平衡，共四种情况：

• LL（左子树左孩子插入）：右单旋转
• RR（右子树右孩子插入）：左单旋转
• LR（左子树右孩子插入）：先左后右双旋转
• RL（右子树左孩子插入）：先右后左双旋转

3. B 树与 B+ 树

• 结点关键字数 = 子女数 − 1，关键字有序排列。
• 插入：先找叶，结点满（m-1 个关键字）则分裂：中间关键字上移，左右子树分开。
• 删除：叶子不够（<⌈m/2⌉−1）则合并或借兄弟关键字。

B+ 树（常用于数据库索引）

• 所有关键字均出现在叶子结点，非叶结点仅存"最大索引"。
• 叶子结点用链表顺序连接，支持范围查询。
• n 个关键字的 B+ 树查找次数 = 树高或树高+1。

7.4 散列表（哈希表）

1. 散列函数构造

• 直接定址法：H(key)=a·key+b，适合关键字分布连续。
• 除留余数法：H(key)=key % p，p 取不大于表长的质数或不含 20 以下质因子的合数。
• 数字分析法 / 平方取中法 / 折叠法：根据关键字特征选择。

2. 冲突处理

• 开放定址法：Hᵢ = (H(key)+dᵢ) % m
  • 线性探测：dᵢ=1,2,… → 易产生"堆积"（同义词与非同义词聚集）
  • 二次探测：dᵢ=±1²,±2²,… 保证能找到一半空位
  • 双散列：dᵢ=i·H₂(key)
• 拉链法（链地址法）：同地址关键字挂在单链表中，无堆积，表长可变。
• 装载因子 α = 表中记录数 / 散列表长度，ASL 随 α 增大而增大。

7.5 B树插入与分裂动画演示

3阶B树（2-3树）：每个节点最多2个关键字、3个子节点。插入后关键字数达到3时需分裂：选中间关键字提升到父节点，左右两部分各成独立节点。演示依次插入 1 2 3 4 5 6 7。

7.6 分块查找动画演示

分块查找(索引顺序查找): 将数据分成若干块, 块间有序(索引表有序), 块内无序。先在索引表中折半查找确定块, 再在块内顺序查找。查找key=38。

7.7 B+树结构演示

B+树是B树的变体: 所有数据存储在叶子节点, 叶子节点用链表连接支持范围查询。内节点仅作索引。演示3阶B+树插入1-7的结构。