第7章 查找

第7章 查找

本书前几章介绍了各种线性和非线性的数据结构，并讨论了这些数据结构的相应运算。而在实际应用中，查找运算是非常常见的。面向一些数据量很大的实时系统，如订票系统、互联网上的信息检索系统等，查找效率尤其重要。本章将针对查找运算，讨论应该采用何种数据结构，使用什么样的方法，并通过对它们的效率进行分析来比较各种查找算法在不同情况下的优劣。

7.1 查找的基本概念

（1） 查找表

为了便于后面各节对各种查找算法的比较，首先介绍查找的概念和术语。

查找表是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构，可以利用其他的数据结构来实现，比如本章将要介绍的线性表、树表及散列表等。

（2） 关键字

关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（对不同的记录，其主关键字均不同）。反之，称用以识别若干记录的关键字为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值。

（3） 查找

查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找成功，此时查找的结果可给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。

（4） 动态查找表和静态查找表

若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表，否则称之为静态查找表。换句话说，动态查找表的表结构本身是在查找过程中动态生成的，即在创建表时，对于给定值，若表中存在其关键字等于给定值的记录，则查找成功返回；否则插入关键字等于给定值的记录。

（5） 平均查找长度

为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法

在查找成功时的平均查找长度（Average Search Length，ASL）。

对于含有 n 个记录的表，查找成功时的平均查找长度为

$$ ASL=\sum_{i=1}^{n}P_{i}C_{i} $$

其中， $ P_{i} $为查找表中第i个记录的概率，且 $ \sum_{i=1}^{n}P_{i}=1 $；

$ C_{i} $ 为找到表中其关键字与给定值相等的第 i 个记录时，和给定值已进行过比较的关键字个数。显然， $ C_{i} $ 随查找过程不同而不同。

由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。

7.2 线性表的查找

在查找表的组织方式中，线性表是最简单的一种。本节将介绍基于线性表的顺序查找、折半查找和分块查找。

7.2.1 顺序查找

顺序查找（Sequential Search）的查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。

顺序查找方法既适用于线性表的顺序存储结构，又适用于线性表的链式存储结构。下面只介绍以顺序表作为存储结构时实现的顺序查找算法。

数据元素类型定义如下：

typedef struct{

    KeyType key;
    InfoType otherinfo;
}ElemType;

顺序表的定义同第2章：

typedef struct{

    ElemType *R;
    int length;
}SSTable;

// 关键字域
// 其他域

// 存储空间基地址
// 当前长度

算法7.1 顺序查找

【算法描述】

int Search_Seq(SSTable ST, KeyType key)
{
    // 在顺序表 ST 中顺序查找其关键字等于 key 的数据元素。若找到，则函数值为该元素在表中的位置，否则为 0 for (i=ST.length; i>=1;--i)
        if (ST.R[i].key==key) return i;
}
// 从后往前找

return 0;

算法 7.1 在查找过程中每步都要检测整个表是否查找完毕，即每步都要有循环变量是否满足条件 $ i \geq 1 $ 的检测。改进这个程序，可以免去这个检测过程。改进方法是查找之前先对 ST.R[0] 的关键字赋值 key，在此，ST.R[0] 起到了监视哨的作用，如算法 7.2 所示。

算法 7.2 设置监视哨的顺序查找

【算法描述】

int Search_Seq(SSTable ST, KeyType key)
{
    //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
    ST.R[0].key=key;
    //“哨兵”
    for (i=ST.length;ST.R[i].key!=key;--i);
    //从后往前找
    return i;
}

【算法分析】

【算法分析】

因此，算法 7.2 仅是一个程序设计技巧上的改进，即通过设置监视哨，免去查找过程中每一步都要检测整个表是否查找完毕。然而实践证明，这个改进能使顺序查找在 ST.length ≥ 1000 时，进行一次查找所需的平均时间几乎减少一半。当然，监视哨也可设在高下标处。

算法 7.2 和算法 7.1 的时间复杂度一样，在第 2 章已经做过分析，即

$$ ASL=\frac{1}{n}\sum_{i=1}^{n}i=\frac{n+1}{2} $$

算法 7.2 的时间复杂度为 O(n)。

顺序查找的优点是：算法简单，对表结构无任何要求，既适用于顺序结构，也适用于链式结构，无论记录是否按关键字有序均可应用。其缺点是：平均查找长度较大，查找效率较低，所以当n很大时，不宜采用顺序查找。

7.2.2 折半查找

折半查找（Binary Search）也称二分查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。在下面及后续的讨论中，均假设有序表是递增有序的。

折半查找的查找过程为：从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。

折半查找每一次查找比较都使查找范围缩小一半，与顺序查找相比，很显然会提高查找效率。

为了标记查找过程中每一次的查找区间，下面分别用 low 和 high 来表示当前查找区间的下界和上界，mid 为区间的中间位置。

算法7.3 折半查找

【算法步骤】

① 置查找区间初值，low 为 1，high 为表长。

② 当 low 小于等于 high 时，循环执行以下操作：

mid取值为 low 和 high 的中间值；

将给定值 key 与中间位置记录的关键字进行比较，若相等则查找成功，返回中间位置 mid；

若不相等则利用中间位置记录将表对分成前、后两个子表。如果 key 比中间位置记录的关键字小，则 high 取为 mid-1，否则 low 取为 mid+1。

③ 循环结束，说明查找区间为空，则查找失败，返回0。

【算法描述】

int Search_Bin(SSTable ST, KeyType key,
{
    // 在有序表 ST 中折半查找其关键字等于 key 的数据元素。若找到，则函数值为该元素在表中的位置，否则为 0
    low=1;high=ST.length;
    while (low<=high)
    {
        mid=(low+high)/2;
        if (key==ST.R[mid].key) return mid;
        else if (key<ST.R[mid].key) high=mid-1;
        else low=mid+1;
    }
    return 0;
}

本算法很容易理解，唯一需要注意的是，循环执行的条件是 low<=high，而不是 low<high，因为 low=high 时；查找区间还有最后一个结点，还要进一步比较。

算法 7.3 很容易改写成递归程序，递归函数的参数除了 ST 和 key 之外，还需要加上 low 和 high，请读者自行实现折半查找的递归算法。

【例7.1】已知如下11个数据元素的有序表（关键字即为数据元素的值）：

请给出查找关键字为27和65的数据元素的折半查找过程。

假设指针 low 和 high 分别指示待查元素所在范围的下界和上界，指针 mid 指示区间的中间位置，即 $ \text{mid} = \lfloor (\text{low} + \text{high}) / 2 \rfloor $。在此例中，low 和 high 的初值分别为 1 和 11，即 [1,11] 为待查范围，mid 初值为 6。

查找关键字 key = 27 的折半查找过程如图 7.1（a）所示。

首先令给定值 key=27 与中间位置的数据元素的关键字 ST.R[mid].key 相比较，因为 36 > 27，说明待查元素若存在，必在区间[low, mid - 1]的范围内，则令指针 high 指向第 mid - 1 个元素，high = 5，重新求得 mid = ⌊(1 + 5)/2⌋ = 3。

然后仍以 key 和 ST.R[mid].key 相比，因为 20<27，说明待查待元素若存在，必在[mid + 1，high]范围内，则令指针 low 指向第 mid + 1 个元素，low = 4 求得 mid 的新值为 4，比较 key 和 ST.R[mid].key，因为相等，则查找成功，返回所查元素在表中的序号，即指针 mid 的值 4。

查找关键字 key = 65 的折半查找过程如图 7.1（b）所示。

查找过程同上，只是在图 7.1（b）中的最后一趟查找时，因为 low > high，查找区间不存在，则说明表中没有关键字等于 65 的元素，查找失败，返回 0。

【算法分析】

折半查找过程可用二叉树来描述。树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。把当前查找区间的中间位置作为根，左子表和右子表分别作为根的左子树和右子树，由此得到的二叉树称为折半查找的判定树。

例 7.1 中的有序表对应的判定树如图 7.2 所示。从判定树上可见，成功的折半查找恰好是走了一

条从判定树的根到被查结点的路径，经历比较的关键字个数恰为该结点在树中的层次。例如，查找27的过程经过一条从根到结点④的路径，需要比较3次，比较次数即为结点④所在的层次。图7.2中比较1次的只有一个根结点，比较2次的有两个结点，比较3次和4次的各有四个结点。假设每个记录的查找概率相同，根据此判定树可知，对长度为11的有序表进行折半查找的平均查找长度为

$$ ASL=\frac{1}{11}(1+2\times2+3\times4+4\times4)=3 $$

由此可见，折半查找法在查找成功时进行比较的关键字个数最多不超过树的深度。而判定树的形态只与表记录个数 $n$ 相关，而与关键字的取值无关，具有 $n$ 个结点的判定树的深度为$\lfloor \log_2 n \rfloor + 1$。所以，对于长度为 $n$ 的有序表，折半查找法在查找成功时和给定值进行比较的关键字个数至多为$\lfloor \log_2 n \rfloor + 1$。

如果在图 7.2 所示的判定树中所有结点的空指针域上加一个指向一个方形结点的指针，如图 7.3 所示。并且，称这些方形结点为判定树的外部结点（与之相对，称那些圆形结点为内部结点），那么折半查找时查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较的关键字个数等于该路径上内部结点个数。例如，查找 65 的过程即为走了一条从根到结点 9～10 的路径。因此，折半查找在查找不成功时和给定值进行比较的关键字个数最多也不超过 $ \lfloor \log_2 n \rfloor + 1 $。

借助于判定树，很容易求得折半查找的平均查找长度。为了讨论方便起见，假定有序表的长度 $ n = 2^h - 1 $，则判定树是深度为 $ h = \log_2(n + 1) $ 的满二叉树。树中层次为 1 的结点有 1 个，层次为 2 的结点有 2 个，…，层次为 $ h $ 的结点有 $ 2^{h-1} $ 个。假设表中每个记录的查找概率相等 $ \left(P_i = \frac{1}{n}\right) $，则查找成功时折半查找的平均查找长度为

$$ \begin{aligned}ASL&=\sum_{i=1}^{n}P_{i}C_{i}\\&=\frac{1}{n}\sum_{j=1}^{h}j\cdot2^{j-1}\\&=\frac{n+1}{n}log_{2}(n+1)-1\end{aligned} $$

当n较大时，可有下列近似结果

$$ ASL=\log_{2}(n+1)-1 $$

因此，折半查找的时间复杂度为 $ O(\log_{2}n) $。可见，折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构。

折半查找的优点是：比较次数少，查找效率高。其缺点是：对表结构要求高，只能用于顺序存储的有序表。查找前需要排序，而排序本身是一种费时的运算。同时为了保持顺序表的有序性，对有序表进行插入和删除时，平均比较和移动表中一半元素，这也是一种费时的运算。因此，折半查找不适用于数据元素经常变动的线性表。

7.2.3 分块查找

分块查找（Blocking Search）又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法。在此查找法中，除表本身以外，尚需建立一个“索引表”。例如，图7.4所示为一个表及其索引表，表中含有18个记录，可分成3个子表（ $ R_{1} $， $ R_{2} $，…， $ R_{6} $）、（ $ R_{7} $， $ R_{8} $，…， $ R_{12} $）、（ $ R_{13} $， $ R_{14} $，…， $ R_{18} $），对每个子表（或称块）建立一个索引项，其中包括两项内容：关键字项（其值为该子表内的最大关键字）和指针项（指示该子表的第一个记录在表中位置）。索引表按关键字有序，则表或者有序或者分块有序。所谓“分块有序”指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字，……，依次类推。

因此，分块查找过程需分两步进行。先确定待查记录所在的块（子表），然后在块中顺序查找。假设给定值 key = 38，则先将 key 依次和索引表中各最大关键字进行比较，因为 22 < key < 48，则关键字为 38 的记录若存在，必定在第二个子表中，由于同一索引项中的指针指示第二个子表中的第一个记录是表中第 7 个记录，则自第 7 个记录起进行顺序查找，直到 ST.elem[10].key = key 为止。假如此子表中没有关键字等于 key 的记录（例如：key = 29 时自第 7 个记录起至第 12 个记录的关键字和 key 比较都不等），则查找不成功。

由于由索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找，亦可用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找。

由此，分块查找的算法为顺序查找和折半查找两种算法的简单合成。

分块查找的平均查找长度为

$$ ASL_{bs}=L_{b}+L_{w} $$

其中， $ L_{b} $ 为查找索引表确定所在块的平均查找长度， $ L_{w} $ 为在块中查找元素的平均查找长度。

一般情况下，为进行分块查找，可以将长度为 $n$ 的表均匀地分成 $b$ 块，每块含有 $s$ 个记录，即 $b = \lceil n/s \rceil$；又假定表中每个记录的查找概率相等，则每块查找的概率为 $1/b$，块中每个记录的查找概率为 $1/s$。

若用顺序查找确定所在块，则分块查找的平均查找长度为

$$ \begin{aligned}ASL_{bs}&=L_{b}+L_{w}=\frac{1}{b}\sum_{j=1}^{b}j+\frac{1}{s}\sum_{i=1}^{s}i=\frac{b+1}{2}+\frac{s+1}{2}\\&=\frac{1}{2}\bigg(\frac{n}{s}+s\bigg)+1\end{aligned} $$

可见，此时的平均查找长度不仅和表长 $n$ 有关，而且和每一块中的记录个数 $s$ 有关。在给定 $n$ 的前提下，$s$ 是可以选择的。容易证明，当 $s$ 取 $\sqrt{n}$ 时，$ASL_{bs}$ 取最小值 $\sqrt{n}+1$。这个值比顺序查找有了很大改进，但远不及折半查找。

若用折半查找确定所在块，则分块查找的平均查找长度为

$$ ASL_{bs}^{\prime}\approx\log_{2}\left(\frac{n}{s}+1\right)+\frac{s}{2} $$

分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。其缺点是：要增加一个索引表的存储空间并对初始索引表进行排序运算。

7.3 树表的查找

前面介绍的3种查找方法都是用线性表作为查找表的组织形式，其中折半查找效率较高。但由于折半查找要求表中记录按关键字有序排列，且不能用链表做存储结构，因此，当表的插入或删除操作频繁时，为维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消折半查找的优点。所以，线性表的查找更适用于静态查找表，若要对动态查找表进行高效率的查找，可采用几种特殊的二叉树作为查找表的组织形式，在此将它们统称为树表。本节将介绍在这些树表上进行查找和修改操作的方法。

7.3.1 二叉排序树

二叉排序树（Binary Sort Tree）又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。

1. 二叉排序树的定义

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）它的左、右子树也分别为二叉排序树。

二叉排序树是递归定义的。由定义可以得出二叉排序树的一个重要性质：中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。

例如，图7.5所示为两棵二叉排序树。

若中序遍历图 7.5（a），则可得到一个按数值大小排序的递增序列：

3,12,24,37,45,53,61,78,90,100

若中序遍历图 7.5（b），则可得到一个按字符大小排序的递增序列：

CAO, CHEN, DING, DU, LI, MA, WANG, XIA, ZHAO

在下面讨论二叉排序树的操作中，使用二叉链表作为存储结构。因为二叉排序树的操作要根据结点的关键字域来进行，所以下面给出了每个结点的数据域的类型定义（包括关键字项和其他数据项）。

// -- -- -- 二叉排序树的二叉链表存储表示 --

typedef struct

{
    KeyType key;
    InfoType otherinfo;
}ElemType;

typedef struct BSTNode

{
    ElemType data;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTre;

// 关键字项
// 其他数据项
// 每个结点的数据域的类型
// 每个结点的数据域包括关键字项和其他数据项
// 左右孩子指针

2. 二叉排序树的查找

因为二叉排序树可以看成是一个有序表，所以在二叉排序树上进行查找和折半查找类似，也是一个逐步缩小查找范围的过程。

算法 7.4 二叉排序树的递归查找

【算法步骤】

① 若二叉排序树为空，则查找失败，返回空指针。

② 若二叉排序树非空，将给定值 key 与根结点的关键字 T->data.key 进行比较：

若 key 等于 T -> data.key，则查找成功，返回根结点地址；

若 key 小于 T->data.key，则递归查找左子树；

若 key 大于 T->data.key，则递归查找右子树。

模仿折半查找算法 7.3，读者很容易写出二叉排序树查找的非递归算法。下面以递归形式给出此查找算法。

【算法描述】

BSTree SearchBST(BSTree T,KeyType key)

{
    //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素

    //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针

    if((!T)||key==T->data.key) return T;
    else if(key<T->data.key) return SearchBST(T->lchild,key);
    else return SearchBST(T->rchild,key);
}

例如，在图 7.5（a）所示的二叉排序树中查找关键字等于 100 的记录（树中结点内的数均为记录的关键字）。首先以 key = 100 和根结点的关键字做比较，因为 key > 45，则查找以④为根的右子树，此时右子树不空，且 key > 53，则继续查找以结点③为根的右子树，由于 key 和③的右子树根的关键字 100 相等，则查找成功，返回指向结点⑩的指针值。又如在图 7.5（a）中

查找关键字等于40的记录，和上述过程类似，在给定值key与关键字45、12及37相继比较之后，继续查找以结点 $ ^{37} $为根的右子树，此时右子树为空，则说明该树中没有待查记录，故查找不成功，返回指针值为“NULL”。

【算法分析】

从上述的两个查找例子（key=100和key=40）可见，在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加1（或结点所在层次数）。因此，和折半查找类似，与给定值比较的关键字个数不超过树的深度。然而，折半查找长度为n的顺序表的判定树是唯一的，而含有n个结点的二叉排序树却不唯一。图7.6中（a）和（b）的两棵二叉排序树中结点的值都相同，但创建这两棵树的序列不同，分别是：（45，24，53，12，37，93）和（12，24，37，45，53，93）。（a）树的深度为3，而（b）树的深度为6。再从平均查找长度来看，假设6个记录的查找概率相等，为1/6，则（a）树的平均查找长度为

$$ ASL_{(a)}=\frac{1}{6}[1+2+2+3+3+3]=14/6 $$

而（b）树的平均查找长度为

$$ A S L_{(b)}=\frac{1}{6}\left[1+2+3+4+5+6\right]=21/6 $$

因此，含有 $n$ 个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树。树的深度为 $n$，其平均查找长度为 $\frac{n+1}{2}$（和顺序查找相同），这是最差的情况。显然，最好的情况是，二叉排序树的形态和折半查找的判定树相似，其平均查找长度和 $\log_{2}n$ 成正比。若考虑把 $n$ 个结点按各种可能的次序插入到二叉排序树中，则有 $n$! 棵二叉排序树（其中有的形态相同）。可以证明，综合所有可能的情况，就平均而言，二叉排序树的平均查找长度仍然和 $\log_{2}n$ 是同数量级的。

可见，二叉排序树上的查找和折半查找相差不大。但就维护表的有序性而言，二叉排序树更加有效，因为无需移动记录，只需修改指针即可完成对结点的插入和删除操作。因此，对于需要经常进行插入、删除和查找运算的表，采用二叉排序树比较好。

3. 二叉排序树的插入

二叉排序树的插入操作是以查找为基础的。要将一个关键字值为 key 的结点*S 插入到二叉排序

树中，则需要从根结点向下查找，当树中不存在关键字等于key的结点时才进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

算法 7.5 二叉排序树的插入

【算法步骤】

① 若二叉排序树为空，则待插入结点 $ ^{*} $S作为根结点插入到空树中。

② 若二叉排序树非空，则将 key 与根结点的关键字 T->data.key 进行比较：

若 key 小于 T->data.key，则将*S 插入左子树；

若 key 大于 T->data.key，则将*S 插入右子树。

【算法描述】

void InsertBST(BSTree &T,ElemType e)
{
    //当二叉排序树T中不存在关键字等于e.key的数据元素时，则插入该元素
    if(!T)
        {
            S=new BSTNode;
            S->data=e;
            S->lchild=S->rchild=NULL;
            T=S;
        }
        else if(e.key<T->data.key)
            InsertBST(T->lchild,e);
        else if (e.key>T->data.key)
            InsertBST(T->rchild,e);
    }

例如，在图7.5（a）所示的二叉排序树上插入关键字为55的结点，由于插入前二叉排序树非空，故将55和根结点45进行比较，因55>45，则应将55插入到45的右子树上；又和45的右子树的根53比较，因55>53，则应将55插入到53的右子树上；依次类推，直至最后55<61，且61的左子树为空，将55作为61的左孩子插入到树中。结果如图7.7所示。

【算法分析】

二叉排序树插入的基本过程是查找，所以时间复杂度同查找一样，是 $ O(\log_{2}n) $。

4. 二叉排序树的创建

二叉排序树的创建是从空的二叉排序树开始的，每输入一个结点，经过查找操作，将新结点插入到当前二叉排序树的合适位置。

算法 7.6 二叉排序树的创建

【算法步骤】

① 将二叉排序树 T 初始化为空树。

② 读入一个关键字为 key 的结点。

③ 如果读入的关键字 key 不是输入结束标志，则循环执行以下操作：

将此结点插入二叉排序树T中；

读入一个关键字为 key 的结点。

【算法描述】

void CreatBST(BSTree &T)

{
    //依次读入一个关键字为key的结点，将此结点插入二叉排序树T中
    T=NULL;
    cin>>e;
    while(e.key!=ENDFLAG)
    {
        InsertBST(T,e);
        cin>>e;
    }
}

【算法分析】

假设有 n 个结点，则需要 n 次插入操作，而插入一个结点的算法时间复杂度为 $ O(\log_2 n) $，所以创建二叉排序树算法的时间复杂度为 $ O(n\log_2 n) $。

例如，设关键字的输入次序为：45, 24, 53, 45, 12, 24, 90，按上述算法生成的二叉排序树的过程如图7.8所示。

容易看出，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。不仅如此，从上面的插入过程还可以看到，每次插入的新结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不必移动其他结点，仅需改动某个结点的指针，由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其他记录。

5. 二叉排序树的删除

被删除的结点可能是二叉排序树中的任何结点，删除结点后，要根据其位置不同修改其双亲结点及相关结点的指针，以保持二叉排序树的特性。

算法 7.7 二叉排序树的删除

【算法步骤】

首先从二叉排序树的根结点开始查找关键字为 key 的待删结点，如果树中不存在此结点，则不做任何操作；否则，假设被删结点为*p（指向结点的指针为 p），其双亲结点为*f（指向结点的指针为 f），P_L 和 P_R 分别表示其左子树和右子树（见图 7.9（a））。

不失一般性，可设 $ ^{*}p $是 $ ^{*}f $的左孩子（右孩子情况类似）。下面分3种情况进行讨论。

（1）若 $ ^{*}p $结点为叶子结点，即 $ P_{L} $和 $ P_{R} $均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。

$$ f->l child=NULL; $$

（2）若 $ ^{*}p $结点只有左子树 $ P_{L} $或者只有右子树 $ P_{R} $，此时只要令 $ P_{L} $或 $ P_{R} $直接成为其双亲结点 $ ^{*}f $的左子树即可。

$$ \mathrm{f->}lchild=\mathrm{p->}lchild;( 或 \mathrm{f->}lchild=\mathrm{p->}rchild;) $$

（3）若*p 结点的左子树和右子树均不空。从图 7.9（b）可知，在删去*p 结点之前，中序遍历该二叉树得到的序列为{…CₗC…QₗQSₗSPPₕF…}，在删去*p 之后，为保持其他元素之间的相对位置不变，可以有两种处理方法：

① 令 $ ^{*} $p的左子树为 $ ^{*} $f的左子树，而 $ ^{*} $p的右子树为 $ ^{*} $s的右子树，如图7.9（c）所示。

$$ \mathrm{f->}lchild=\mathrm{p->}lchild;\mathrm{s->}rchild=\mathrm{p->}rchild; $$

② 令*p 的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。如图 7.9（d）所示，当以直接前驱*s 替代*p 时，由于*s 只有左子树 S_L，则在删去*s 之后，只要令 S_L 为*s 的双亲*q 的右子树即可。

$$ p->data=s->data;q->r child=s->l child; $$

显然，前一种处理方法可能增加树的深度，而后一种方法是以被删结点左子树中关键字最大的结点替代被删结点，然后从左子树中删除这个结点。此结点一定没有右子树（否则它就不是左子树中关键字最大的结点），这样不会增加树的高度，所以常采用这种处理方案。下面的算法描述即采用这种方案。

【算法描述】

//从二叉排序树T中删除关键字等于key的结点

p=T; f=NULL;
//初始化
/*-----下面的 while 循环从根开始查找关键字等于 key 的结点*p-----*/
while(p)
{
    if(p->data.key==key) break;
    f=p;
    if(p->data.key>key) p=p->lchild;
    else p=p->rchild;
}
if(!p) return;
// 找到关键字等于 key 的结点*p，结束循环
//*f 为*p 的双亲结点
//在*p 的左子树中继续查找
//在*p 的右子树中继续查找
//while
// 找不到被删结点则返回

/*-----考虑3种情况实现p所指子树内部的处理：*p左右子树均不空、无右子树、无左子树---*/

if ((p->lchild) && (p->rchild))

{
    q=p; s=p->lchild;
    while (s->rchild) {
        //在*p的左子树中继续查找其前驱结点，即最右
        {
            q=s; s=s->rchild;
        }
        p->data=s->data;
        if (q!=p) q->rchild=s->lchild;
        else q->lchild=s->lchild;
        delete s;
        return;
    }
    else if(!p->rchild) {
        // if
        //被删结点*p无右子树，只需重接其左子树
        {
            q=p; p=p->lchild;
        } //else if
        else if(!p->lchild) {
            //被删结点*p无左子树，只需重接其右子树
        }
        q=p; p=p->rchild;
        //else if
        /*-----将p所指的子树挂接到其双亲结点*f相应的位置-----*/
        if(!f) T=p;
        else if(q==f->lchild) f->lchild=p;
        else f->rchild=p;
        delete q;
    }
}

【算法分析】

同二叉排序树插入一样，二叉排序树删除的基本过程也是查找，所以时间复杂度仍是 $ O(\log_{2}n) $。

根据算法7.7，图7.10所示给出了二叉排序树删除的3种情况。

7.3.2 平衡二叉树

1. 平衡二叉树的定义

二叉排序树查找算法的性能取决于二叉树的结构，而二叉排序树的形状则取决于其数据集。如果数据呈有序排列，则二叉排序树是线性的，查找的时间复杂度为 $ O(n) $；反之，如果二叉排序树的结构合理，则查找速度较快，查找的时间复杂度为 $ O(\log_2 n) $。事实上，树的高度越小，查找速度越快。因此，希望二叉树的高度尽可能小。本节将讨论一种特殊类型的二叉排序树，称为平衡二叉树（Balanced Binary Tree 或 Height-Balanced Tree），因由前苏联数学家 Adelson-Velskii 和 Landis 提出，所以又称 AVL 树。

平衡二叉树或者是空树，或者是具有如下特征的二叉排序树：

（1）左子树和右子树的深度之差的绝对值不超过1；

（2）左子树和右子树也是平衡二叉树。

若将二叉树上结点的平衡因子（Balance Factor，BF）定义为该结点左子树和右子树的深度之差，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。图7.11（a）所示为两棵平衡二叉树，而图7.11（b）所示为两棵不平衡的二叉树，结点中的值为该结点的平衡因子。

因为 AVL 树上任何结点的左右子树的深度之差都不超过 1，则可以证明它的深度和 $ \log_{2}n $ 是同数量级的（其中 n 为结点个数）。由此，其查找的时间复杂度是 $ O(\log_{2}n) $。

2. 平衡二叉树的平衡调整方法

如何创建一棵平衡二叉树呢？插入结点时，首先按照二叉排序树处理，若插入结点后破坏了平衡二叉树的特性，需对平衡二叉树进行调整。调整方法是：找到离插入结点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为最小不平衡子树，可将重新平衡的范围局限于这棵子树。

先看一个具体例子（见图7.12）。假设表中关键字序列为（13，24，37，90，53）。

（1）空树和1个结点 $ ^{⑬} $的树显然都是平衡的二叉树。在插入24之后仍是平衡的，只是根结点的平衡因子BF由0变为-1，如图7.12（a）～（c）所示。

（2）在继续插入37之后，由于结点 $ ^{⑬} $的BF值由-1变成-2，由此出现了不平衡的现象。此时好比一根扁担出现一头重一头轻的现象，若能将扁担的支撑点由 $ ^{⑬} $改至 $ ^{⑳} $，扁担的两头

就平衡了。由此，可以对树做一个向左逆时针“旋转”的操作，令结点②为根，而结点③为它的左子树，此时，结点③和②的平衡因子都为0，而且仍保持二叉排序树的特性，如图7.12（d）～（e）所示。

（3）在继续插入90和53之后，结点37的BF值由-1变成-2，排序树中出现了新的不平衡现象，需进行调整。但此时由于是结点38插在结点90的左子树上，因此不能如上做简单调整。离插入结点最近的最小不平衡子树是以结点37为根的子树。这时，必须以3作为根结点，而使37成为它的左子树的根，90成为它的右子树的根。这好比对树做了两次“旋转”操作，先向右顺时针旋转，后向左逆时针旋转（见图7.12（f）～（h）），使二叉排序树由不平衡转化为平衡。

一般情况下，假设最小不平衡子树的根结点为 A，则失去平衡后进行调整的规律可归纳为下列 4 种情况。

（1）LL型：由于在A左子树根结点的左子树上插入结点，A的平衡因子由1增至2，致使以A为根的子树失去平衡，则需进行一次向右的顺时针旋转操作，如图7.13所示。

图 7.14 所示为两个 LL 型调整的实例。

（2）RR型：由于在A的右子树根结点的右子树上插入结点，A的平衡因子由-1变为-2，致使以A为根结点的子树失去平衡，则需进行一次向左的逆时针旋转操作，如图7.15所示。

图 7.16 所示为两个 RR 型调整的实例。

（3）LR型：由于在A的左子树根结点的右子树上插入结点，A的平衡因子由1增至2，致使以A为根结点的子树失去平衡，则需进行两次旋转操作。第一次对B及其右子树进行逆时针旋转，C转上去成为B的根，这时变成了LL型，所以第二次进行LL型的顺时针旋转即可恢复平衡。如果C原来有左子树，则调整C的左子树为B的右子树，如图7.17所示。

LR 型旋转前后 A、B、C 三个结点平衡因子的变化分为 3 种情况，图 7.18 所示为 3 种 LR 型调整的实例。

（4）RL型：由于在A的右子树根结点的左子树上插入结点，A的平衡因子由-1变为-2，致使以A为根结点的子树失去平衡，则旋转方法和LR型相对称，也需进行两次旋转，先顺时针右旋，再逆时针左旋，如图7.19所示。

同 LR 型旋转类似，RL 型旋转前后 A、B、C 三个结点的平衡因子的变化也分为 3 种情况，图 7.20 所示为 3 种 RL 型调整的实例。

上述4种情况中，（1）和（2）对称，（3）和（4）对称。旋转操作的正确性容易由“保持二叉排序树的特性：中序遍历所得关键字序列自小至大有序”证明之。同时，无论哪一种情况，在经过平衡旋转处理之后，以B或C为根的新子树为平衡二叉树，而且它们的深度和插入之前以A为根的子树相同。因此，当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转处理即可。因为经过旋转处理之后的子树深度和插入之前相同，因而不影响插入路径上所有祖先结点的平衡度。

3. 平衡二叉树的插入

在平衡的二叉排序树 BBST 上插入一个新的数据元素 e 的递归算法可描述如下。

① 若 BBST 为空树，则插入一个数据元素为 e 的新结点作为 BBST 的根结点，树的深度增 1。

② 若 e 的关键字和 BBST 的根结点的关键字相等，则不进行插入。

③ 若 e 的关键字小于 BBST 的根结点的关键字，而且在 BBST 的左子树中不存在和 e 有相同关键字的结点，则将 e 插入在 BBST 的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：

BBST 的根结点的平衡因子为-1（右子树的深度大于左子树的深度）：则将根结点的平衡因子更改为 0，BBST 的深度不变；

BBST 的根结点的平衡因子为 0（左、右子树的深度相等）：则将根结点的平衡因子更改为 1，BBST 的深度增 1；

BBST 的根结点的平衡因子为 1（左子树的深度大于右子树的深度）：若 BBST 的左子树根结点的平衡因子为 1，则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为 0，树的深度不变；

若 BBST 的左子树根结点的平衡因子为 -1，则需进行先向左、后向右的双向旋转平衡处理，并且在旋转处理之后。修改根结点和其左、右子树根结点的平衡因子，树的深度不变。

④ 若 e 的关键字大于 BBST 的根结点的关键字，而且在 BBST 的右子树中不存在 e 有相同关键字的结点，则将 e 插入在 BBST 的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。其处理操作和③中所述相对称，读者可自行补充。

7.3.3 B-树

前面介绍的查找方法均适用于存储在计算机内存中较小的文件，统称为内查找法。若文件很大且存放于外存进行查找时，这些查找方法就不适用了。内查找法都以结点为单位进行查找，这样需要反复地进行内、外存的交换，是很费时的。1970年，R.Bayer和E.Mccreight提出了一种适用于外查找的平衡多叉树——B-树，磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数都采用B-树这种数据结构。

1. B-树的定义

一棵 m 阶的 B-树，或为空树，或为满足下列特性的 m 叉树：

（1）树中每个结点至多有 m 棵子树；

（2）若根结点不是叶子结点，则至少有两棵子树；

（3）除根之外的所有非终端结点至少有 $ \lceil m/2\rceil $棵子树；

（4）所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（失败结点并不存在，指向这些结点的指针为空。引入失败结点是为了便于分析 B-树的查找性能）；

（5）所有的非终端结点最多有 m-1 个关键字，结点的结构如图 7.21 所示。

其中， $ K_i $ ( $ i=1,\cdots,n $) 为关键字，且 $ K_i < K_{i+1} $ ( $ i=1,\cdots,n-1 $); $ P_i $ ( $ i=0,\cdots,n $) 为指向子树根结点的指针，且指针 $ P_{i-1} $ 所指子树中所有结点的关键字均小于 $ K_i $ ( $ i=1,\cdots,n $)， $ P_n $ 所指子树中所有结点的关键字均大于 $ K_n $， $ n\lceil m/2\rceil-1 \leq n \leq m-1 $ 为关键字的个数（或 $ n+1 $ 为子树

个数)。

从上述定义可以看出，对任一关键字 $ K_{i} $ 而言， $ P_{i-1} $ 相当于指向其“左子树”， $ P_{i} $ 相当于指向其“右子树”。

B-树具有平衡、有序、多路的特点，图7.22所示为一棵4阶的B-树，能很好地说明其特点。

（1）所有叶子结点均在同一层次，这体现出其平衡的特点。

（2）树中每个结点中的关键字都是有序的，且关键字 $ K_{i} $ “左子树” 中的关键字均小于 $ K_{i} $，而其“右子树” 中的关键字均大于 $ K_{i} $，这体现出其有序的特点。

（3）除叶子结点外，有的结点中有一个关键字，两棵子树，有的结点中有两个关键字，三棵子树，这种4阶的B-树最多有三个关键字，四棵子树，这体现出其多路的特点。

在具体实现时，为记录其双亲结点，B-树结点的存储结构通常增加一个 parent 指针，指向其双亲结点，存储结构示意图如图 7.23 所示。

2. B-树的查找

由 B-树的定义可知，在 B-树上进行查找的过程和二叉排序树的查找类似。

例如，在图 7.22 所示的 B-树上查找关键字 47 的过程如下：首先从根开始，根据根结点指针 t 找到*a 结点，因*a 结点中只有一个关键字，且 47 > 35，若查找的记录存在，则必在指针 P₁ 所指的子树内，顺指针找到*c 结点，该结点有两个关键字（43 和 78），而 43 < 47 < 78，若查找的记录存在，则必在指针 P₁ 所指的子树中。同样，顺指针找到*g 结点，在该结点中顺序查找，找到关键字 47，由此，查找成功。

查找不成功的过程也类似，例如，在同一棵树中查找 23。从根开始，因为 23 < 35，则顺该结点中指针 $ P_0 $ 找到 *b 结点，又因为 *b 结点中只有一个关键字 18，且 23 > 18，所以顺结点中第二个指针 $ P_1 $ 找到 *e 结点。同理，因为 23 < 27，则顺指针往下找，此时因指针所指为叶子结点，说明此棵 B-树中不存在关键字 23，查找因失败而告终。

由此可见，在 B-树上进行查找的过程是一个顺指针查找结点，和在结点的关键字中查找交叉进行的过程。

由于 B-树主要用做文件的索引，因此它的查找涉及外存的存取，在此略去外存的读写，只做

示意性的描述。假设结点类型定义如下：

#define m3 // B-树的阶，暂设为3

typedef struct BTNode

{
    int keynum; // 结点中关键字的个数，即结点的大小
    struct BTNode *parent; // 指向双亲结点
    KeyType key[m+1]; // 关键字向量，0号单元未用
    struct BTNode *ptr[m+1]; // 子树指针向量
    Record *recptr[m+1]; // 记录指针向量，0号单元未用
} BTNode, *BTree; // B-树结点和B-树的类型

typedef struct

{
    BTNode *pt; // 指向找到的结点
    int i; // 1..m，在结点中的关键字序号
    int tag; // 1：查找成功，0：查找失败
} Result; // B-树的查找结果类型

算法 7.8 B-树的查找

【算法步骤】

将给定值 key 与根结点的各个关键字 $ K_1, K_2, \cdots, K_j $（ $ 1 \leq j \leq m-1 $）进行比较，由于该关键字序列是有序的，所以查找时可采用顺序查找，也可采用折半查找。查找时：

① 若 key = $ K_i $ ( $ 1 \leq i \leq j $)，则查找成功；

② 若 key<K_{1}，则顺着指针 P_{0} 所指向的子树继续向下查找；

③ 若 $ K_i < key < K_{i+1} $（ $ 1 \leq i \leq j-1 $），则顺着指针 $ P_i $ 所指向的子树继续向下查找；

④ 若 key > K_{j}，则顺着指针 P_{j} 所指向的子树继续向下查找。

如果在自上而下的查找过程中，找到了值为 key 的关键字，则查找成功；如果直到叶子结点也未找到，则查找失败。

【算法描述】

Result SearchBTree(BTree T,KeyType key)

{
    // 在 m 阶 B-树 T 上查找关键字 key，返回结果 (pt, i, tag)

    // 若查找成功，则特征值 tag=1，指针 pt 所指结点中第 i 个关键字等于 key

    // 否则特征值 tag=0，等于 key 的关键字应插入在指针 pt 所指结点中第 i 和第 i+1 个关键字之间

    p=T; q=NULL; found=FALSE; i=0; // 初始化，p 指向待查结点，q 指向 p 的双
while (p&&!found)
{
    i=Search(p, key);
    // 在 p->key[1..keynum] 中查找 i，使得：p->key[i] <= key<p->key[i+1]
    if (i > 0 && p->key[i]==k)     found=TRUE; // 找到待查关键字
    else { q=p; p=p->ptr[i]; }
}
if (found) return (p, i, l); // 查找成功
else return (q, i, 0); // 查找成功，返回 K 的插入位置信息
}

【算法分析】

从算法7.8可见，在B-树上进行查找包含两种基本操作：（1）在B-树中找结点；（2）在结点

中找关键字。由于 B-树通常存储在磁盘上，则前一查找操作是在磁盘上进行的（在算法 7.8 中没有体现），而后一查找操作是在内存中进行的，即在磁盘上找到指针 p 所指结点后，先将结点中的信息读入内存，然后再利用顺序查找或折半查找查询等于 K 的关键字。显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多出很多，因此，在磁盘上进行查找的次数，即待查关键字所在结点在 B-树上的层次数，是决定 B-树查找效率的首要因素。

现考虑最坏的情况，即待查结点在 B-树的最下面一层。也就是说，含 N 个关键字的 m 阶 B-树的最大深度是多少？

先看一棵3阶的B-树。按B-树上的定义，3阶的B-树上所有非终端结点至多可有两个关键字，至少有一个关键字（即子树个数为2或3，故又称2-3树）。因此，若关键字个数≤2时，树的深度为2（即叶子结点层次为2）；若关键字个数≤6时，树的深度不超过3。反之，若B-树的深度为4，则关键字的个数必须≥7（见图7.24（g）），此时，每个结点都含有可能的关键字的最小数目。

一般情况的分析可类似平衡二叉树进行，先讨论深度为 $ h+1 $ 的 m 阶 B-树所具有的最少结点数。

根据 B-树的定义，第一层至少有 1 个结点；第二层至少有 2 个结点；由于除根之外的每个非终端结点至少有 $ \lceil m/2 \rceil $ 棵子树，则第三层至少有 $ 2(\lceil m/2 \rceil) $ 个结点；……；依次类推，第 $ h+1 $ 层至少有 $ 2(\lceil m/2 \rceil)^{h-1} $ 个结点。而 $ h+1 $ 层的结点为叶子结点。若 $ m $ 阶 B-树中具有 $ N $ 个关键字，则叶子结点即查找不成功的结点为 $ N+1 $，由此有：

$$ N+1\geq2\times\left(\lceil m/2\rceil\right)^{h-1} $$

反之

$$ h\leqslant\log\left|m/2\right|\left(\frac{N+1}{2}\right)+1 $$

这就是说，在含有 $N$ 个关键字的 B-树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过 $\log_{\lceil m/2\rceil}\left(\frac{N+1}{2}\right)+1$。

3. B-树的插入

B-树是动态查找树，因此其生成过程是从空树起，在查找的过程中通过逐个插入关键字而得到。但由于 B-树中除根之外的所有非终端结点中的关键字个数必须大于等于 $ \lceil m/2 \rceil - 1 $，因此，每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过 $ m - 1 $，则插入完成，否则表明结点已满，要产生结点的“分裂”，将此结点在同一层分成两个结点。一般情况下，结点分裂方法是：以中间关键字为界把结点一分为二，成为两个结点，并把中间关键字向上插入到双亲结点上，若双亲结点已满，则采用同样的方法继续分解。最坏的情况下，一直分解到树根结点，这时 B-树高度增加 1。

例如，图 7.25（a）所示为 3 阶的 B-树（图中略去 F 结点（即叶子结点）），假设需依次插入关键字 30、26、85 和 7。首先通过查找确定应插入的位置。由根*a 起进行查找，确定 30 应插入在*d 结点中，由于*d 中关键字数目不超过 2（即 $ m-1 $），故第一个关键字插入完成。插入 30 后的 B-树如图 7.25（b）所示。同样，通过查找确定关键字 26 亦应插入在*d 结点中。由于*d 中关键字的数目超过 2，此时需将*d 分裂成两个结点，关键字 26 及其前、后两个指针仍保留在*d 结点中，而关键字 37 及其前、后两个指针存储到新产生的结点*d 中。同时，将关键字 30 和指示结点*d 的指针插入到其双亲结点中。由于*b 结点中的关键字数目没有超过 2，则插入完成。插入后的 B-树如图 7.25（d）所示。类似地，在*g 中插入 85 之后需分裂成两个结点，而当 70 继而插入到双亲结点中时，由于*e 中关键字数目超过 2，则再次分裂为结点*e 和*e'，如图 7.25（g）所示。最后在插入关键字 7 时，*c、*b 和*a 相继分裂，并生成一个新的根结点*m，如图 7.25（h）～（j）所示。

算法 7.9 B-树的插入

【算法步骤】

① 在 B-树中查找给定关键字的记录，若查找成功，则插入操作失败；否则将新记录作为空指针 p 插入到查找失败的叶子结点的上一层结点（由 q 指向）中。

② 若插入新记录和空指针后，q 指向的结点的关键字个数未超过 m-1，则插入操作成功，否则转入步骤③。

③ 以该结点的第 $ m/2 $ 个关键字 $ K_{\lceil m/2\rceil} $ 为拆分点，将该结点分成 3 个部分： $ K_{\lceil m/2\rceil} $ 左边部分、 $ K_{\lceil m/2\rceil} $、 $ K_{\lceil m/2\rceil} $ 右边部分。 $ K_{\lceil m/2\rceil} $ 左边部分仍然保留在原结点中； $ K_{\lceil m/2\rceil} $ 右边部分存放在一个新创建的结点（由 p 指向）中；关键字值为 $ K_{\lceil m/2\rceil} $ 的记录和指针 p 插入到 q 的双亲结点中。因 q 的双亲结点增加一个新的记录，所以必须对 q 的双亲结点重复②和③的操作，依次类推，直至由 q 指向的结点是根结点，转入步骤④。

④ 由于根结点无双亲，则由其分裂产生的两个结点的指针 p 和 q，以及关键字为 $ K_{[m/2]} $ 的记录构成一个新的根结点。此时，B-的高度增加 1。

下面算法描述中的 q 和 i 是由查找函数 SearchBTree 返回的信息而得。

【算法描述】

Status InsertBTree(BTree &T,KeyType K,BTree q,int i)

{
    //在m阶B-树T上结点*q的key[i]与key[i+1]之间插入关键字K

    //若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶B-树
    x=K;ap=NULL;finished=FALSE;    //x表示新插入的关键字，ap为一个空指针
    while(q&&!finished)
        {
            Insert(q,i,x,ap);     //将x和ap分别插入到q->key[i+1]和q->ptr[i+1]

if (q -> keynum < m) finished = TRUE;     // 插入完成
else                                            // 分裂结点*q
{
    s = [m/2]; split(q, s, ap); x = q -> key[s];
    // 将 q -> key[s + 1..m], q -> ptr[s..m] 和 q -> recptr[s + 1..m] 移入新结点 * ap
    q = q -> parent;
    if (q) i = Search(q, x);     // 在双亲结点 * q 中查找 x 的插入位置
    // else
    // while
    if (!finished)           // T 是空树（参数 q 初值为 NULL）或者根结点已分裂为结点 * q 和 * ap
    NewRoot(T, q, x, ap);           // 生成含信息（T, x, ap）的新的根结点 * T，原 T 和 ap 为子树指针
    return OK;
}

4. B-树的删除

m 阶 B-树的删除操作是在 B-树的某个结点中删除指定的关键字及其邻近的一个指针，删除后应该进行调整使该树仍然满足 B-树的定义，也就是要保证每个结点的关键字数目范围为 $ [m/2]-1, m] $。删除记录后，结点的关键字个数如果小于 $ [m/2]-1 $，则要进行“合并”结点的操作。除了删除记录，还要删除该记录邻近的指针。若该结点为最下层的非终端结点，由于其指针均为空，删除后不会影响其他结点，可直接删除；若该结点不是最下层的非终端结点，邻近的指针则指向一棵子树，不可直接删除。此时可做如下处理：将要删除记录用其右（左）边邻近指针指向的子树中关键字最小（大）的记录（该记录必定在最下层的非终端结点中）替换。采取这种方法进行处理，无论要删除的记录所在的结点是否为最下层的非终端结点，都可归结为在最下层的非终端结点中删除记录的情况。

例如，在图 7.25（a）所示的 B-树上删去 45，可以用*f结点中的 50 替代 45，然后在*f 结点中删去 50。因此，下面可以只讨论删除最下层非终端结点中的关键字的情形。有以下 3 种可能。

（1）被删关键字所在结点中的关键字数目不小于 $ [m/2] $，则只需从该结点中删去该关键字 $ K_i $ 和相应指针 $ P_i $，树的其他部分不变。例如，从图 7.25（a）所示 B-树中删去关键字 12，删除后的 B-树如图 7.26（a）所示。

（2）被删关键字所在结点中的关键字数目等于 $ \lceil m/2 \rceil - 1 $，而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于 $ \lceil m/2 \rceil - 1 $，则需将其兄弟结点中的最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。例如，从图 7.26（a）中删去 50，需将其右兄弟结点中的 61 上移至 $ *e $ 结点中，而将 $ *e $ 结点中的 53 移至 $ *f $，从而使 $ *f $ 和 $ *g $ 中关键字数目均不小于 $ \lceil m/2 \rceil - 1 $，而双亲结点中的关键字数目不变，如图 7.26（b）所示。

（3）被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于 $ \lceil m/2 \rceil - 1 $。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针 $ P_i $ 所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字 $ K_i $ 一起，合并到 $ P_i $ 所指兄弟结点中（若没有右兄弟，则合并至左兄弟结点中）。例如，从图 7.26（b）所示 B-树中删去 53，则应删去 $ *f $ 结点，并将 $ *f $ 的剩余信息（指针“空”）和双亲 $ *e $ 结点中的 61 一起合并到右兄弟结点 $ *g $ 中，删除后的树如图 7.26（c）所示。如果因此使双亲结点中关键字数目小于 $ \lceil m/2 \rceil - 1 $，则依次类推做相应处理。例如，在图 7.26（c）的 B-树中删去关键字 37 之后，双亲 $ *b $ 结点中剩余信息（指针 c）应和其双亲 $ *a $ 结点中关键字 45 一起合并至右兄弟结点 $ *e $ 中，删除后的 B-树如图 7.26（d）所示。

在 B-树中删除结点的算法在此不再详述，读者可根据上述讨论自行写出此算法。

7.3.4 B+ 树

B+ 树是一种 B-树的变形树，更适合用于文件索引系统。严格来讲，它已不符合第5章中定义的树了。

1. B+ 树和 B- 树的差异

一棵 m 阶的 B+ 树和 m 阶的 B- 树的差异在于：

（1）有 n 棵子树的结点中含有 n 个关键字；

（2）所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；

（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或

最小）关键字。

例如，图7.27所示为一棵3阶的B+树，通常在B+树上有两个头指针，一个指向根结点，另一个指向关键字最小的叶子结点。因此，可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根结点开始，进行随机查找。

2. B+ 树的查找、插入和删除

在 B+ 树上进行随机查找、插入和删除的过程基本上与 B-树类似。

（1）查找：若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。因此，在 B+ 树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。B+ 树查找的分析类似于 B- 树。

B+ 树不仅能够有效地查找单个关键字，而且更适合查找某个范围内的所有关键字。例如，在 B+ 树上找出范围在 [a, b] 之间的所有关键字值。处理方法如下：通过一次查找找出关键字 a，不管它是否存在，都可以到达可能出现 a 的叶子结点，然后在叶子结点中查找关键字值等于 a 或大于 a 的那些关键字，对于所找到的每个关键字都有一个指针指向相应的记录，这些记录的关键字在所需要的范围。如果在当前结点中没有发现大于 b 的关键字，就可以使用当前叶子结点的最后一个指针找到下一个叶子结点，并继续进行同样的处理，直至在某个叶子结点中找到大于 b 的关键字，才停止查找。

（2）插入：仅在叶子结点上进行插入，当结点中的关键字个数大于 m 时要分裂成两个结点，它们所含关键字的个数分别为 $ \left\lfloor \frac{m+1}{2} \right\rfloor $ 和 $ \left\lceil \frac{m+1}{2} \right\rceil $；并且，它们的双亲结点中应同时包含这两个结点中的最大关键字。

（3）删除：B+树的删除也仅在叶子结点进行，当叶子结点中最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于 $ \left\lceil m/2\right\rceil $时，其和兄弟结点的合并过程亦和B-树类似。

7.4 散列表的查找

7.4.1 散列表的基本概念

前面讨论了基于线性表、树表结构的查找方法，这类查找方法都是以关键字的比较为基础的。

在查找过程中只考虑各元素关键字之间的相对大小，记录在存储结构中的位置和其关键字无直接关系，其查找时间与表的长度有关，特别是当结点个数很多时，查找时要大量地与无效结点的关键字进行比较，致使查找速度很慢。如果能在元素的存储位置和其关键字之间建立某种直接关系，那么在进行查找时，就无需做比较或做很少次的比较，按照这种关系直接由关键字找到相应的记录。这就是散列查找法（Hash Search）的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较。因此，散列查找法又叫杂凑法或散列法。

下面给出散列法中常用的几个术语。

（1）散列函数和散列地址：在记录的存储位置 p 和其关键字 key 之间建立一个确定的对应关系 H，使 p = H(key)，称这个对应关系 H 为散列函数，p 为散列地址。

（2）散列表：一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标。

（3）冲突和同义词：对不同的关键字可能得到同一散列地址，即 $ key_1 \neq key_2 $，而 $ H(key_1) = H(key_2) $，这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称作同义词， $ key_1 $ 与 $ key_2 $ 互称为同义词。

例如，对 C 语言某些关键字集合建立一个散列表，关键字集合为

}}$$ S_{1}=\{main,int,float,while,return,break,switch,case,do\} $$

设定一个长度为26的散列表应该足够，散列表可定义为

$$ char~HT[26][8]; $$

假设散列函数的值取为关键字 key 中第一个字母在字母表 {a, b, …, z} 的序号（序号范围为 0～25），即

$$ H(key)=key[0]-\text{‘a} $$

其中，设 key 的类型是长度为 8 的字符数组，根据此散列函数构造的散列表如表 7.1 所示。

假设关键字集合扩充为：

$$ S_{2}=S_{1}+\{\mathrm{short},\mathrm{default},\mathrm{double},\mathrm{static},\mathrm{for},\mathrm{struct}\} $$

如果散列函数不变，新加入的七个关键字经过计算得到： $ H(\text{short}) = H(\text{static}) = H(\text{struct}) = 18 $， $ H(\text{default}) = H(\text{double}) = 3 $， $ H(\text{for}) = 5 $，而 18、3 和 5 这几个位置均已存放相应的关键字，这就发生了冲突现象，其中，switch、short、static 和 struct 称为同义词；float 和 for 称为同义词，do、default 和 double 称为同义词。

集合 $ S_{2} $ 中的关键字仅有 15 个，仔细分析这 15 个关键字的特性，应该不难构造一个散列函数避免冲突。但在实际应用中，理想化的、不产生冲突的散列函数极少存在，这是因为通常散列表中关键字的取值集合远远大于表空间的地址集。例如，高级语言的编译程序要对源程序中的标识符建立一张符号表进行管理，多数都采取散列表。在设定散列函数时，考虑的查找关键字集合应包含所有可能产生的关键字，不同的源程序中使用的标识符一般也不相同，如果此语言规定标识符为长度不超过 8 的、字母开头的字母数字串，字母区分大小写，则标识符取值集合的大小为：

$$ C_{52}^{1}\times C_{62}^{7}\times7!=1.09\times10^{12} $$

而一个源程序中出现的标识符是有限的，所以编译程序将散列表的长度设为1000足矣。于是，要将多达 $ 10^{12} $个可能的标识符映射到有限的地址上，难免产生冲突。通常，散列函数是一个多对一的映射，所以冲突是不可避免的，只能通过选择一个“好”的散列函数使得在一定程度上减少冲突。而一旦发生冲突，就必须采取相应措施及时予以解决。

综上所述，散列查找法主要研究以下两方面的问题：

（1）如何构造散列函数：

（2）如何处理冲突。

7.4.2 散列函数的构造方法

构造散列函数的方法很多，一般来说，应根据具体问题选用不同的散列函数，通常要考虑以下因素：

（1）散列表的长度；

（2）关键字的长度；

（3）关键字的分布情况；

（4）计算散列函数所需的时间；

（5）记录的查找频率。

构造一个“好”的散列函数应遵循以下两条原则：

（1）函数计算要简单，每一关键字只能有一个散列地址与之对应；

（2）函数的值域需在表长的范围内，计算出的散列地址的分布应均匀，尽可能减少冲突。下面介绍构造散列函数的几种常用方法。

1. 数字分析法

如果事先知道关键字集合，且每个关键字的位数比散列表的地址码位数多，每个关键字由n位数组成，如 $ k_1k_2\cdots k_n $，则可以从关键字中提取数字分布比较均匀的若干位作为散列地址。

例如，有80个记录，其关键字为8位十进制数。假设散列表的表长为100，则可取两位十进制数组成散列地址，选取的原则是分析这80个关键字，使得到的散列地址尽量避免产生冲突。假设这80个关键字中的一部分如下所列：

对关键字全体的分析中可以发现：第 $ ^{①} $、 $ ^{②} $位都是“8 1”，第 $ ^{③} $位只可能取3或4，第 $ ^{⑧} $位可能取2、5或7，因此这4位都不可取。由于中间的4位可看成是近乎随机的，因此可取其中任

意两位，或取其中两位与另外两位的叠加求和后舍去进位作为散列地址。

数字分析法的适用情况：事先必须明确知道所有的关键字每一位上各种数字的分布情况。

在实际应用中，例如，同一出版社出版的所有图书，其 ISBN 号的前几位都是相同的，因此，若数据表只包含同一出版社的图书，构造散列函数时可以利用这种数字分析排除 ISBN 号的前几位数字。

2. 平方取中法

通常在选定散列函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，如果取关键字平方后的中间几位或其组合作为散列地址，则使随机分布的关键字得到的散列地址也是随机的，具体所取的位数由表长决定。平方取中法是一种较常用的构造散列函数的方法。

例如，为源程序中的标识符建立一个散列表，假设标识符为字母开头的字母数字串。假设人为约定每个标识的内部编码规则如下：把字母在字母表中的位置序号作为该字母的内部编码，如I的内部编码为09，D的内部编码为04，A的内部编码为01。数字直接用其自身作为内部编码，如1的内部编码为01，2的内部编码为02。根据以上编码规则，可知“IDA1”的内部编码为09040101，同理可以得到“IDB2”、“XID3”和“YID4”的内部编码。之后分别对内部编码进行平方运算，再取出第7位到第9位作为其相应标识符的散列地址，如表7.2所示。

平方取中法的适用情况：不能事先了解关键字的所有情况，或难于直接从关键字中找到取值较分散的几位。

3. 折叠法

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址，这种方法称为折叠法。根据数位叠加的方式，可以把折叠法分为移位叠加和边界叠加两种。移位叠加是将分割后每一部分的最低位对齐，然后相加；边界叠加是将两个相邻的部分沿边界来回折叠，然后对齐相加。

例如，当散列表长为1000时，关键字key=45387765213，从左到右按3位数一段分割，可以得到4个部分：453、877、652、13。分别采用移位叠加和边界叠加，求得散列地址为995和914，如图7.28所示。

$$ \begin{array}{r}453\\{\begin{array}{r}877\\652+13\end{array}} \\\hline[1]995\\H(key)=995 \end{array} $$

$$ \begin{array}{r}453\\778\\652\\+ \quad 31\\ \hline [1]914 \\ H(key)=914 \end{array} $$

折叠法的适用情况：适合于散列地址的位数较少，而关键字的位数较多，且难于直接从关键字中找到取值较分散的几位。

4. 除留余数法

假设散列表表长为 m，选择一个不大于 m 的数 p，用 p 去除关键字，除后所得余数为散列地址，即

$$ H(key)=key\%p $$

这个方法的关键是选取适当的 p，一般情况下，可以选 p 为小于表长的最大质数。例如，表长 m=100，可取 p=97。

除留余数法计算简单，适用范围非常广，是最常用的构造散列函数的方法。它不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模，这样能够保证散列地址一定落在散列表的地址空间中。

7.4.3 处理冲突的方法

选择一个“好”的散列函数可以在一定程度上减少冲突，但在实际应用中，很难完全避免发生冲突，所以选择一个有效的处理冲突的方法是散列法的另一个关键问题。创建散列表和查找散列表都会遇到冲突，两种情况下处理冲突的方法应该一致。下面以创建散列表为例，来说明处理冲突的方法。

处理冲突的方法与散列表本身的组织形式有关。按组织形式的不同，通常分两大类：开放地址法和链地址法。

1. 开放地址法

开放地址法的基本思想是：把记录都存储在散列表数组中，当某一记录关键字 key 的初始散列地址 $ H_{0}=H(key) $ 发生冲突时，以 $ H_{0} $ 为基础，采取合适方法计算得到另一个地址 $ H_{1} $，如果 $ H_{1} $ 仍然发生冲突，以 $ H_{1} $ 为基础再求下一个地址 $ H_{2} $，若 $ H_{2} $ 仍然冲突，再求得 $ H_{3} $。依次类推，直至 $ H_{k} $ 不发生冲突为止，则 $ H_{k} $ 为该记录在表中的散列地址。

这种方法在寻找“下一个”空的散列地址时，原来的数组空间对所有的元素都是开放的，所以称为开放地址法。通常把寻找“下一个”空位的过程称为探测，上述方法可用如下公式表示：

$$ H_{i}=(H(key)+d_{i})\%m\qquad i=1,2,\cdots,k(k\leqslant m-1) $$

其中， $ H(key) $为散列函数，m为散列表表长， $ d_{i} $为增量序列。根据 $ d_{i} $取值的不同，可以分为以下3种探测方法。

（1） 线性探测法

$$ d_{i}=1,2,3,\cdots,m-1 $$

这种探测方法可以将散列表假想成一个循环表，发生冲突时，从冲突地址的下一单元顺序寻找空单元，如果到最后一个位置也没找到空单元，则回到表头开始继续查找，直到找到一个空位，就把此元素放入此空位中。如果找不到空位，则说明散列表已满，需要进行溢出处理。

（2） 二次探测法

$$ d_{i}=1^{2},-1^{2},2^{2},-2^{2},3^{2},\cdots,+k^{2},-k^{2}(k\leqslant m/2) $$

（3） 伪随机探测法

$ d_{i} $ = 伪随机数序列

例如，散列表的长度为 11，散列函数 $ H(key) = key\%11 $，假设表中已填有关键字分别为 17、60、29 的记录，如图 7.29（a）所示。现有第四个记录，其关键字为 38，由散列函数得到散列地址为 5，产生冲突。

若用线性探测法处理时，得到下一个地址6，仍冲突；再求下一个地址7，仍冲突；直到散列地址为8的位置为“空”时为止，处理冲突的过程结束，38填入散列表中序号为8的位置，如图7.29（b）所示。

若用二次探测法，散列地址 5 冲突后，得到下一个地址 6，仍冲突；再求得下一个地址 4，无冲突，38 填入序号为 4 的位置，如图 7.29（c）所示。

若用伪随机探测法，假设产生的伪随机数为9，则计算下一个散列地址为 $ (5+9)\%11=3 $，所以38填入序号为3的位置，如图7.29（d）所示。

从上述线性探测法处理的过程中可以看到一个现象：当表中 i, i+1, i+2 位置上已填有记录时，下一个散列地址为 i、i+1、i+2 和 i+3 的记录都将填入 i+3 的位置，这种在处理冲突过程中发生的两个第一个散列地址不同的记录争夺同一个后继散列地址的现象称作“二次聚集”（或称作“堆积”），即在处理同义词的冲突过程中又添加了非同义词的冲突。

可以看出，上述三种处理方法各有优缺点。线性探测法的优点是：只要散列表未填满，总能找到一个不发生冲突的地址。缺点是：会产生“二次聚集”现象。而二次探测法和伪随机探测法的优点是：可以避免“二次聚集”现象。缺点也很显然：不能保证一定找到不发生冲突的地址。

2. 链地址法

链地址法的基本思想是：把具有相同散列地址的记录放在同一个单链表中，称为同义词链表。有 $ m $ 个散列地址就有 $ m $ 个单链表，同时用数组 $ HT[0\cdots m-1] $ 存放各个链表的头指针，凡是散列地址为 $ i $ 的记录都以结点方式插入到以 $ HT[i] $ 为头结点的单链表中。

【例 7.2】已知一组关键字为（19，14，23，1，68，20，84，27，55，11，10，79），设散列函数 $ H(key) = key \% 13 $，用链地址法处理冲突，试构造这组关键字的散列表。

由散列函数 $ H(key) = key \% 13 $ 得知散列地址的值域为 0～12，故整个散列表有 13 个单链表组成，用数组 $ HT[0..12] $ 存放各个链表的头指针。如散列地址均为 1 的同义词 14、1、27、79 构

成一个单链表，链表的头指针保存在 HT[1]中，同理，可以构造其他几个单链表，整个散列表的结构如图 7.30 所示。

这种构造方法在具体实现时，依次计算各个关键字的散列地址，然后根据散列地址将关键字插入到相应的链表中。

7.4.4 散列表的查找

在散列表上进行查找的过程和创建散列表的过程基本一致。算法 7.10 描述了开放地址法（线性探测法）处理冲突的散列表的查找过程。

下面以开放地址法为例，给出散列表的存储表示。

// -- -- -- 开放地址法散列表的存储表示

#define m 20

typedef struct{

    KeyType key;
    InfoType otherinfo;
} HashTable[m];

// 散列表的表长
// 关键字项
// 其他数据项

算法 7.10 散列表的查找

【算法步骤】

① 给定待查找的关键字 key，根据造表时设定的散列函数计算 $ H_{0}=H(key) $。

② 若单元 $ H_{0} $为空，则所查元素不存在。

③ 若单元 $ H_{0} $中元素的关键字为 key，则查找成功。

④ 否则重复下述解决冲突的过程：

按处理冲突的方法，计算下一个散列地址 $ H_{i} $;

若单元 $ H_{i} $为空，则所查元素不存在；

若单元 $ H_{i} $中元素的关键字为 key，则查找成功。

【算法描述】

#define NULLKEY 0 //单元为空的标记

int SearchHash(HashTable HT, KeyType key)

HO=H(key); //根据散列函数H（key）计算散列地址

if(HT[HO].key==NULLKEY) return -1; //若单元HO为空，则所查元素不存在
else if(HT[HO].key==key) return HO; //若单元HO中元素的关键字为key，则查找成功
else
{
    for(i=1;i<m;++i)
    {
        Hi=(HO+i) %m; //按照线性探测法计算下一个散列地址Hi
        if(HT[Hi].key==NULLKEY) return -1; //若单元Hi为空，则所查元素不存在
        else if(HT[Hi].key==key) return Hi; //若单元Hi中元素的关键字为key，则查找成功
    }
    return -1;
}

【算法分析】

从散列表的查找过程可见：

（1）虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需以平均查找长度作为衡量散列表查找效率的量度。

（2）查找过程中需和给定值进行比较的关键字的个数取决于三个因素：散列函数、处理冲突的方法和散列表的装填因子。

散列表的装填因子 $ \alpha $定义为

$$ \alpha=\frac{ 表中填入的记录数 }{ 散列表的长度 } $$

$ \alpha $ 标志散列表的装满程度。直观地看， $ \alpha $ 越小，发生冲突的可能性就越小；反之， $ \alpha $ 越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。

（3）散列函数的“好坏”首先影响出现冲突的频繁程度。但一般情况下认为：凡是“均匀的”散列函数，对同一组随机的关键字，产生冲突的可能性相同，假如所设定的散列函数是“均匀”的，则影响平均查找长度的因素只有两个——处理冲突的方法和装填因子 $ \alpha $。

表 7.3 给出了在等概率情况下，采用几种不同方法处理冲突时，得到的散列表查找成功和查找失败时的平均查找长度，证明过程从略。

（4）从表7.3可以看出，散列表的平均查找长度是 $ \alpha $的函数，而不是记录个数n的函数。由

此，在设计散列表时，不管 n 多大，总可以选择合适的 $ \alpha $ 以便将平均查找长度限定在一个范围内。对于一个具体的散列表，通常采用直接计算的方法求其平均查找长度，下面通过具体示例说明。

【例7.3】对于例7.2中的关键字(19,14,23,1,68,20,84,27,55,11,10,79)，仍设散列函数为 $ H(key)=key\%13 $，用线性探测法处理冲突。设表长为16，试构造这组关键字的散列表，并计算查找成功和查找失败时的平均查找长度。

依次计算各个关键字的散列地址，如果没有冲突，将关键字直接存放在相应的散列地址所对应的单元中；否则，用线性探测法处理冲突，直到找到相应的存储单元中。

如对于前三个关键字进行计算， $ H(19)=6 $， $ H(14)=1 $， $ H(23)=10 $，所得散列地址均没有冲突，直接填入所在单元。

而对于第四个关键字, $ H(1)=1 $, 发生冲突, 根据线性探测法, 求得下一个地址 $ (1+1)\%16=2 $, 没有冲突, 所以1填入序号为2的单元。

同理，可依次填入其他关键字。对于最后一个关键字79， $ H(79)=1 $，发生冲突，用线性探测法处理冲突，后面的地址2～8均有冲突，最终79填入9号单元。

最终构造结果如表 7.4 所示，表中最后一行的数字表示放置该关键字时所进行的关键字比较次数。

要查找一个关键字 key，根据算法 7.10，首先用散列函数计算 $ H_{0}=H(key) $，然后进行比较，比较的次数和创建散列表时放置此关键字的比较次数是相同的。

例如，查找 19 时，计算散列函数 $ H(19) = 6 $， $ HT[6] $.key 非空且值为 19，查找成功，关键字比较次数为 1 次。

同样，当查找关键字14、68、20、23、11时，均需比较1次即查找成功。

当查找关键字 1 时，计算散列函数 $ H(1) = 1 $， $ HT[1].key $ 非空且值为 $ 14 \neq 1 $，用线性探测法处理冲突，计算下一个地址为 $ (1 + 1)\%16 = 2 $， $ HT[2].key $ 非空且值为 1，查找成功，关键字比较次数为 2 次。

当查找关键字 55，84，10 时，需比较 3 次；当查找 27 时，需比较 4 次；而查找 79 时，需要比较 9 次才能查找成功。

在记录的查找概率相等的前提下，这组关键字采用线性探测法处理散列表冲突时，查找成功时的平均查找长度为

$$ ASL_{\mathrm{succ}}=\frac{1}{12}(1\cdot6+2+3\cdot3+4+9)=2.5 $$

查找失败时有两种情况：

（1）单元为空；

（2）按处理冲突的方法探测一遍后仍未找到。假设散列函数的取值个数为 r，则 0 到 r-1 相当于 r 个查找失败的入口，从每个入口进入后，直到确定查找失败为止，其关键字的比较次数就是与该入口对应的查找失败的查找长度。

在例7.3中，散列函数的取值个数为13，即总共有13个查找失败的入口（0到12），对每个

入口依次进行计算。

假设待查我的关键字不在表中，若计算散列函数 $ H(key) = 0 $， $ HT[0].key $ 为空，比较 1 次即确定查找失败。若 $ H(key) = 1 $， $ HT[1].key $ 非空，则依次向后比较，直到 $ HT[13].key $ 为空，总共比较 13 次才能确定查找失败。类似地，对 $ H(key) = 2, 3, \cdots, 12 $ 进行分析，可得查找失败的平均查找长度为

$$ ASL_{unsucc}=\frac{1}{13}(1+13+12+11+10+9+8+7+6+5+4+3+2)=7 $$

在例7.2中，采用链地址法处理冲突时，对于图7.30中所示的每个单链表中的第1个结点的关键字（如14、68、19、20、23、11），查找成功时只需比较1次，而对于第2个结点的关键字（如1、55、84、10），查找成功时需比较2次，第3个结点的关键字27需比较3次，第4个结点的关键字79则需比较4次才能查找成功。这时，查找成功时的平均查找长度为

$$ ASL_{succ}=\frac{1}{12}(1\cdot6+2\cdot4+3+4)=1.75 $$

采用链地址法处理冲突时，待查的关键字不在表中，若计算散列函数 $ H(key) = 0 $， $ HT[0] $ 的指针域为空，比较 1 次即确定查找失败。若 $ H(key) = 1 $， $ HT[1] $ 所指的单链表包括 4 个结点，所以需要比较 5 次才能确定失败。类似地，对 $ H(key) = 2, 3, \cdots, 12 $ 进行分析，可得查找失败的平均查找长度为

$$ ASL_{unsucc}=\frac{1}{13}(1+5+1+3+1+1+3+2+1+1+3+2+1)=1.92 $$

容易看出，线性探测法在处理冲突的过程中易产生记录的二次聚集，使得散列地址不相同的记录又产生新的冲突；而链地址法处理冲突不会发生类似情况，因为散列地址不同的记录在不同的链表中，所以链地址法的平均查找长度小于开放地址法。另外，由于链地址法的结点空间是动态申请的，无需事先确定表的容量，因此更适用于表长不确定的情况。同时，易于实现插入和删除操作。

通过上面的示例，可以看出，在查找概率相等的前提下，直接计算查找成功的平均查找长度可以采用以下公式

$$ ASL_{succ}=\frac{1}{n}\sum_{i=1}^{n}C_{i} $$

其中，n 为散列表中记录的个数， $ C_{i} $ 为成功查找第 i 个记录所需的比较次数。

而直接计算查找失败的平均查找长度可以采用以下公式

$$ ASL_{unsucc}=\frac{1}{r}\sum_{i=1}^{r}C_{i} $$

其中，r 为散列函数取值的个数， $ C_{i} $ 为散列函数取值为 i 时查找失败的比较次数。

7.5 小结

查找是数据处理中经常使用的一种操作。本章主要介绍了对查找表的查找，查找表实际上仅

仅是一个集合，为了提高查找效率，将查找表组织成不同的数据结构，主要包括3种不同结构的查找表：线性表、树表和散列表。

（1）线性表的查找。主要包括顺序查找、折半查找和分块查找，3者之间的比较详见表7.5。

（2）树表的查找。树表的结构主要包括二叉排序树、平衡二叉树、B-树和B+树。

①二叉排序树的查找过程与折半查找过程类似，二者之间的比较详见表7.6。

②二叉排序树在形态均匀时性能最好，而形态为单支树时其查找性能则退化为与顺序查找相同，因此，二叉排序树最好是一棵平衡二叉树。平衡二叉树的平衡调整方法就是确保二叉排序树在任何情况下的深度均为 $ O(\log_2 n) $，平衡调整方法分为4种：LL型、RR型、LR型和RL型。

③ B-树是一种平衡的多叉查找树，是一种在外存文件系统中常用的动态索引技术。在 B-树上进行查找的过程和二叉排序树类似，是一个顺指针查找结点和在结点内的关键字中查找交叉进行的过程。为了确保 B-树的定义，在 B-树中插入一个关键字，可能产生结点的“分裂”，而删除一个关键字，可能产生结点的“合并”。

④ B+ 树是一种 B-树的变型树，更适合做文件系统的索引。在 B+ 树上进行随机查找、插入和删除的过程基本上与 B-树类似，但具体实现细节又有所区别。

（3）散列表的查找。散列表也属线性结构，但它和线性表的查找有着本质的区别。它不是以关键字比较为基础进行查找的，而是通过一种散列函数把记录的关键字和它在表中的位置建立起对应关系，并在存储记录发生冲突时采用专门的处理冲突的方法。这种方式构造的散列表，不仅平均查找长度和记录总数无关，而且可以通过调节装填因子，把平均查找长度控制在所需的范围内。

散列查找法主要研究两方面的问题：如何构造散列函数，以及如何处理冲突。

① 构造散列函数的方法很多，除留余数法是最常用的构造散列函数的方法。它不仅可以对关

键字直接取模，也可在折叠、平方取中等运算之后取模。

② 处理冲突的方法通常分为两大类：开放地址法和链地址法，二者之间的差别类似于顺序表和单链表的差别，二者的比较详见表7.7。

学习完本章后，要求掌握顺序查找、折半查找和分块查找的方法，掌握描述折半查找过程的判定树的构造方法。掌握二叉排序树的构造和查找方法，平衡二叉树的4种平衡调整方法。理解B-和B+树的特点、基本操作和二者的区别。熟练掌握散列表的构造方法。明确各种不同查找方法之间的区别和各自的适用情况，能够按定义计算各种查找方法在等概率情况下查找成功的平均查找长度。

习题

1. 选择题

（1）对 n 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

A. $ (n-1)/2 $ B. n/2 C. $ (n+1)/2 $ D. n

（2）适用于折半查找的表的存储方式，以及元素排列要求为（）。

A. 链接方式存储，元素无序

B. 链接方式存储，元素有序

C. 顺序方式存储，元素无序

D. 顺序方式存储，元素有序

（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( )查找法。

A. 顺序查找

B. 折半查找

C. 分块查找

D. 哈希查找

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素 58，则它将依次与表中（ ）比较大小，查找结果是失败。

A. 20，70，30，50

B. 30，88，70，50

C. 20，50

D. 30，88，50

（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（___）次关键字。

A. 3 B. 4 C. 5 D. 6

（6）折半查找与二叉排序树的时间性能（）。

A. 相同

B. 完全不同

C. 有时不相同

D. 数量级都是 $ O(\log_{2}n) $

（7）分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。

A. （100, 80, 90, 60, 120, 110, 130） B. （100, 120, 110, 130, 80, 60, 90）

C. （100, 60, 80, 90, 120, 110, 130） D. （100, 80, 60, 90, 120, 130, 110）

（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为 0，右孩子的平衡因子为 1，则应作（）型调整以使其平衡。

A. LL

B. LR

C. RL

D. RR

（9）下列关于 m 阶 B-树的说法错误的是（）。

A. 根结点至多有 m 棵子树

B. 所有叶子都在同一层次上

C. 非叶结点至少有 $ \frac{m}{2} $（m 为偶数）或 $ \frac{m}{2} + 1 $（m 为奇数）棵子树

D. 根结点中的数据是有序的

（10）下面关于 B-和 B+树的叙述中，不正确的是（）。

A. B-树和 B+树都是平衡的多叉树

B. B-树和 B+树都可用于文件的索引结构

C. B-树和 B+树都能有效地支持顺序检索

D. B-树和 B+树都能有效地支持随机检索

（11）m 阶 B-树是一棵（）。

A. m 叉排序树

B. m 叉平衡排序树

C. m-1 叉平衡排序树

D. m+1 叉平衡排序树

（12）下面关于散列查找的说法，正确的是（）。

A. 散列函数构造的越复杂越好，因为这样随机性好，冲突小

B. 除留余数法是所有散列函数中最好的

C. 不存在特别好与坏的散列函数，要视情况而定

D. 散列表的平均查找长度有时也和记录总数有关

（13）下面关于散列查找的说法，不正确的是（）。

A. 采用链地址法处理冲突时，查找任何一个元素的时间都相同

B．采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的

C. 用链地址法处理冲突，不会引起二次聚集现象

D. 用链地址法处理冲突，适合表长不确定的情况

（14）设散列表长为14，散列函数是 $ H(key)=key\%11 $，表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。

A. 3 B. 5 C. 8 D. 9

（15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字（）。

A. 不一定都是同义词

B. 一定都是同义词

C. 一定都不是同义词

D. 都相同

2. 应用题

（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题。

① 画出描述折半查找过程的判定树。

② 若查找元素 54，需依次与哪些元素比较？

③ 若查找元素 90，需依次与哪些元素比较？

④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。

（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。

（3）已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）。

① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

② 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

③按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

（4）对图7.31所示的3阶B-树，依次执行下列操作，画出各步操作的结果。 $ ^{①} $插入90

② 插入25

③ 插入45

④ 删除60

（5）设散列表的地址范围为 0～17，散列函数为：

$ H(key) = key\%16 $。用线性探测法处理冲突，输入关键字序列：(10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49)。构造散列表，试回答下列问题：

① 画出散列表的示意图。

② 若查找关键字 63，需要依次与哪些关键字进行比较？

③ 若查找关键字 60，需要依次与哪些关键字进行比较？

④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

（6）设有一组关键字（9，1，23，14，55，20，84，27），采用散列函数： $ H(key)=key\%7 $，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造散列表，并计算查找成功的平均查找长度。

（7）设散列函数 $ H(K) = 3K\% $ 11，散列地址空间为 $ 0 \sim 10 $，对关键字序列（32, 13, 49, 24, 38, 21, 4, 12），按下述两种解决冲突的方法构造散列表，并分别求出等概率下查找成功时和查找失败时的平均查找长度 $ ASL_{succ} $ 和 $ ASL_{unsucc} $。

① 线性探测法。

② 链地址法。

3. 算法设计题

（1）试写出折半查找的递归算法。

（2）试写一个判别给定二叉树是否为二叉排序树的算法。

（3）已知二叉排序树采用二叉链表存储结构，根结点的指针为 T，链结点的结构为（lchild，

data, rchild)，其中 lchild、rchild 分别指向该结点左、右孩子的指针，data 域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值 $ \geq x $ 的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。

（4）已知二叉树 T 的结点形式为 (llink, data, count, rlink)，在树中查找值为 X 的结点，若找到，则记数（count）加 1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

（5）假设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一个算法，求平衡二叉树的高度。

（6）分别写出在散列表中插入和删除关键字为 K 的一个记录的算法，设散列函数为 H，解决冲突的方法为链地址法。