查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

8.1-8.2 查找概论

查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。例如图8-2-1就是一个查找表。

关键字（Key）是数据元素中某个数据项的值，又称为键值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项（字段），我们称为关键码，如图8-2-1中①和②所示。
若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary Key）。注意这也就意味着，对不同的记录，其主关键字均不相同。主关键字所在的数据项称为主关键码，如图8-2-1中③和④所示。
那么对于那些可以识别多个数据元素（或记录）的关键字，我们称为次关键字（Secondary Key），如图8-2-1中⑤所示。次关键字也可以理解为是不以唯一标识一个数据元素（或记录）的关键字，它对应的数据项就是次关键码。
查找表按照操作方式来分有两大种：静态查找表和动态查找表。
静态查找表（Static Search Table）：只作查找操作的查找表。它的主要操作有：

1. 查询某个“特定的”数据元素是否在查找表中。
2. 检索某个“特定的”数据元素和各种属性。

动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。显然动态查找表的操作就是两个：

1. 查找时插入数据元素。
2. 查找时删除数据元素。

为了提高查找的效率，我们需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。
从逻辑上来说，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。可是要想获得较高的查找性能，我们就不能不改变数据元素之间的关系，在存储时可以将查找集合组织成表、树等结构。
例如，对于静态查找表来说，我们不妨应用线性表结构来组织数据，这样可以使用顺序查找算法，如果再对主关键字排序，则可以应用折半查找等技术进行高效的查找。
如果是需要动态查找，则会复杂一些，可以考虑二叉排序树的查找技术。

8.3 顺序表查找

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

8.3.1 顺序表查找算法

顺序查找的算法实现如下：

/* 无哨兵顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字 */
int Sequential_Search(int *a,int n,int key)
{
    int i;
    for(i=1;i<=n;i++){
        if (a[i]==key)
            return i;
    }
    return 0;
}

8.3.2 顺序表查找优化

到这里并非足够完美，因为每次循环时都需要对i是否小于等于n作判断。事实上，设置一个哨兵，就不需要每次让i与n作比较。看下面的改进后的顺序查找算法代码。

/* 有哨兵顺序查找 */
int Sequential_Search2(int *a,int n,int key)
{
    int i;
    a[0]=key;
    i=n;
    while(a[i]!=key){
        i--;
    }
    return i;
}

这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。当然，“哨兵”也不一定就一定要在数组开始，也可以在末端。
对于这种顺序查找算法来说，平均查找次数为（n+1）/2，所以最终时间复杂度还是O（n）。
很显然，顺序查找技术是有很大缺点的，n很大时，查找效率极为低下，不过优点也是有的，算法非常简单，对静态查找表的记录没有任何要求，在一些小型数据的查找时，是可以适用的。
另外，也正由于查找概率的不同，我们完全可以将容易查找到的记录放在前面，而不常用的记录放置在后面，效率就可以有大幅提高。

8.4 有序表查找

8.4.1 折半查找

折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
折半查找代码如下：

/* 折半查找 */
int Binary_Search(int *a,int n,int key){
    int low,high,mid;
    low=1;    /* 定义最低下标为记录首位 */
    high=n;    /* 定义最高下标为记录末位 */
    while(low<=high){
        mid=(low+high)/2;    /* 折半 */
        if (key<a[mid])        /* 若查找值比中值小 */
            high=mid-1;        /* 最高下标调整到中位下标小一位 */
        else if (key>a[mid])/* 若查找值比中值大 */
            low=mid+1;        /* 最低下标调整到中位下标大一位 */
        else
            return mid;        /* 若相等则说明mid即为查找到的位置 */
    }
    return 0;
}

折半算法的时间复杂度为O（㏒n），它显然远远好于顺序查找的O（n）时间复杂度。
不过由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

8.4.2 插值查找

折半查找代码的第6句，我们略微等式变换后得到：
mid=(low+high)/2=low+1/2(high-low);
我们将在折半查找算法的代码中更改一下，第6行代码如下：
mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */
插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式(key-a[low])/(a[high]-a[low])。
应该说，从时间复杂度来看，它也是O（㏒n），但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。反之，数组中如果分布类似{0，1，2，2000，2001……，999998，999999}这种极端不均匀的数据，用插值查找未必是很合适的选择。

8.4.3 斐波那契查找

斐波那契查找（Fibonacci Search），它是利用了黄金分割原理来实现的。
下面我们根据代码来看程序是如何运行的。

/* 斐波那契查找 */
int Fibonacci_Search(int *a,int n,int key)
{
    int low,high,mid,i,k=0;
    low=1;    /* 定义最低下标为记录首位 */
    high=n;    /* 定义最高下标为记录末位 */
    while(n>F[k]-1) /* 计算n位于斐波那契数列的位置 */
        k++;
    for (i=n;i<F[k]-1;i++) /* 将不满的数值补全 */
        a[i]=a[n];
    while(low<=high){
        mid=low+F[k-1]-1;
        if (key<a[mid]){
            high=mid-1;
            k=k-1;
        }
        else if (key>a[mid]){
            low=mid+1;
            k=k-2;
        }
        else{
            if (mid<=n)
                return mid;        /* 若相等则说明mid即为查找到的位置 */
            else
                return n;
        }
    }
    return 0;
}

斐波那契查找算法的核心在于：

1. 当key=a[mid]时，查找就成功；
2. 当key<a[mid]时，新范围是第low个到第mid-1个，此时范围个数为F[k-1]-1个；
3. 当key>a[mid]时，新范围是第m+1个到第high个，此时范围个数为F[k-2]-1个。

也就是说，如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于当中的大部分数据，其工作效率要高一些。所以尽管斐波那契查找的时间复杂也为O（㏒n），但就平均性能来说，斐波那契查找要优于折半查找。可惜如果是最坏情况，比如这里key=1，那么始终都处于左侧长半区在查找，则查找效率要低于折半查找。
还有比较关键的一点，折半查找是进行加法与除法运算（mid=（low+high）/2），插值查找进行复杂的四则运算mid=low+ (high-low)*(key-a[low])/(a[high]-a[low])，而斐波那契查找只是最简单加减法运算（mid=low+F[k-1]-1），在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。
应该说，三种有序表的查找本质上是分隔点的选择不同，各有优劣，实际开发时可根据数据的特点综合考虑再做出选择。

8.5 线性索引查找

数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。
索引按照结构可以分为线性索引、树形索引和多级索引。我们这里就只介绍线性索引技术。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。我们重点介绍三种线性索引：稠密索引、分块索引和倒排索引。

8.5.1 稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。，如图8-5-2所示。

对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。

8.5.2 分块索引

稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。

分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：

• 块内无序，即每一块内的记录不要求有序。当然，你如果能够让块内有序对查找来说更理想，不过这就要付出大量时间和空间的代价，因此通常我们不要求块内有序。
• 块间有序，例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字……因为只有块间有序，才有可能在查找时带来效率。

对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。

如图8-5-4所示，我们定义的分块索引的索引项结构分三个数据项：

• 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大；
• 存储了块中的记录个数，以便于循环时使用；
• 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

在分块索引表中查找，就是分两步进行：

1. 在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。例如，在图8-5-4的数据集中查找62，我们可以很快可以从左上角的索引表中由57<62<96得到62在第三个块中。
2. 根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。

分块索引查找的平均查找长度为：（√n）+1。
可见，分块索引的效率比之顺序查找的O（n）是高了不少，不过显然它与折半查找的O（㏒n）相比还有不小的差距。因此在确定所在块的过程中，由于块间有序，所以可以应用折半、插值等手段来提高效率。
总的来说，分块索引在兼顾了对细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据库表查找等技术的应用当中。

8.5.3 倒排索引

搜索引擎常用的最简单的，也算是最基础的搜索技术——倒排索引。
比如不同的文章，将所有单词整理出一张单词表，并排序，出现该单词的则标记为后面的文章编号。

索引项的通用结构是：

• 次关键码，例如“英文单词”；
• 记录号表，例如“文章编号”。

其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒排索引（inverted index）。倒排索引源于实际应用中需要根据属性（或字段、次关键码）的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。
倒排索引的优点显然就是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，就可以得到结果。但它的缺点是这个记录号不定长，比如上例有7个单词的文章编号只有一个，而“book”、“friend”、“good”有两个文章编号，若是对多篇文章所有单词建立倒排索引，那每个单词都将对应相当多的文章编号，维护比较困难，插入和删除操作都需要作相应的处理。

8.6 二叉排序树

二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

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

这样我们就得到了一棵二叉树，并且当我们对它进行中序遍历时，就可以得到一个有序的序列，所以我们通常称它为二叉排序树。

8.6.1 二叉排序树查找操作

首先我们提供一个二叉树的结构。

/* 二叉树的二叉链表结点结构定义 */
typedef  struct BiTNode    /* 结点结构 */
{
    int data;    /* 结点数据 */
    struct BiTNode *lchild, *rchild;    /* 左右孩子指针 */
} BiTNode, *BiTree;

然后我们来看看二叉排序树的查找是如何实现的。

/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
    if (!T)    /*  查找不成功 */
    {
        *p = f;
        return FALSE;
    }
    else if (key == T->data) /*  查找成功 */
    {
        *p = T;
        return TRUE;
    }
    else if (key < T->data)
        return SearchBST(T->lchild, key, T, p);  /*  在左子树中继续查找 */
    else
        return SearchBST(T->rchild, key, T, p);  /*  在右子树中继续查找 */
}

8.6.2 二叉排序树插入操作

有了二叉排序树的查找函数，那么所谓的二叉排序树的插入，其实也就是将关键字放到树中的合适位置而已，来看代码。

/*  当二叉排序树T中不存在关键字等于key的数据元素时， */
/*  插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key)
{
    BiTree p, s;
    if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if (!p) /* 此时因为已经查找过了，所有p指向最后查找的根结点 */
            *T = s;            /*  插入s为新的根结点 */
        else if (key < p->data)
            p->lchild = s;    /*  插入s为左孩子 */
        else
            p->rchild = s;  /*  插入s为右孩子 */
        return TRUE;
    }
    else
        return FALSE;  /*  树中已有关键字相同的结点，不再插入 */
}

有了二叉排序树的插入代码，我们要实现二叉排序树的构建就非常容易了。

int i;
    int a[10] = { 62,88,58,47,35,73,51,99,37,93 };
    BiTree T = NULL;
    for (i = 0; i < 10; i++)
        InsertBST(&T, a[i]);

8.6.3 二叉排序树删除操作

对于要删除的结点只有左子树或只有右子树的情况，相对也比较好解决。那就是结点删除后，将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业。最终，整个结构还是一个二叉排序树。
但是对于要删除的结点既有左子树又有右子树的情况怎么办呢？
比较好的办法就是，找到需要删除的结点p的直接前驱（或直接后继）s，用s来替换结点p，然后再删除此结点s。

根据我们对删除结点三种情况的分析：

• 叶子结点；
• 仅有左或右子树的结点；
• 左右子树都有的结点。

我们来看代码，下面这个算法是递归方式对二叉排序树T查找key，查找到时删除。

/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE。 */
Status DeleteBST(BiTree *T, int key)
{
    if (!*T) /* 不存在关键字等于key的数据元素 */
        return FALSE;
    else
    {
        if (key == (*T)->data) /* 找到关键字等于key的数据元素 */
            return Delete(T);
        else if (key < (*T)->data)
            return DeleteBST(&(*T)->lchild, key);
        else
            return DeleteBST(&(*T)->rchild, key);
    }
}

这段代码和前面的二叉排序树查找几乎完全相同，唯一的区别就在于第8行，此时执行的是Delete方法，对当前结点进行删除操作。我们来看Delete的代码。

/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
Status Delete(BiTree *p)
{
    BiTree q, s;//q、s为临时结点
    if ((*p)->rchild == NULL) /* 右子树空则只需重接它的左子树(待删结点是叶子也走此分支) */
    {
        q = *p; *p = (*p)->lchild; free(q);
    }
    else if ((*p)->lchild == NULL) /* 只需重接它的右子树 */
    {
        q = *p; *p = (*p)->rchild; free(q);
    }
    else /* 左右子树均不空 */
    {
        q = *p; s = (*p)->lchild;
        while (s->rchild) /* 转左，然后向右到尽头（找待删结点NULL的前驱） */
        {//根结点*p的左子树中最右的叶结点为直接前驱
            q = s;
            s = s->rchild;
        }
        (*p)->data = s->data; /*  s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */
        if (q != *p)
            q->rchild = s->lchild; /*  重接q的右子树 */
        else
            q->lchild = s->lchild; /*  重接q的左子树 */
        free(s);
    }
    return TRUE;
}

从这段代码也可以看出，我们其实是在找删除结点的前驱结点替换的方法，对于用后继结点来替换，方法上是一样的。

8.6.4 二叉排序树总结

总之，二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即根结点就是要找的结点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。
如果，数组元素的次序是从小到大有序，则二叉排序树就成了极端的右斜树，查找时间复杂度为O（n），等同于顺序查找。
因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。即其深度与完全二叉树相同，那么查找的时间复杂就为O（㏒n），近似于折半查找。

8.7 平衡二叉树（AVL树）

平衡二叉树（Self-Balancing Binary Search Tree 或Height-Balanced Binary Search Tree），是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。
从平衡二叉树的英文名字，你也可以体会到，它是一种高度平衡的二叉排序树。那什么叫做高度平衡呢？意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor），那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。

8.7.1 平衡二叉树实现原理

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
所谓的平衡二叉树，其实就是在二叉排序树创建过程中保证它的平衡性，一旦发现有不平衡的情况，马上处理，这样就不会造成不可收拾的情况出现。通过刚才这个例子，你会发现，当最小不平衡子树根结点的平衡因子BF是大于1时，就右旋，小于-1时就左旋。当插入结点后，最小不平衡子树的BF与它的子树的BF符号相反时，就需要对结点先进行一次旋转以使得符号相同后，再反向旋转一次才能够完成平衡操作。

8.7.2 平衡二叉树实现算法

首先是需要改进二叉排序树的结点结构，增加一个bf，用来存储平衡因子。

/* 二叉树的二叉链表结点结构定义 */
typedef  struct BiTNode    /* 结点结构 */
{
    int data;    /* 结点数据 */
    int bf; /*  结点的平衡因子 */
    struct BiTNode *lchild, *rchild;    /* 左右孩子指针 */
} BiTNode, *BiTree;

然后，对于右旋操作，我们的代码如下。

/* 对以p为根的二叉排序树作右旋处理， */
/* 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */
void R_Rotate(BiTree *P)
{
    BiTree L;
    L = (*P)->lchild; /*  L指向P的左子树根结点 */
    (*P)->lchild = L->rchild; /*  L的右子树挂接为P的左子树 */
    L->rchild = (*P);
    *P = L; /*  P指向新的根结点 */
}

此函数代码的意思是说，当传入一个二叉排序树P，将它的左孩子结点定义为L，将L的右子树变成P的左子树，再将P改成L的右子树，最后将L替换P成为根结点。这样就完成了一次右旋操作，如图8-7-9所示。图中三角形代表子树，N代表新增结点。

左旋操作代码如下。

/* 对以P为根的二叉排序树作左旋处理， */
/* 处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0  */
void L_Rotate(BiTree *P)
{
    BiTree R;
    R = (*P)->rchild; /*  R指向P的右子树根结点 */
    (*P)->rchild = R->lchild; /* R的左子树挂接为P的右子树 */
    R->lchild = (*P);
    *P = R; /*  P指向新的根结点 */
}

这段代码与右旋代码是对称的，在此不做解释了。
现在我们来看左平衡旋转处理的函数代码。

#define LH +1 /*  左高 */
#define EH 0  /*  等高 */
#define RH -1 /*  右高 */

/*  对以指针T所指结点为根的二叉树作左平衡旋转处理 */
/*  本算法结束时，指针T指向新的根结点 */
void LeftBalance(BiTree *T)
{
    BiTree L, Lr;
    L = (*T)->lchild; /*  L指向T的左子树根结点 */
    switch (L->bf)
    { /*  检查T的左子树的平衡度，并作相应平衡处理 */
    case LH: /*  新结点插入在T的左孩子的左子树上，要作单右旋处理 */
        (*T)->bf = L->bf = EH;
        R_Rotate(T);
        break;
    case RH: /*  新结点插入在T的左孩子的右子树上，要作双旋处理 */
        Lr = L->rchild; /*  Lr指向T的左孩子的右子树根 */
        switch (Lr->bf)
        { /*  修改T及其左孩子的平衡因子 */
        case LH: (*T)->bf = RH;
            L->bf = EH;
            break;
        case EH: (*T)->bf = L->bf = EH;
            break;
        case RH:
            (*T)->bf = EH;
            L->bf = LH;
            break;
        }
        Lr->bf = EH;
        L_Rotate(&(*T)->lchild); /*  对T的左子树作左旋平衡处理 */
        R_Rotate(T); /*  对T作右旋平衡处理 */
    }
}

首先，我们定义了三个常数变量，分别代表1、0、-1。

1. 函数被调用，传入一个需调整平衡性的子树T。由于LeftBalance 函数被调用时，其实是已经确认当前子树是不平衡状态，且左子树的高度大于右子树的高度。换句话说，此时T的根结点应该是平衡因子BF的值大于1的数。
2. 第4行，我们将T的左孩子赋值给L。
3. 第5~27行是分支判断。
4. 当L的平衡因子为LH，即为1时，表明它与根结点的BF值符号相同，因此，第8行，将它们的BF值都改为0，并且第9行，进行右旋操作。操作的方式如图8-7-9所示。
5. 当L的平衡因子为RH，即为-1时，表明它与根结点的BF值符号相反，此时需要做双旋处理。第13~22行，针对L的右孩子Lr的BF作判断，修改根结点T和L的BF值。第24行将当前Lr的BF改为0。
6. 第25行，对根结点的左子树进行左旋，如图8-7-10第二图所示。
7. 第26行，对根结点进行右旋，如图8-7-10的第三图所示，完成平衡操作。

同样的，右平衡旋转处理的函数代码非常类似。

/*  对以指针T所指结点为根的二叉树作右平衡旋转处理， */
/*  本算法结束时，指针T指向新的根结点 */
void RightBalance(BiTree *T)
{
    BiTree R, Rl;
    R = (*T)->rchild; /*  R指向T的右子树根结点 */
    switch (R->bf)
    { /*  检查T的右子树的平衡度，并作相应平衡处理 */
    case RH: /*  新结点插入在T的右孩子的右子树上，要作单左旋处理 */
        (*T)->bf = R->bf = EH;
        L_Rotate(T);
        break;
    case LH: /*  新结点插入在T的右孩子的左子树上，要作双旋处理 */
        Rl = R->lchild; /*  Rl指向T的右孩子的左子树根 */
        switch (Rl->bf)
        { /*  修改T及其右孩子的平衡因子 */
        case RH:
            (*T)->bf = LH; R->bf = EH; break;
        case EH:
            (*T)->bf = R->bf = EH; break;
        case LH:
            (*T)->bf = EH; R->bf = RH; break;
        }
        Rl->bf = EH;
        R_Rotate(&(*T)->rchild); /*  对T的右子树作右旋平衡处理 */
        L_Rotate(T); /*  对T作左旋平衡处理 */
    }
}

有了这些准备，我们的主函数才算是正式登场了。

/*  若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */
/*  数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */
/*  失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 */
Status InsertAVL(BiTree *T, int e, Status *taller)
{
    if (!*T)
    { /*  插入新结点，树“长高”，置taller为TRUE */
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = e; (*T)->lchild = (*T)->rchild = NULL; (*T)->bf = EH;
        *taller = TRUE;
    }
    else
    {
        if (e == (*T)->data)
        { /*  树中已存在和e有相同关键字的结点则不再插入 */
            *taller = FALSE; return FALSE;
        }
        if (e < (*T)->data)
        { /*  应继续在T的左子树中进行搜索 */
            if (!InsertAVL(&(*T)->lchild, e, taller)) /*  未插入 */
                return FALSE;
            if (*taller) /*   已插入到T的左子树中且左子树“长高” */
                switch ((*T)->bf) /*  检查T的平衡度 */
                {
                case LH: /*  原本左子树比右子树高，需要作左平衡处理 */
                    LeftBalance(T);    *taller = FALSE; break;
                case EH: /*  原本左、右子树等高，现因左子树增高而使树增高 */
                    (*T)->bf = LH; *taller = TRUE; break;
                case RH: /*  原本右子树比左子树高，现左、右子树等高 */
                    (*T)->bf = EH; *taller = FALSE; break;
                }
        }
        else
        { /*  应继续在T的右子树中进行搜索 */
            if (!InsertAVL(&(*T)->rchild, e, taller)) /*  未插入 */
                return FALSE;
            if (*taller) /*  已插入到T的右子树且右子树“长高” */
                switch ((*T)->bf) /*  检查T的平衡度 */
                {
                case LH: /*  原本左子树比右子树高，现左、右子树等高 */
                    (*T)->bf = EH; *taller = FALSE;    break;
                case EH: /*  原本左、右子树等高，现因右子树增高而使树增高  */
                    (*T)->bf = RH; *taller = TRUE; break;
                case RH: /*  原本右子树比左子树高，需要作右平衡处理 */
                    RightBalance(T); *taller = FALSE; break;
                }
        }
    }
    return TRUE;
}

不容易，终于讲完了，本算法代码很长，是有些复杂，编程中容易在很多细节上出错，要想真正掌握它，需要同学们自己多练习。不过其思想还是不难理解的，总之就是把不平衡消灭在最早时刻。
如果我们需要查找的集合本身没有顺序，在频繁查找的同时也需要经常的插入和删除操作，显然我们需要构建一棵二叉排序树，但是不平衡的二叉排序树，查找效率是非常低的，因此我们需要在构建时，就让这棵二叉排序树是平衡二叉树，此时我们的查找时间复杂度就为O（㏒n），而插入和删除也为O（㏒n）。这显然是比较理想的一种动态查找表算法。

8.8 多路查找树（B树）

多路查找树（muitl-way search tree），其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。
在这里，每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的。为此，我们讲解它的4种特殊形式：2-3树、2-3-4树、B树和B+树。

8.8.1 2-3树

2-3树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为3结点）。
一个2结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个2结点要么没有孩子，要有就有两个，不能只有一个孩子。
一个3结点包含一小一大两个元素和三个孩子（或没有孩子），一个3结点要么没有孩子，要么具有3个孩子。如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
并且2-3树中所有的叶子都在同一层次上。如图8-8-2所示，就是一棵有效的2-3树。

一 2-3树的插入实现
对于2-3树的插入来说，与二叉排序树相同，插入操作一定是发生在叶子结点上。可与二叉排序树不同的是，2-3树插入一个元素的过程有可能会对该树的其余结构产生连锁反应。
2-3树插入可分为三种情况。

1. 对于空树，插入一个2结点即可，这很容易理解。
2. 插入结点到一个2结点的叶子上。应该说，由于其本身就只有一个元素，所以只需要将其升级为3结点即可。如图8-8-3所示。我们希望从左图的2-3树中插入元素3，根据遍历可知，3比8小、比4小，于是就只能考虑插入到叶子结点1所在的位置，因此很自然的想法就是将此结点变成一个3结点，即右图这样完成插入操作。当然，要视插入的元素与当前叶子结点的元素比较大小后，决定谁在左谁在右。例如，若插入的是0，则此结点就是“0”在左“1”在右了。
3. 要往3结点中插入一个新元素。因为3结点本身已经是2-3树的结点最大容量（已经有两个元素），因此就需要将其拆分，且将树中两元素或插入元素的三者中选择其一向上移动一层。
   

二 2-3树的删除实现
删除情况较多，具体请见大话数据结构P348。

当然，如果对2-3树的插入和删除等所有的情况进行讲解，既占篇幅，又没必要，总的来说它是有规律的，需要你们在上面的这些例子中多去体会后掌握。

8.8.2 2-3-4树

有了2-3树的讲解，2-3-4树就很好理解了，它其实就是2-3树的概念扩展，包括了4结点的使用。一个4结点包含小中大三个元素和四个孩子（或没有孩子），一个4结点要么没有孩子，要么具有4个孩子。如果某个4结点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。
由于2-3-4树和2-3树是类似的，我们这里就简单介绍一下，如果我们构建一个数组为{7，1，2，5，6，9，8，4，3}的2-3-4树的过程，如图8-8-15所示。图1是在分别插入7、1、2时的结果图，因为3个元素满足2-3-4树的单个4结点定义，因此此时不需要拆分，接着插入元素5，因为已经超过了4结点的定义，因此拆分为图2的形状。之后的图其实就是在元素不断插入时最后形成了图7的2-3-4树。

图8-8-16是对一个2-3-4树的删除结点的演变过程，删除顺序是1、6、3、4、5、2、9。

8.8.3 B树

B树（B-tree）是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶（order），因此，2-3树是3阶B树，2-3-4树是4阶B树。
一个m阶的B树具有如下属性：

在B树上查找的过程是一个顺指针查找结点和在结点中查找关键字的交叉过程。
比方说，我们要查找数字7，首先从外存（比如硬盘中）读取得到根结点3、5、8三个元素，发现7不在当中，但在5和8之间，因此就通过Az再读取外存的6、7结点，查找到所要的元素。
至于B树的插入和删除，方式是与2-3树和2-3-4树相类似的，只不过阶数可能会很大而已。
我们在本节的开头提到，如果内存与外存交换数据次数频繁，会造成了时间效率上的瓶颈，那么B树结构怎么就可以做到减少次数呢？
我们的外存，比如硬盘，是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是211到214个字节。
在一个典型的B树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。因此我们会对B树进行调整，使得B树的阶数（或结点的元素）与硬盘存储的页面大小相匹配。比如说一棵B树的阶为1001（即1个结点包含1000个关键字），高度为2，它可以储存超过10亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。
通过这种方式，在有限内存的情况下，每一次磁盘的访问我们都可以获得最大数量的数据。由于B树每结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少了必须访问结点和数据块的数量，从而提高了性能。可以说，B树的数据结构就是为内外存的数据交互准备的。
那么对于n个关键字的m阶B树，最坏情况是要查找几次呢？我们来作一分析。
也就是说，在含有n个关键字的B树上查找时，从根结点到关键字结点的路径上涉及的结点数不超过$\log_\frac m2\left(\frac{n+1}2\right)+1$。

8.8.4 B+树

B+树是应文件系统所需而出的一种B树的变形树，注意严格意义上讲，它其实已经不是第六章定义的树了。在B树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。
例如图8-8-19所示，就是一棵B+树的示意，灰色关键字即是根结点中的关键字在叶子结点再次列出，并且所有叶子结点都链接在一起。

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

• 有n棵子树的结点中包含有n个关键字；
• 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接；
• 所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字。

这样的数据结构最大的好处就在于，如果是要随机查找，我们就从根结点出发，与B树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，它也只是用来索引的，不能提供实际记录的访问，还是需要到达包含此关键字的终端结点。如果我们是需要从最小关键字进行从小到大的顺序查找，我们就可以从最左侧的叶子结点出发，不经过分支结点，而是延着指向下一叶子的指针就可遍历所有的关键字。
B+树的结构特别适合带有范围的查找。比如查找我们学校18~22岁的学生人数，我们可以通过从根结点出发找到第一个18岁的学生，然后再在叶子结点按顺序查找到符合范围的所有记录。
B+树的插入、删除过程也都与B树类似，只不过插入和删除的元素都是在叶子结点上进行而已。

8.9 散列表查找（哈希表）概述

能否直接通过关键字key得到要查找的记录内存存储位置呢,而不是挨个查找下标，再通过顺序存储的存储位置计算内存地址？

8.9.1 散列表查找定义

我们只要通过某个函数f，使得
存储位置=f（关键字）
那样我们可以通过查找关键字不需要比较就可获得需要的记录的存储位置。这就是一种新的存储技术——散列技术。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。查找时，根据这个确定的对应关系找到给定值key的映射f（key），若查找集合中存在这个记录，则必定在f（key）的位置上。
这里我们把这种对应关系f称为散列函数，又称为哈希（Hash）函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。那么关键字对应的记录存储位置我们称为散列地址。

8.9.2 散列表查找步骤

整个散列过程其实就是两步:

1. 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。不管什么记录，我们都需要用同一个散列函数计算出地址再存储。
2. 当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。说起来很简单，在哪存的，上哪去找，由于存取用的是同一个散列函数，因此结果当然也是相同的。

散列技术既是一种存储方法，也是一种查找方法。然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向查找的存储结构。
散列技术最适合的求解问题是查找与给定值相等的记录。对于查找来说，简化了比较过程，效率就会大大提高。但万事有利就有弊，散列技术不具备很多常规数据结构的能力。
比如那种同样的关键字，它能对应很多记录的情况，却不适合用散列技术；散列表也不适合范围查找，无法排序，无法计算最大值、最小值等结果。
设计一个简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题。
另一个问题是冲突。在理想的情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。我们时常会碰到两个关键字key1≠key2，但是却有f（key1）=f（key2），这种现象我们称为冲突（collsion），并把key1和key2称为这个散列函数的同义词（synonym）。出现了冲突当然非常糟糕，那将造成数据查找错误。尽管我们可以通过精心设计的散列函数让冲突尽可能的少，但是不能完全避免。于是如何处理冲突就成了一个很重要的课题，这在我们后面也需要详细讲解。

8.10 散列函数的构造方法

那么什么才算是好的散列函数呢？
1.计算简单。 2.散列地址分布均匀

8.10.1 直接定址法

可以取关键字的某个线性函数值为散列地址，即
f（key）=a x key+b（a、b为常数）
这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。

8.10.2 数字分析法

比如手机号码作为关键字，那么我们抽取手机号码后面的四位成为散列地址。
这里我们提到了一个关键词——抽取。抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。

8.10.3 平方取中法

这个方法计算很简单，假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227，用做散列地址。再比如关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是671，也可以是710，用做散列地址。平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

8.10.4 折叠法

折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如我们的关键字是9876543210，散列表表长为三位，我们将它分为四组，987|654|321|0，然后将它们叠加求和987+654+321+0=1962，再取后3位得到散列地址为962。
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

8.10.5 除留余数法

此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为：
f（key）=key mod p（p ≤ m）
mod是取模（求余数）的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。
很显然，本方法的关键就在于选择合适的p，p如果选得不好，就可能会容易产生同义词。
根据前辈们的经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。

8.10.6 随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是f（key）=random（key）。这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
总之，现实中，应该视不同的情况采用不同的散列函数。我们只能给出一些考虑的因素来提供参考：

1. 计算散列地址所需的时间。
2. 关键字的长度。
3. 散列表的大小。
4. 关键字的分布情况。
5. 记录查找的频率。

综合这些因素，才能决策选择哪种散列函数更合适。

8.11 处理散列冲突的方法

8.11.1 开放定址法

所谓的开放定址法就是一旦发生了冲突，就代入公式去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
公式是： fi(key)=(f(key)+di) MOD m (di=1,2,3,……,m-1)
我们把这种解决冲突的开放定址法称为线性探测法。
从这个例子我们也看到，我们在解决冲突的时候，还会碰到如48和37这种本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。很显然，堆积的出现，使得我们需要不断处理冲突，无论是存入还是查找效率都会大大降低。
我们可以把di该进为(di)²，增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为二次探测法。
fi（key）=（f（key）+di）MOD m （di=1²，(-1)²，2²,(-2)²,…，q²，(-q)²,q≤m/2）
还有一种方法是，在冲突时，对于位移量d采用随机函数计算得到，我们称之为随机探测法。
fi（key）=（f（key）+di）MOD m （di是一个随机数列）

8.11.2 再散列函数法

对于我们的散列表来说，我们事先准备多个散列函数。
f$_i$（key）=RH$_i$（key）（i=1,2,…,k）
这里RH$_i$，就是不同的散列函数，你可以把我们前面说的什么除留余数、折叠、平方取中全部用上。每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个可以把冲突解决掉。这种方法能够使得关键字不产生聚集，当然，相应地也增加了计算的时间。

8.11.3 链地址法

将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。对于关键字集合{12，67，56，16，25，37，22，29，15，47，48，34}，我们用前面同样的12为除数，进行除留余数法，可得到如图8-11-1结构，此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。

链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。

8.11.4 公共溢出区法

这个方法其实就更加好理解，你不是冲突吗？好吧，凡是冲突的都跟我走，我给你们这些冲突找个地儿待着。这就如同孤儿院收留所有无家可归的孩子一样，我们为所有冲突的关键字建立了一个公共的溢出区来存放。
就前面的例子而言，我们共有三个关键字{37，48，34}与之前的关键字位置有冲突，那么就将它们存储到溢出表中，如图8-11-2所示。

图8-11-2在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表去进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

8.12 散列表查找实现

8.12.1 散列表查找算法实现

首先是需要定义一个散列表的结构以及一些相关的常数。其中HashTable 就是散列表结构。结构当中的elem为一个动态数组。

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /* 定义散列表长为数组的长度 */
#define NULLKEY -32768
typedef struct{
    int *elem; /* 数据元素存储基址，动态分配数组 */
    int count; /*  当前数据元素个数 */
}HashTable;
int m = 0; /* 散列表表长，全局变量 */

有了结构的定义，我们可以对散列表进行初始化。

/* 初始化散列表 */
Status InitHashTable(HashTable *H){
    int i;
    m = HASHSIZE;
    H->count = m;
    H->elem = (int *)malloc(m * sizeof(int));
    for (i = 0; i < m; i++)
        H->elem[i] = NULLKEY;
    return OK;
}

为了插入时计算地址，我们需要定义散列函数，散列函数可以根据不同情况更改算法。

/* 散列函数 */
int Hash(int key)
{
    return key % m; /* 除留余数法 */
}

初始化完成后，我们可以对散列表进行插入操作。假设我们插入的关键字集合就是前面的{12，67，56，16，25，37，22，29，15，47，48，34}。

/* 插入关键字进散列表 */
void InsertHash(HashTable *H, int key)
{
    int addr = Hash(key); /* 求散列地址 */
    while (H->elem[addr] != NULLKEY) /* 如果不为空，则冲突 */
        addr = (addr + 1) % m; /* 开放定址法的线性探测 */
    H->elem[addr] = key; /* 直到有空位后插入关键字 */
}

代码中插入关键字时，首先算出散列地址，如果当前地址不为空关键字，则说明有冲突。此时我们应用开放定址法的线性探测进行重新寻址，此处也可更改为链地址法等其他解决冲突的办法。
散列表存在后，我们在需要时就可以通过散列表查找要的记录。

/* 散列表查找关键字 */
Status SearchHash(HashTable H, int key, int *addr)
{
    *addr = Hash(key);  /* 求散列地址 */
    while (H.elem[*addr] != key) /* 如果不为空，则冲突 */
    {
        *addr = (*addr + 1) % m; /* 开放定址法的线性探测 */
        if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* 如果循环回到原点 */
            return UNSUCCESS;    /* 则说明关键字不存在 */
    }
    return SUCCESS;
}

查找的代码与插入的代码非常类似，只需做一个不存在关键字的判断而已。

8.12.2 散列表查找性能分析

最后，我们对散列表查找的性能作一个简单分析。如果没有冲突，散列查找是我们本章介绍的所有查找中效率最高的，因为它的时间复杂度为O(1)。可惜，我说的只是“如果”，没有冲突的散列只是一种理想，在实际的应用中，冲突是不可避免的。那么散列查找的平均查找长度取决于哪些因素呢？

1. 散列函数是否均匀
   散列函数的好坏直接影响着出现冲突的频繁程度，不过，由于不同的散列函数对同一组随机的关键字，产生冲突的可能性是相同的，因此我们可以不考虑它对平均查找长度的影响。
2. 处理冲突的方法
   相同的关键字、相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测处理冲突可能会产生堆积，显然就没有二次探测法好，而链地址法处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。
3. 散列表的装填因子
   所谓的装填因子α=填入表中的记录个数/散列表长度。α标志着散列表的装满的程度。当填入表中的记录越多，α就越大，产生冲突的可能性就越大。比如我们前面的例子，如图8-11-5所示，如果你的散列表长度是12，而填入表中的记录个数为11，那么此时的装填因子α=11/12=0.9167，再填入最后一个关键字产生冲突的可能性就非常之大。也就是说，散列表的平均查找长度取决于装填因子，而不是取决于查找集合中的记录个数。

不管记录个数n有多大，我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围之内，此时我们散列查找的时间复杂度就真的是O(1)了。为了做到这一点，通常我们都是将散列表的空间设置得比查找集合大，此时虽然是浪费了一定的空间，但换来的是查找效率的大大提升，总的来说，还是非常值得的。

8.13 总结回顾

我们这一章全都是围绕一个主题“查找”来作文章的。
首先我们要弄清楚查找表、记录、关键字、主关键字、静态查找表、动态查找表等这些概念。
然后，对于顺序表查找来说，尽管很土（简单），但它却是后面很多查找的基础，注意设置“哨兵”的技巧，可以使得本已经很难提升的简单算法里还是提高了性能。
有序查找，我们着重讲了折半查找的思想，它在性能上比原来的顺序查找有了质的飞跃，由O（n）变成了O（㏒n）。之后我们又讲解了另外两种优秀的有序查找：插值查找和斐波那契查找，三者各有优缺点，望大家要仔细体会。
线性索引查找，我们讲解了稠密索引、分块索引和倒排索引。索引技术被广泛的用于文件检索、数据库和搜索引擎等技术领域，是进一步学习这些技术的基础。
二叉排序树是动态查找最重要的数据结构，它可以在兼顾查找性能的基础上，让插入和删除也变得效率较高。不过为了达到最优的状态，二叉排序树最好是构造成平衡的二叉树才最佳。因此我们就需要再学习关于平衡二叉树（AVL树）的数据结构，了解AVL树是如何处理平衡性的问题。这部分是本章重点，需要认真学习掌握。
B树这种数据结构是针对内存与外存之间的存取而专门设计的。由于内外存的查找性能更多取决于读取的次数，因此在设计中要考虑B树的平衡和层次。我们讲解时是先通过最最简单的B树（2-3树）来理解如何构建、插入、删除元素的操作，再通过2-3-4树的深化，最终来理解B树的原理。之后，我们还介绍了B+树的设计思想。
散列表是一种非常高效的查找数据结构，在原理上也与前面的查找不尽相同，它回避了关键字之间反复比较的烦琐，而是直接一步到位查找结果。当然，这也就带来了记录之间没有任何关联的弊端。应该说，散列表对于那种查找性能要求高，记录之间关系无要求的数据有非常好的适用性。在学习中要注意的是散列函数的选择和处理冲突的方法。