顺序、折半查找与树型查找

本节导读

大纲的查找一章列了基本概念、顺序查找、分块查找、折半查找、树型查找（二叉搜索树、平衡二叉树、红黑树）、B 树和 B+ 树、散列表、字符串模式匹配、查找算法的分析及应用。本节讲前五项，下一节讲其余几项。

这一节的计算集中在平均查找长度（ASL）和比较次数；树型查找则要会画出插入、删除、旋转之后的树。学完你应该能写出折半查找的代码与比较过程，能构造二叉搜索树和平衡二叉树，并说出红黑树的五条性质。

查找的基本概念与顺序查找

查找表是同一类型数据元素的集合；只做查找的叫静态查找表，查找时还要插入、删除的叫动态查找表。衡量查找算法的主要指标是平均查找长度：

$$\mathrm{ASL} = \sum_{i=1}^{n} P_i C_i$$ASL=i=1∑n​Pi​Ci​

其中 $P_i$Pi​ 是查找第 i 个元素的概率，$C_i$Ci​ 是找到它需要的比较次数；查找失败时另算失败的 ASL。

顺序查找从一端开始逐个比较，对顺序表和链表都适用。在表的一端设「哨兵」可以省掉每次的越界判断。等概率下查找成功的 $\mathrm{ASL} = \dfrac{n+1}{2}$ASL=2n+1​；带哨兵时查找失败要比较 n + 1 次。表若按关键字有序，比到第一个大于待查值的元素就能判定失败，失败的平均比较次数可以减少。

折半查找

折半查找只适用于有序的顺序表（要能随机存取）：

int bin_search(int A[], int n, int key) {   /* A[0..n-1] 递增有序 */
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;          /* 取下整 */
        if (A[mid] == key) return mid;
        else if (A[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;                               /* 查找失败 */
}

查找过程可以画成一棵判定树：每个结点是一次比较，左子树是比它小的那一半。判定树是平衡二叉树，所以：

• 查找成功时比较次数不超过判定树的高度 $\lceil \log_2(n+1) \rceil$⌈log2​(n+1)⌉；
• 查找失败时比较次数等于判定树的高度或比它少 1；
• 等概率下成功的 ASL 约为 $\log_2(n+1) - 1$log2​(n+1)−1，时间复杂度 $O(\log_2 n)$O(log2​n)。

mid 取下整还是上整，判定树的形状不同，比较序列也不同，做题时看清题目的约定。

分块查找

分块查找（索引顺序查找）把表分成若干块：块内可以无序，块间有序（前一块的最大关键字小于后一块的所有关键字），另建索引表记下每块的最大关键字和起始位置。先在索引表里确定在哪一块，再在块内顺序查找，$\mathrm{ASL} = L_I + L_S$ASL=LI​+LS​。

长度为 n 的表均匀分成 b 块、每块 s 个元素，索引表和块内都用顺序查找时：

$$\mathrm{ASL} = \frac{b+1}{2} + \frac{s+1}{2}$$ASL=2b+1​+2s+1​

$s = \sqrt{n}$s=n​ 时 ASL 最小，为 $\sqrt{n} + 1$n​+1。例如 n = 400 时每块 20 个元素最合适，ASL 为 21。

二叉搜索树

二叉搜索树（二叉排序树）要么为空，要么左子树上所有关键字都小于根，右子树上所有关键字都大于根，左右子树也都是二叉搜索树。所以中序遍历得到递增序列。

• 查找：从根开始比较，小了往左、大了往右，比较次数不超过树高。
• 插入：查找失败的位置就是插入位置，新结点一定是叶结点。
• 删除：被删结点是叶结点，直接删；只有一棵子树，让子树替代它；有两棵子树，用它的中序直接后继（右子树中最小的结点）或直接前驱（左子树中最大的结点）替代它，再删去那个后继（前驱）。

同一组关键字插入次序不同，树的形态就不同：接近平衡时 ASL 是 $O(\log_2 n)$O(log2​n)，退化成单支树时是 $O(n)$O(n)。

平衡二叉树

平衡二叉树（AVL 树）中任一结点的左右子树高度差（平衡因子 = 左子树高 − 右子树高）的绝对值不超过 1。插入一个结点后，从插入点往上找到第一个平衡因子绝对值为 2 的结点 A，只调整以 A 为根的最小不平衡子树：

类型	新结点插在哪里	调整
LL	A 的左孩子的左子树	以左孩子为轴右旋一次
RR	A 的右孩子的右子树	以右孩子为轴左旋一次
LR	A 的左孩子的右子树	先左旋再右旋，左孩子的右孩子成为新根
RL	A 的右孩子的左子树	先右旋再左旋，右孩子的左孩子成为新根

设高度为 h（根在第 1 层）的平衡二叉树最少有 $N_h$Nh​ 个结点，则 $N_1 = 1$N1​=1，$N_2 = 2$N2​=2，$N_h = N_{h-1} + N_{h-2} + 1$Nh​=Nh−1​+Nh−2​+1。所以 n 个结点的平衡二叉树高度是 $O(\log_2 n)$O(log2​n)，查找、插入、删除都是 $O(\log_2 n)$O(log2​n)。

红黑树

红黑树是满足下面五条性质的二叉搜索树（把空指针看成黑色的叶结点 NIL）：

1. 每个结点是红色或黑色；
2. 根是黑色；
3. 叶结点（NIL）是黑色；
4. 红结点的两个孩子都是黑色，即不存在两个相邻的红结点；
5. 从任一结点到它的每个叶结点的路径上，黑结点个数相同（叫这个结点的黑高）。

由性质 4、5 可知：从根到叶结点的最长路径不超过最短路径的 2 倍，n 个内部结点的红黑树高度不超过 $2\log_2(n+1)$2log2​(n+1)。红黑树只是近似平衡，但插入、删除时调整的代价小（插入至多旋转 2 次，删除至多 3 次），适合插入删除频繁的场合。插入的新结点一律着红色（不破坏性质 5），若与父结点同为红色，再按叔结点的颜色变色或旋转。

易错提醒

• ❌ 折半查找也可以用于有序的单链表。✅ 只能用于有序的顺序表。因为要按下标直接取到中间元素，链表做不到随机存取。

• ❌ 在二叉搜索树中删除有两棵子树的结点，直接用它的右孩子顶替。✅ 用中序直接后继（右子树最左下的结点）或直接前驱顶替。因为右孩子不一定是右子树中最小的结点。

• ❌ 平衡二叉树插入后失衡，就调整离根最近的那个失衡结点。✅ 调整的是离插入点最近的失衡结点为根的最小不平衡子树。因为它调整好了，上面的结点自然恢复平衡。

• ❌ 红黑树是平衡二叉树（AVL 树）的一种。✅ 红黑树不要求左右子树高度差不超过 1，只保证最长路径不超过最短路径的 2 倍。因为它的平衡条件靠颜色规则，比 AVL 宽松。

• ❌ 二叉搜索树的查找效率总是 $O(\log_2 n)$O(log2​n)。✅ 取决于树的形态，退化成单支树时是 $O(n)$O(n)。因为比较次数不超过树高，而树高随插入次序变化。

例题精讲

例题 1（折半查找）

有序表 5、9、12、18、23、31、37、42、50、56、63、71、88（共 13 个，位序 1 至 13，mid 取下整）。查找 50 依次与哪些元素比较？等概率下查找成功的 ASL 是多少？

答题要点示范：low = 1、high = 13，mid = 7，37 小于 50，low = 8；mid = 10，56 大于 50，high = 9；mid = 8，42 小于 50，low = 9；mid = 9，找到。依次比较 37、56、42、50，共 4 次。判定树第 1 至 4 层分别有 1、2、4、6 个结点，$\mathrm{ASL} = \dfrac{1 \times 1 + 2 \times 2 + 3 \times 4 + 4 \times 6}{13} = \dfrac{41}{13}$ASL=131×1+2×2+3×4+4×6​=1341​。

例题 2（二叉搜索树）

依次插入 45、24、53、12、37、93、28、40 构造二叉搜索树，再删除 24（用中序后继顶替），写出删除后的先序序列。

答题要点示范：构造后 45 的左孩子 24、右孩子 53；24 的左孩子 12、右孩子 37；37 的左孩子 28、右孩子 40；53 的右孩子 93。24 有两棵子树，中序后继是右子树最左下的 28，用 28 顶替 24，再删去原来的 28（叶结点）。先序序列：45、28、12、37、40、53、93。

例题 3（平衡二叉树）

依次插入 20、10、30、25、27 构造平衡二叉树，写出最后的形态。

答题要点示范：插入 20、10、30、25 后仍平衡（25 是 30 的左孩子）。插入 27 后它是 25 的右孩子，30 的平衡因子变为 2，是最小不平衡子树的根；27 插在 30 的左孩子的右子树上，属 LR 型：先以 25 为轴左旋、再以 27 为轴右旋，27 成为这棵子树的根，左孩子 25、右孩子 30。最后：根 20，左孩子 10，右孩子 27，27 的孩子是 25 和 30。

点评：先找最小不平衡子树（这里是 30 而不是根 20），再看新结点在它的哪个孩子的哪棵子树上，类型就定了。

本节小结

• ASL 是各元素比较次数的加权平均；顺序查找成功 $\dfrac{n+1}{2}$2n+1​，适用于顺序表和链表。
• 折半查找只用于有序顺序表，判定树是平衡二叉树，成功最多比较 $\lceil \log_2(n+1) \rceil$⌈log2​(n+1)⌉ 次。
• 分块查找块内无序、块间有序；都顺序查找时 $\mathrm{ASL} = \dfrac{b+1}{2} + \dfrac{s+1}{2}$ASL=2b+1​+2s+1​，每块 $\sqrt{n}$n​ 个最好。
• 二叉搜索树中序递增；删除有两棵子树的结点用中序前驱或后继顶替。
• 平衡二叉树按 LL、RR、LR、RL 调整最小不平衡子树；红黑树靠五条颜色性质近似平衡，最长路径不超过最短路径的 2 倍。