七、查找

本章导览

共 8 个小节：顺序查找、折半查找、分块查找、二叉排序树、平衡二叉树、红黑树、B树/B+树、散列查找

本章重点

• 查找看 ASL（平均查找长度）
• 线性表：顺序（无序 O(n)）、折半（有序 O(log n)）、分块
• 树形：BST/AVL/红黑树/B+树；散列：哈希直接定址 O(1)

顺序查找

关键点

• 逐个比较，不要求有序，O(n)
• 可设哨兵省越界判断；数据大且有序应改折半

折半查找

关键点

• 有序顺序表，每次砍半 O(log n)
• 前提：必须有序 + 顺序存储（链表不能随机定位 mid）
• mid 取整与 low/high 边界易错

分块查找

关键点

• 块间有序、块内无序 + 索引表；先定块再块内顺序查
• 增删只在块内；ASL 介于顺序与折半之间

二叉排序树

关键点

• BST：左 < 根 < 右；中序遍历得有序序列
• 平均 O(log n)，有序插入会退化成链 O(n)
• 删除分三种：叶 / 单子树 / 双子树（用前驱后继替换）

平衡二叉树

关键点

• AVL：平衡因子 |BF| ≤ 1，树高 O(log n)
• 失衡靠旋转修复：LL / RR / LR / RL
• 比红黑树更平衡、查找快，但旋转更频繁

红黑树

关键点

• 弱平衡 BST，染红 / 黑 + 五条性质，最长路 ≤ 2 倍最短路
• 操作 O(log n)，插删旋转少、性能稳
• 广用于 STL map / set、内核

B树/B+树

关键点

• 多路平衡查找树，为磁盘减少 I/O
• B 树结点存键 + 记录；B+ 树叶子存全部键 + 链表相连，范围查询更优
• 数据库索引多用 B+ 树

B树

关键点

B 树的插入：不断向上裂变。 B 树的删除：非终端节点删除转化为终端节点删除，终端节点能删直接删，不符合条件就去借，借不到就进行合并。

B+树

散列查找

关键点

• H(key) 直接算地址，理想 O(1)；常用除留余数法
• 冲突处理：拉链法 / 开放定址法
• 装填因子 α 越大，冲突越多

常见的散列函数

关键点

常见的散列函数有：除留余数法、直接定址法、数字分析法、平方取中法。 常见的散列函数设计目标：让不同关键字的冲突尽可能地少。 （1）除留余数法 （2）直接定址法 （3）数字分析法 （4）平方取中法

处理冲突的方法