数据结构进阶 - 第八章 查找算法

第8章 查找算法

目录

• 查找的基本概念
• 基于线性表的查找法
  • 顺序查找法
  • 折半查找法
  • 分块查找法
• 基于树的查找法
  • 二叉排序树
  • 平衡二叉排序树
  • 红黑树
  • B树
  • B+树
• 计算式查找法——哈希查找

查找的基本概念

基本定义

查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定关键字相同的数据元素，并返回该数据元素在列表中的位置。

在查找算法中常用到三类参量，即：

1. 查找对象K（我什么）
2. 查找范围L（在哪儿）
3. 查找的结果（K在L中的位置）

其中，为输入参量，在查找中不可缺少。

为输出参量，可由函数返回值表示。

查找性能指标

查找长度：为确定数据元素在列表中的位置，需和给定进行关键字比较，比较的次数称为查找长度。

平均查找长度（ASL）

平均查找长度（ASL）：列表中的每一个元素Ri均有可能被查找，假设每个元素Ri被查找的概率为pi，则整个列表中元素的查找性能用平均查找长度（ASL）来衡量。

对于长度为n的列表，查找成功时的平均查找长度ASL为：

$$ASL=P_1{C}_1+P_2{C}_2+...+P_n{C}_n=\sum _{i=1}^n{P}_i{C}_i$$

其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。

查找成功时ASL与查找失败时ASL

查找成功时ASL：确定待查找的元素X在列表中，而进行的关键字比较次数。

查找失败时ASL：确定待查找的元素X不在列表中，而进行的关键字比较次数。

对于长度为n的列表，查找不成功时的平均查找长度ASL为：

$$ASL=P_1{C}_1+P_2{C}_2+...+P_n{C}_n=\sum _{i=1}^n{P}_i{C}_i$$

其中Pi为查找不成功的概率，Ci为在列表中找不到数据元素时，进行过的关键字比较次数。

若每种查找不成功情况的概率pi相等，则查找不成功的ASL：

$$ASL=\frac{1}{n}\sum _{i=1}^n{C}_i$$

基于线性表的查找法

比较式查找法 → 基于线性表的查找法 → 列表L（集合）采用线性表存储表示

顺序查找法

【顺序查找法】：

1. 将待查找列表L（集合）采用线性表存储表示；
2. 用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。

数据结构定义

#define LIST_SIZE 20

typedef struct {
    KeyType key;
    OtherType other_data;
} RecordType;

typedef struct {
    RecordType r[LIST_SIZE+1]; /* r[0]为工作单元 */
    int length;
} RecordList;

算法实现

int SeqSearch(RecordList L, KeyType k)
{
    /* 在顺序表中顺序查找其关键字等于k的元素，若找到，则函数值为该
       元素在表中的位置，否则为0 */
    
    L.r[0].key=k; i=L.length;
    while (L.r[i].key!=k) i--;
    return (i);
}

性能分析

查找成功时ASL

假设列表长度为n，那么查找第i个数据元素时需要进行n+1-i次比较，即Ci=n+1-i。如果设查找每个数据元素的概率相等，即pi=1/n，则顺序查找算法的平均查找长度为：

$$AS{L}_{succ}=\sum _{i=1}^n{P}_i{C}_i=\frac{1}{n}\sum _{i=1}^n{C}_i=\frac{1}{n}\sum _{i=1}^n(n+1-i)=\frac{n+1}{2}$$

查找失败时ASL

假设列表长度为n，只要待查找的关键字不是列表中的n个关键字值之一，均为查找不成功。查找关键字值外的元素不成功时从最后一个元素开始依次与关键字值比较，直到比较到监视哨L.r[0].key才相等，则需要进行n+1次比较。所以查找失败的ASL=n+1。

顺序查找的优化（对有序表）

查找表中元素有序存储（递增/递减）

查找目标：21

29-21查找失败，由于29>21，可以提前结束查找。

折半查找法

**【折半查找法】**前提：

1. 待查找列表L（集合）采用线性表顺序存储表示；
2. 列表中的数据元素按关键字值递增（递减）有序存放。

【基本过程】：将表中间位置记录的L.r[mid].key与待查找关键字比较：

• 如果两者相等，则查找成功；
• 如果中间位置记录的关键字大于查找关键字，则进一步查找前（左）半子表；
• 否则进一步查找后（右）半子表，重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

算法示例

用折半查找法查找12的过程：

第1步： low=1, mid=6, high=11

• L.r[mid].key=43 > 12，high=mid-1

第2步： low=1, mid=3, high=5

• L.r[mid].key=19 > 12，high=mid-1

第3步： low=1, mid=2, high=2

• L.r[mid].key=13 > 12，high=mid-1

第4步： low=1, high=1

• L.r[mid].key=7 < 12，low=mid+1

此时low>high查找失败

折半查找的递归算法（分治）

int BinSearch(RecordList L, KeyType k, int low, int high) {
    mid=(low+high)/2;
    
    if(low>high) return 0;
    
    if(L.r[mid].key==k) return mid;
    else if(k < L.r[mid].key)
        return BinSearch(L,k,low,high-1);
    else
        return BinSearch(L,k,low+1,high);
}

折半查找的改进——插值查找

插值查找位置计算

$$mid=low+\frac{key-a[low]}{a[high]-a[low]}\times (high-low)$$

插值查找适合表长较大、关键字分布均匀的查找表。

性能分析

查找成功时ASL

折半查找过程可用一判定树描述。判定树结构：树中每一结点表示表中一记录，结点值记录在表中的位置。

折半查找判定树与待查找元素在列表中的位置无关，与列表中元素关键字值无关。

假设每个元素的查找概率相等，则它们的平均查找长度分别是：

$$AS{L}_{succ}=\frac{1}{11}(1\times 1+2\times 2+3\times 4+4\times 4)=\frac{33}{11}$$

查找失败时ASL

$$AS{L}_{unsucc}=\frac{1}{12}(3\times 4+4\times 8)=\frac{44}{12}$$

由此可见，在二叉排序树上进行查找的平均查找长度和二叉排序树的形态有关。

重要结论

折半查找成功时的平均查找长度为：

$$AS{L}_{bin}=\frac{1}{n}\sum _{j=1}^{n}j\times 2^{j-1}=\frac{n+1}{n}{\log }_2(n+1)-1\approx {\log }_{2}n+1$$

优点：比较次数少，查找速度快，平均性能好。
缺点：要求待查的表为有序表，且插入、删除困难。

分块查找法

分块查找法要求将表组织成以下结构：

首先将列表分成若干块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，但块与块之间有序。

构造一个索引表。其中每个索引对应一个块并记录每块的起始地址，和每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。

基本过程

分块查找的基本过程为：

1. 首先，将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块，具体的可用顺序查找法或折半查找法进行；
2. 进一步用顺序查找法，在相应块内查找关键字为K的元素。

平均查找长度

分块查找的平均查找长度由两部分组成：即查找索引表时的平均查找长度为Lb，以及在相应块内进行顺序查找的平均查找长度Lw。

$$AS{L}_{bs}=L_b+L_w$$

假设将长度为n的表分成b块，且每块含有s个元素，则b=n/s。又假定表中每个元素的查找概率相等，每个索引项的查找概率为1/b，其中每个元素的查找概率为1/s。若用顺序查找法确定待查元素所在的块，则有：

$$L_b=\frac{1}{b}\sum _{j=1}^{b}j=\frac{b+1}{2}$$

$$L_w=\frac{1}{s}\sum _{i=1}^{s}i=\frac{s+1}{2}$$

将b=n/s代入，得：

$$AS{L}_{bs}=\frac{b+s}{2}+1\ge \frac{n}{s}\cdot s+1=\sqrt{n}+1$$

重要结论

当 $\frac{n}{s}=s$ 时取最小值。所以，分块的大小为 $\sqrt{n}$ 时，分块查找性能最好。

基于树的查找法

基于树的查找法是指将查找的列表（数据元素集合）看成是树形结构，按照树的存储结构来存储列表元素集合并在树存储上实现查找的方法。主要包括：

• 二叉排序树（BST）
• 平衡二叉排序树（AVL）
• 红黑树（RBT）
• B树B+树

二叉排序树

定义

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

1. 若它的左子树非空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树非空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉排序树。

数据结构

使用二叉链表作为存储结构，其结点结构说明如下：

typedef struct node
{
    KeyType key; /* 关键字的值 */
    struct node *lchild, *rchild; /* 左右指针 */
} BSTNode, *BSTree;

插入方法

1. 若二叉排序树是空树，则key成为二叉排序树的根；
2. 若二叉排序树非空，则将key与二叉排序树的根进行比较：
   • 如果key的值等于根结点的值，则停止插入；
   • 如果key的值小于根结点的值，则将key插入左子树；
   • 如果key的值大于根结点的值，则将key插入右子树。

void InsertBST(BSTree *bst, KeyType key) {
    if (*bst==NULL) {
        s=(BSTree)malloc(sizeof(BSTNode));
        s->key=key;
        s->lchild=NULL; s->rchild=NULL;
        *bst=s;
    }
    else if (key < (*bst)->key)
        InsertBST(&((*bst)->lchild), key);
    else if (key > (*bst)->key)
        InsertBST(&((*bst)->rchild), key);
}

建立算法

void CreateBST(BSTree *bst)
{
    /* 从键盘输入元素的值，创建相应的二叉排序树 */
    KeyType key;
    *bst=NULL;
    scanf("%d", &key);
    while (key!=ENDKEY) {
        InsertBST(bst, key);
        scanf("%d", &key);
    }
}

查找方法

根据二叉排序树的特点，首先将查找关键字与根结点关键字进行比较，如果：

1. k=t: 则返回根结点地址；
2. k<t: 则进一步查找左子树；
3. k>t: 则进一步查找右子树。

显然，这是一个递归过程。可用递归算法实现：

递归算法

BSTree SearchBST(BSTree bst, KeyType key)
{
    /* 在根指针bst所指二叉排序树中，递归查找某关键字等于key的结点，
       若查找成功，返回指向该元素结点指针，否则返回空指针。*/
    
    if (!bst) return NULL;
    else if (bst->key==key) return bst; /* 查找成功 */
    else if (key < bst->key)
        return SearchBST(bst->lchild, key); /* 在左子树中继续查找 */
    else
        return SearchBST(bst->rchild, key); /* 在右子树中继续查找 */
}

非递归算法

BSTree SearchBST(BSTree bst, KeyType key)
{
    /* 在根指针bst所指二叉排序树上，查找关键字等于key的结点，若查找
       成功，返回指向该元素结点指针，否则返回空指针。*/
    
    BSTree q; q=bst;
    while(q) {
        if (q->key==key) return q; /* 查找成功 */
        if (key < q->key) q=q->lchild; /* 在左子树中查找 */
        else q=q->rchild; /* 在右子树中查找 */
    }
    return NULL; /* 查找失败 */
}

性能分析

对于含有同样关键字的一组结点，结点插入的先后次序不同，所构成的二叉排序树的形态各异，从而影响着二叉排序树的平均查找长度。

假设每个元素的查找概率相等，则它们的平均查找长度分别是：

成功情况：
KaTeX parse error: Unexpected end of input in a macro argument, expected '}' at end of input: …+3+3)/6 = 14/6}

不成功情况：
KaTeX parse error: Unexpected end of input in a macro argument, expected '}' at end of input: …+4+4)/6 = 25/6}

由此可见，在二叉排序树上进行查找的平均查找长度和二叉排序树的形态有关。

若考虑各个结点被访问到的概率相等，则有I个结点的二叉排序树，其查找性能为O(log n)。

平衡二叉排序树

**【平衡二叉排序树】**又称为AVL树。一棵平衡二叉排序树或者是空树，或者是具有下列性质的二叉排序树：

1. 左子树与右子树高度之差的绝对值小于等于1；
2. 左子树和右子树也是平衡二叉排序树。

【平衡因子】：结点的左子树深度与右子树深度之差。

由性质可知，一棵平衡二叉排序树的所有结点的平衡因子只能是-1、0或1。

插入操作

当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现绝对值大于1的平衡因子。

平衡二叉排序树的插入：

1. 将新结点插入到平衡二叉排序树中（插入方法同二叉排序树）
2. 从插入点到根结点分别检查是否平衡因子
3. 若所有结点的平衡因子 ≤ 1，则无需调整；
4. 若找到一个失去平衡的结点，则进行旋转使新结点插入后的路径上的所有结点都变成最小不平衡子树；根据最小不平衡子树的失衡类型进行旋转调整。

四种失衡类型

LL型调整

由于结点的左子树的左分支上插入了新结点导致了失衡故称之为LL型。

LR型调整

RR型调整

由于在结点的右子树的右分支上插入了新结点导致了失衡故称之为RR型。

RL型调整

红黑树

红黑树定义

红黑树就是一种特殊的平衡二叉排序树，除了符合二叉排序树的性质外，还具体下列的特性：

1. 结点是红色或者黑色
2. 根结点是黑色
3. 每个叶子的结点都是黑色的空结点（NULL）（外部结点）
4. 每个红色结点的两个子结点都是黑色的。
5. 从任意结点到其每个叶子的所有路径都包含相同的黑色结点。

红黑树性质总结

• Rudolf Bayer 1972年发明，在当时被称为平衡二叉B树（symmetric binary B-trees）
• 1978年Leo J.Guibas 和Robert Sedgwick 修改了如今的红黑树。
• 红黑树具有良好的效率，它可以在O（log n）时间内完成查找、插入和删除操作。

一棵有n个结点的红黑树的高度最多为2（log（n+1））。
简单证明如下页

红黑树的插入和建立

红黑树插入

同二叉排序树插入运算，首先需要在已有的红黑树中插入新结点，新结点默认为红色且位于终端结点（除了附加的叶子结点外）。

当在红黑树中插入新结点后，可能要根据红黑树的定义进行调整：

旋转 变色

插入情况分析

新结点是黑色时，直接插入新结点即可。

若新插入的结点（红色）的父结点是黑色的，则直接将新结点插入即可。

若新插入的结点（红色）的父结点是红色的且其叔结点也是红色的，则需要将父和叔结点变为黑色，爷结点变为红色。

之后：父结点为根结点，则根据红色结点与其父的颜色决定进一步的"调整"

若新插入的结点（红色）的父结点是红色且其叔结点为空或者为黑色：

需要根据类型：

• LL
• LR
• RL
• RR

进行旋转和变色。

B树

实际问题

实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的，自然该节点的子树数量也就是有限的。

解决办法

减少树的深度（当然是不能减少少于的数据量）。

一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

新的查找树结构——多路（m路）查找树结构，即B树结构。

m路查找树（m叉排序树）

**定义：**一棵m路查找树，或者是空树，或者是满足如下性质的树：

1. 结点最多有m棵子树；
2. 根结点至少有2棵子树；
3. 除根结点之外的所有非叶结点至少有⌈m/2⌉棵子树（有⌈m/2⌉-1个关键字）；
4. 所有叶结点出现在同一层上，并且不含信息，通常称为失败结点。失败结点为虚结点，在B树中并不存在，指向它们的指针为空指针。引入失败结点是为了便于分析B树的查找性能。

B树

一棵B树是一棵平衡的m路查找树，它或者是空树，或者是满足如下性质的树：

1. 树中每个结点最多有m棵子树；
2. 根结点至少有2棵子树；
3. 除根结点之外的所有非叶结点至少有⌈m/2⌉棵子树（有⌈m/2⌉-1个关键字），m-1个关键字）；
4. 所有叶结点出现在同一层上，并且不含信息，通常称为失败结点。失败结点为虚结点，在B树中并不存在，指向它们的指针为空指针。引入失败结点是为了便于分析B树的查找性能。

B树的高度

有n个关键字的m阶B树，其高度h的范围如何确定？

**最小高度：**即将n个关键字列表元素集合组成满二叉。则有：

$$=m^{h-1}$$

每个结点都分m个文，即有每个结点最多有m-1个关键字，第一层m个结点，第二层m²个结点。

$$h>=\lceil {\log }_m(n+1)\rceil$$

最大高度：

$$2^{\lceil \frac{m}{2}{\rceil }^{h-1}}\le n+1$$

B树的查找

我们从上述的查找过程可以得出，在B-树的查找过程为：

1. 在B-树中查找给定关键字的方法是：首先把根结点读入内存，在根结点所包含的关键字K1,K2,…,Kn中查找给定的关键字（可以采用顺序查找或二分查找），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在某个Ki与Ki+1之间，从而选择对应的指针Ai，将指向结点读入内存，继续上述查找过程，直到找到结点中的关键字等于给定值，或者指针Ai为空为止。

2. 在实际应用中，从磁盘上读一个结点的信息所耗费的时间远远超过内存中的一次查找所用的时间，是检索的时间主要由读磁盘的次数来决定。

B树插入

首先假设这个B-树的阶为：3，则每个分支点最多包含2个关键字，最少包含⌈3/2⌉-1即1个关键字。树的初始化如下：

当插入关键字：30，可以得到如下的结果：

[详细插入过程示例…]

B树删除

Case1: 删除终端结点（失败叶子结点紧相邻的上一层结点）

[详细删除过程示例…]

Case2: 删除非终端结点

删除

1. 若小于K的子树中关键字个数>⌈m/2⌉-1,则找出那个前驱值K’，并用K’来取代K，再递归地删除K’即可。

2. 若大于K的子树中关键字个数>⌈m/2⌉-1,则找出那个后继值K’，并用K’来取代K，再递归地删除K’即可。

3. 若前面两个子树关键字个数均为⌈m/2⌉-1，则将关键字K连同根指合两个子结合并，然后删除K即可。

B+树

B+树

B+树是应数据库所需而出现的一种B树的变形树。一棵B+树需要满足下列条件：

1. 每个分支点最多有m棵子树（孩子结点）；
2. 非叶根结点至少有2棵子树，除根结点以外的所有非叶结点至少有⌈m/2⌉棵子树；
3. 结点的子树与关键字个数相等；
4. 所有叶结点包含全部关键字及指向相应记录（数据）的指针，叶结点中关键字按大小顺序排列，并且相邻叶结点按大小顺序相接起来；
5. 所有分支结点中仅包含它的各个子结点（即下一级索引块）中关键字的最大值（或最小值）及指向其子结点的指针。

B树与B+树主要区别

• B+树中具有n个关键字的结点含有n棵子树，即每个关键字对应一棵子树；
• B树中，具有n个关键字的结点含有n+1棵子树。

B+树主要特征

• m阶B+树中每个（非根分支点）结点关键字个数的取值范围为⌈m/2⌉ ≤ n ≤ m；（根结点：1 ≤ n ≤ m）；
• m阶B树中，每个（非根分支点）结点关键字个数的取值范围为⌈m/2⌉-1 ≤ n ≤ m-1；（根结点：1 ≤ n ≤ m-1）；

计算式查找法——哈希查找

哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表称为哈希表。

哈希法的基本思想

首先在元素的关键字k和元素的存储位置p之间建立一个对应关系，使得p=f(k)，f称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为f(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=f(k)，从而达到按关键字直接存取元素的目的。

哈希查找过程

**step1：**将列表元素存储到存储空间HashTable[M]中；

**step2：**查找关键字值为k的数据；

1. 先做Hash(k)的函数计算，计算出的值为m；
2. 到HashTable[m]的单元去找关键字值为k的数据。

哈希查找法：查找的出发点不是拿关键字值与表中关键字的比较，而是拿关键字值自己做Hash(k)哈希函数计算，得到的值做地址，去找HashTable中地址为Hash(k)的单元，以期找到关键字值为k的数据。

冲突处理

当Hash(Ki)= Hash(Kj)时发生冲突

冲突必须解决！如何解决？给Rj重新找一个空间安放。

新的问题：查找时，是否仅过地址计算后，就认为对应单元存放的就是要查找的元素呢？

哈希函数的构造方法

构造原则：

1. 函数本身便于计算；
2. 计算出来的地址分布均匀，即对任一关键字k，f(k)对应不同地址的概率相等，目的是尽可能减少冲突。

常见哈希函数

• 数字分析法、
• 平方取中、
• 分段叠加法
• 除留余数法
• 伪随机数法等。

除留余数法

假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为：H(k)=k%p其中%为模p取余运算

为减少冲突，取较大的值和值，m=p=13

$$h(18)=18\%13=5$$
$$h(75)=75\%13=10$$
$$h(60)=60\%13=8$$
$$h(43)=43\%13=4$$
$$h(54)=54\%13=2$$
$$h(90)=90\%13=12$$
$$h(46)=46\%13=7$$

处理冲突的方法

1.开放定址法（再散列法）

**基本思想：**当关键字key的哈希地址p=H(key)出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=(H(key)+di)%m，其中H(key)为哈希函数，m为表长，di为增量序列。

**线性探测再散列：**di=1, 2, 3, ···, m-1
**二次探测再散列：**di=1², -1², 2², -2²,···, k², -k²
k<=m/2，m是可以表示成4k+3的素数
伪随机数：

2.再哈希法

同时构造多个不同的哈希函数：
Hi=RH1（key）i=1，2，···，k

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）······直到冲突不再产生。

这种方法不易产生聚集，但增加了计算时间。

3.链地址法

**基本思想：**将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。

4.建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

哈希表的查找算法（线性探测再散列处理冲突）

#define m <哈希表长度>
#define NULLKEY <代表空记录的关键字值>

typedef int KeyType;
typedef struct {
    KeyType key;
    ......
} RecordType;

哈希表的查找算法（线性探测再散列处理冲突）

int HashSearch(HashTable ht, KeyType K)
{
    p0=hash(K);
    if (ht[p0].key==NULLKEY) return (-1);
    else if (ht[p0].key==K) return (p0);
    else {
        for (i=1; i<=m-1; i++) {
            pi=(p0+i) % m;
            if (ht[pi].key==NULLKEY)
                return (-1);
            else if (ht[pi].key==K) return (pi);
        }
        return (-1);
    }
}

哈希表的创建算法（线性探测再散列处理冲突）

CreateHashTable (Hash Table ht, RecordType r[])
{
    for(i=1;i<=n;i++) {
        p0=hash(r[i].key);
        if(ht[p0].key==NULLKEY) ht[p0]=r[i];
        else{
            for(j=1;j<=m-1;j++) {
                pi=(p0+j)%m;
                if(ht[pi].key==NULLKEY) {ht[pi]=r[i]; break;}
            }
        }
    }
}

哈希法性能分析

影响比较次数的因素

1. 哈希函数
2. 处理冲突的方法
3. 装填因子

哈希表的装填因子α的定义如下：
α=哈希表中元素个数/哈希表的长度

α描述哈希表的装满程度。显然，α越小，发生冲突的可能性越小，而α越大，发生冲突的可能性也越大。

性能分析示例

手工计算等概率情况下查找成功的平均查找长度公式

$$AS{L}_{succ}=\frac{1}{n}\sum _{i=1}^n{C}_i$$

**示例：**已知一组关键字序列（19，14，23，01，68，20，84，27，55，11，10，79）哈希函数H(key)=key % 13

$$\frac{1}{12}(1\times 6+2\times 3+3\times 3+4\times 9)=2.5$$

总结

本章介绍了多种查找算法，包括基于线性表的查找（顺序查找、折半查找、分块查找），基于树的查找（二叉排序树、平衡二叉排序树、红黑树、B树、B+树）以及哈希查找。每种算法都有其适用场景和性能特点：

• 顺序查找：适用于无序表，时间复杂度O(n)
• 折半查找：适用于有序表，时间复杂度O(log n)
• 分块查找：兼顾插入删除和查找效率
• 二叉排序树：动态查找表，平均时间复杂度O(log n)
• 平衡二叉排序树：保证最坏情况下的查找效率
• 红黑树：实际应用中的高效平衡树
• B树/B+树：适用于外存查找，数据库索引的基础
• 哈希查找：理想情况下时间复杂度O(1)，但需要处理冲突

选择合适的查找算法需要根据具体的应用场景、数据规模、更新频率等因素综合考虑。