**

1. 什么是查找表

**
在日常生活中，几乎每天都要进行一些查找的工作，在电话簿中查阅某个人的电话号码；在电脑的文件夹中查找某个具体的文件等等。本节主要介绍用于查找操作的数据结构——查找表。

查找表是由同一类型的数据元素构成的集合。例如电话号码簿和字典都可以看作是一张查找表。

一般对于查找表有以下几种操作：

在查找表中查找某个具体的数据元素；

在查找表中插入数据元素；

从查找表中删除数据元素；

静态查找表和动态查找表

在查找表中只做查找操作，而不改动表中数据元素，称此类查找表为静态查找表；反之，在查找表中做查找操作的同时进行插入数据或者删除数据的操作，称此类表为动态查找表。

关键字

在查找表查找某个特定元素时，前提是需要知道这个元素的一些属性。例如，每个人上学的时候都会有自己唯一的学号，因为你的姓名、年龄都有可能和其他人是重复的，唯独学号不会重复。而学生具有的这些属性（学号、姓名、年龄等）都可以称为关键字。

关键字又细分为主关键字和次关键字。若某个关键字可以唯一地识别一个数据元素时，称这个关键字为主关键字，例如学生的学号就具有唯一性；反之，像学生姓名、年龄这类的关键字，由于不具有唯一性，称为次关键字。

如何进行查找？

不同的查找表，其使用的查找方法是不同的。例如每个人都有属于自己的朋友圈，都有自己的电话簿，电话簿中数据的排序方式是多种多样的，有的是按照姓名的首字母进行排序，这种情况在查找时，就可以根据被查找元素的首字母进行顺序查找；有的是按照类别（亲朋好友）进行排序。在查找时，就需要根据被查找元素本身的类别关键字进行排序。

具体的查找方法需要根据实际应用中具体情况而定。

**

2. 顺序查找算法详解（包含C语言实现代码）

**
通过前面对静态查找表的介绍，静态查找表即为只做查找操作的查找表。

静态查找表既可以使用顺序表表示，也可以使用链表结构表示。虽然一个是数组、一个链表，但两者在做查找操作时，基本上大同小异。
本节以静态查找表的顺序存储结构为例做详细的介绍。

顺序查找的实现

静态查找表用顺序存储结构表示时，顺序查找的查找过程为：从表中的最后一个数据元素开始，逐个同记录的关键字做比较，如果匹配成功，则查找成功；反之，如果直到表中第一个关键字查找完也没有成功匹配，则查找失败。

顺序查找的具体实现代码为：

#include <stdio.h>
#include <stdlib.h>
#define keyType int
typedef struct {keyType key;//查找表中每个数据元素的值//如果需要，还可以添加其他属性
}ElemType;
typedef struct{ElemType *elem;//存放查找表中数据元素的数组int length;//记录查找表中数据的总数量
}SSTable;
//创建查找表
void Create(SSTable **st,int length){(*st)=(SSTable*)malloc(sizeof(SSTable));(*st)->length=length;(*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));printf("输入表中的数据元素：\n");//根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据for (int i=1; i<=length; i++) {scanf("%d",&((*st)->elem[i].key));}
}
//查找表查找的功能函数，其中key为关键字
int Search_seq(SSTable *st,keyType key){st->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置，起监视哨的作用int i=st->length;//从查找表的最后一个数据元素依次遍历，一直遍历到数组下标为0while (st->elem[i].key!=key) {i--;}//如果 i=0，说明查找失败；反之，返回的是含有关键字key的数据元素在查找表中的位置return i;
}
int main() {SSTable *st;Create(&st, 6);getchar();printf("请输入查找数据的关键字：\n");int key;scanf("%d",&key);int location=Search_seq(st, key);if (location==0) {printf("查找失败");}else{printf("数据在查找表中的位置为：%d",location);}return 0;
}

可运行代码中设置了一个固定长度为 6 的顺序表，例如在查找表为{1,2,3,4,5,6}找到关键字为 1 的数据元素的位置，则运行效果为：

输入表中的数据元素：

1 2 3 4 5 6

请输入查找数据的关键字：
2

数据在查找表中的位置为：2

同时，在程序中初始化创建查找表时，由于是顺序存储，所以将所有的数据元素存储在数组中，但是把第一个位置留给了用户用于查找的关键字。例如，在顺序表{1,2,3,4,5,6}中查找数据元素值为 7 的元素，则添加后的顺序表为：

图 1 顺序表中的监视哨

顺序表的一端添加用户用于搜索的关键字，称作“监视哨”。
图 1 中监视哨的位置也可放在数据元素 6 的后面（这种情况下，整个查找的顺序应有逆向查找改为顺序查找）。
放置好监视哨之后，顺序表遍历从没有监视哨的一端依次进行，如果查找表中有用户需要的数据，则程序输出该位置；反之，程序会运行至监视哨，此时匹配成功，程序停止运行，但是结果是查找失败。

顺序查找的性能分析

查找操作的性能分析主要考虑其时间复杂度，而整个查找过程其实大部分时间花费在关键字和查找表中的数据进行比较上。

所以查找算法衡量好坏的依据为：查找成功时，查找的关键字和查找表中的数据元素中进行过比较的个数的平均值，称为平均查找长度（Average Search Length，用 ASL 表示）。

例如，对于具有 n 个数据元素的查找表，查找成功的平均查找长度的计算公式为：

Pi 为第 i 个数据元素被查找的概率，所有元素被查找的概率的和为 1；Ci 表示在查找到第 i 个数据元素之前已进行过比较的次数。若表中有 n 个数据元素，查找第一个元素时需要比较 n 次；查找最后一个元素时需要比较 1 次，所以有 Ci = n – i + 1 。

一般情况，表中各数据元素被查找的概率是未知的。假设含有 n 个数据元素的查找表中，各数据被查找的概率是相同的，则：

换算后，得：

如果对于查找表中各个数据元素有可能被查找的概率提前已知，就应该根据其查找概率的大小对查找表中的数据元素进行适当的调整：被查找概率越大，离查找出发点 i 越近；反之，越远。这样可以适当的减少查找操作中的比较次数。

上边的平均查找长度是在假设查找算法每次都成功的前提下得出的。而对于查找算法来说，查找成功和查找失败的概率是相同的。所以，查找算法的平均查找长度应该为查找成功时的平均查找长度加上查找失败时的平均查找长度。

对于含有 n 个数据的表来说，每次查找失败，比较的次数都是 n+1。所以查找算法的平均查找长度的计算公式为：

总结

本节主要介绍了静态查找表的顺序存储的表示和查找算法的实现，其中使用监视哨对普通的顺序表的遍历算法做了改进，在数据量大的情况下，能够有效提高算法的运行效率。

**

3. 二分查找（折半查找）算法详解（C语言实现）

**
折半查找，也称二分查找，在某些情况下相比于顺序查找，使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。

例如，在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前，需要首先对该表中的数据按照所查的关键字进行排序：{5,13,19,21,37,56,64,75,80,88,92}。

在折半查找之前对查找表按照所查的关键字进行排序的意思是：若查找表中存储的数据元素含有多个关键字时，使用哪种关键字做折半查找，就需要提前以该关键字对所有数据进行排序。

折半查找算法

对静态查找表{5,13,19,21,37,56,64,75,80,88,92}采用折半查找算法查找关键字为 21 的过程为：

图 1 折半查找的过程（a）

如上图 1 所示，指针 low 和 high 分别指向查找表的第一个关键字和最后一个关键字，指针 mid 指向处于 low 和 high 指针中间位置的关键字。在查找的过程中每次都同 mid 指向的关键字进行比较，由于整个表中的数据是有序的，因此在比较之后就可以知道要查找的关键字的大致位置。

例如在查找关键字 21 时，首先同 56 作比较，由于21 < 56，而且这个查找表是按照升序进行排序的，所以可以判定如果静态查找表中有 21 这个关键字，就一定存在于 low 和 mid 指向的区域中间。

因此，再次遍历时需要更新 high 指针和 mid 指针的位置，令 high 指针移动到 mid 指针的左侧一个位置上，同时令 mid 重新指向 low 指针和 high 指针的中间位置。如图 2 所示：

图 2 折半查找的过程（b）

同样，用 21 同 mid 指针指向的 19 作比较，19 < 21，所以可以判定 21 如果存在，肯定处于 mid 和 high 指向的区域中。所以令 low 指向 mid 右侧一个位置上，同时更新 mid 的位置。

图 3 折半查找的过程（3）

当第三次做判断时，发现 mid 就是关键字 21 ，查找结束。
注意：在做查找的过程中，如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。

折半查找的实现代码：

#include <stdio.h>
#include <stdlib.h>
#define keyType int
typedef struct {keyType key;//查找表中每个数据元素的值//如果需要，还可以添加其他属性
}ElemType;
typedef struct{ElemType *elem;//存放查找表中数据元素的数组int length;//记录查找表中数据的总数量
}SSTable;
//创建查找表
void Create(SSTable **st,int length){(*st)=(SSTable*)malloc(sizeof(SSTable));(*st)->length=length;(*st)->elem = (ElemType*)malloc((length+1)*sizeof(ElemType));printf("输入表中的数据元素：\n");//根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据for (int i=1; i<=length; i++) {scanf("%d",&((*st)->elem[i].key));}
}
//折半查找算法
int Search_Bin(SSTable *ST,keyType key){int low=1;//初始状态 low 指针指向第一个关键字int high=ST->length;//high 指向最后一个关键字int mid;while (low<=high) {mid=(low+high)/2;//int 本身为整形，所以，mid 每次为取整的整数if (ST->elem[mid].key==key)//如果 mid 指向的同要查找的相等，返回 mid 所指向的位置{return mid;}else if(ST->elem[mid].key>key)//如果mid指向的关键字较大，则更新 high 指针的位置{high=mid-1;}//反之，则更新 low 指针的位置else{low=mid+1;}}return 0;
}
int main(int argc, const char * argv[]) {SSTable *st;Create(&st, 11);getchar();printf("请输入查找数据的关键字：\n");int key;scanf("%d",&key);int location=Search_Bin(st, key);//如果返回值为 0，则证明查找表中未查到 key 值，if (location==0) {printf("查找表中无该元素");}else{printf("数据在查找表中的位置为：%d",location);}return 0;
}

以图 1 的查找表为例，运行结果为：

输入表中的数据元素：
5 13 19 21 37 56 64 75 80 88 92
请输入查找数据的关键字：
21
数据在查找表中的位置为：4

折半查找的性能分析

折半查找的运行过程可以用二叉树来描述，这棵树通常称为“判定树”。例如图 1 中的静态查找表中做折半查找的过程，对应的判定树如图 4：

图 4 折半查找对应的判定树

注意，此图中叶子节点看似为父节点的右孩子节点，其实不然，这里的叶子节点既可以作为右孩子节点，也可以当作左孩子节点对待，都是可以的。

在判定树中可以看到，如果想在查找表中查找 21 的位置，只需要进行 3 次比较，依次和 56、19、21 进行比较，而比较的次数恰好是该关键字所在判定树中的层次（关键字 21 在判定树中的第 3 层）。

对于具有 n 个结点（查找表中含有 n 个关键字）的判定树，它的层次数至多为：log2n + 1（如果结果不是整数，则做取整操作，例如：
log211 +1 = 3 + 1 = 4 ）。

同时，在查找表中各个关键字被查找概率相同的情况下，折半查找的平均查找长度为：ASL = log2(n+1) – 1。

总结

通过比较折半查找的平均查找长度，同前面介绍的顺序查找相对比，明显折半查找的效率要高。但是折半查找算法只适用于有序表，同时仅限于查找表用顺序存储结构表示。

当查找表使用链式存储结构表示时，折半查找算法无法有效地进行比较操作（排序和查找操作的实现都异常繁琐）。

**

4. 二叉排序树（二叉查找树）及C语言实现

**
前几节介绍的都是有关静态查找表的相关知识，从本节开始介绍另外一种查找表——动态查找表。

动态查找表中做查找操作时，若查找成功可以对其进行删除；如果查找失败，即表中无该关键字，可以将该关键字插入到表中。

动态查找表的表示方式有多种，本节介绍一种使用树结构表示动态查找表的实现方法——二叉排序树（又称为“二叉查找树”）。

什么是二叉排序树？

二叉排序树要么是空二叉树，要么具有如下特点：

二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；

二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；

二叉排序树的左右子树也要求都是二叉排序树；

例如，图 1 就是一个二叉排序树：

图 1 二叉排序树

使用二叉排序树查找关键字

二叉排序树中查找某关键字时，查找过程类似于次优二叉树，在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有
3 种不同的结果：

如果相等，查找成功；

如果比较结果为根结点的关键字值较大，则说明该关键字可能存在其左子树中；

如果比较结果为根结点的关键字值较小，则说明该关键字可能存在其右子树中；

实现函数为：（运用递归的方法）

BiTree SearchBST(BiTree T,KeyType key){//如果递归过程中 T 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针if (!T || key==T->data) {return T;}else if(key<T->data){//递归遍历其左孩子return SearchBST(T->lchild, key);}else{//递归遍历其右孩子return SearchBST(T->rchild, key);}
}

二叉排序树中插入关键字

二叉排序树本身是动态查找表的一种表示形式，有时会在查找过程中插入或者删除表中元素，当因为查找失败而需要插入数据元素时，该数据元素的插入位置一定位于二叉排序树的叶子结点，并且一定是查找失败时访问的最后一个结点的左孩子或者右孩子。

例如，在图 1 的二叉排序树中做查找关键字 1 的操作，当查找到关键字 3 所在的叶子结点时，判断出表中没有该关键字，此时关键字 1 的插入位置为关键字 3 的左孩子。

所以，二叉排序树表示动态查找表做插入操作，只需要稍微更改一下上面的代码就可以实现，具体实现代码为：

BOOL SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){//如果 T 指针为空，说明查找失败，令 p 指针指向查找过程中最后一个叶子结点，并返回查找失败的信息if (!T){*p=f;return false;}//如果相等，令 p 指针指向该关键字，并返回查找成功信息else if(key==T->data){*p=T;return true;}//如果 key 值比 T 根结点的值小，则查找其左子树；反之，查找其右子树else if(key<T->data){return SearchBST(T->lchild,key,T,p);}else{return SearchBST(T->rchild,key,T,p);}
}
//插入函数
BOOL InsertBST(BiTree T,ElemType e){BiTree p=NULL;//如果查找不成功，需做插入操作if (!SearchBST(T, e,NULL,&p)) {//初始化插入结点BiTree s=(BiTree)malloc(sizeof(BiTree));s->data=e;s->lchild=s->rchild=NULL;//如果 p 为NULL，说明该二叉排序树为空树，此时插入的结点为整棵树的根结点if (!p) {T=s;}//如果 p 不为 NULL，则 p 指向的为查找失败的最后一个叶子结点，只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子else if(e<p->data){p->lchild=s;}else{p->rchild=s;}return true;}//如果查找成功，不需要做插入操作，插入失败return false;
}

通过使用二叉排序树对动态查找表做查找和插入的操作，同时在中序遍历二叉排序树时，可以得到有关所有关键字的一个有序的序列。

例如，假设原二叉排序树为空树，在对动态查找表 {3，5，7，2，1} 做查找以及插入操作时，可以构建出一个含有表中所有关键字的二叉排序树，过程如图 2 所示:

图 2 二叉排序树插入过程

通过不断的查找和插入操作，最终构建的二叉排序树如图 2（5） 所示。当使用中序遍历算法遍历二叉排序树时，得到的序列为：1 2 3 5 7 ，为有序序列。

一个无序序列可以通过构建一棵二叉排序树，从而变成一个有序序列。

二叉排序树中删除关键字

在查找过程中，如果在使用二叉排序树表示的动态查找表中删除某个数据元素时，需要在成功删除该结点的同时，依旧使这棵树为二叉排序树。

假设要删除的为结点 p，则对于二叉排序树来说，需要根据结点 p 所在不同的位置作不同的操作，有以下 3 种可能：

1、结点 p 为叶子结点，此时只需要删除该结点，并修改其双亲结点的指针即可；

2、结点 p 只有左子树或者只有右子树，如果 p 是其双亲节点的左孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的左子树；反之也是如此，如果 p 是其双亲节点的右孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的右子树；

3、结点 p 左右子树都有，此时有两种处理方式：

1）令结点 p 的左子树为其双亲结点的左子树；结点 p 的右子树为其自身直接前驱结点的右子树，如图 3 所示；

图 3 二叉排序树中删除结点（1）

2）用结点 p 的直接前驱（或直接后继）来代替结点 p，同时在二叉排序树中对其直接前驱（或直接后继）做删除操作。如图 4 为使用直接前驱代替结点 p：

图 4 二叉排序树中删除结点（2）

图 4 中，在对左图进行中序遍历时，得到的结点 p 的直接前驱结点为结点 s，所以直接用结点 s 覆盖结点 p，由于结点 s 还有左孩子，根据第 2 条规则，直接将其变为双亲结点的右孩子。

具体实现代码：（可运行）

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ElemType int
#define  KeyType int
/* 二叉排序树的节点结构定义 */
typedef struct BiTNode
{int data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//二叉排序树查找算法
int SearchBST(BiTree T, KeyType key, BiTree f, BiTree *p) {//如果 T 指针为空，说明查找失败，令 p 指针指向查找过程中最后一个叶子结点，并返回查找失败的信息if (!T) {*p = f;return FALSE;}//如果相等，令 p 指针指向该关键字，并返回查找成功信息else if (key == T->data) {*p = T;return TRUE;}//如果 key 值比 T 根结点的值小，则查找其左子树；反之，查找其右子树else if (key < T->data) {return SearchBST(T->lchild, key, T, p);}else {return SearchBST(T->rchild, key, T, p);}
}
int InsertBST(BiTree *T, ElemType e) {BiTree p = NULL;//如果查找不成功，需做插入操作if (!SearchBST((*T), e, NULL, &p)) {//初始化插入结点BiTree s = (BiTree)malloc(sizeof(BiTNode));s->data = e;s->lchild = s->rchild = NULL;//如果 p 为NULL，说明该二叉排序树为空树，此时插入的结点为整棵树的根结点if (!p) {*T = s;}//如果 p 不为 NULL，则 p 指向的为查找失败的最后一个叶子结点，只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子else if (e < p->data) {p->lchild = s;}else {p->rchild = s;}return TRUE;}//如果查找成功，不需要做插入操作，插入失败return FALSE;
}
//删除函数
int Delete(BiTree *p)
{BiTree q, s;//情况 1，结点 p 本身为叶子结点，直接删除即可if (!(*p)->lchild && !(*p)->rchild) {*p = NULL;}else if (!(*p)->lchild) { //左子树为空，只需用结点 p 的右子树根结点代替结点 p 即可；q = *p;*p = (*p)->rchild;free(q);}else if (!(*p)->rchild) {//右子树为空，只需用结点 p 的左子树根结点代替结点 p 即可；q = *p;*p = (*p)->lchild;//这里不是指针 *p 指向左子树，而是将左子树存储的结点的地址赋值给指针变量 pfree(q);}else {//左右子树均不为空，采用第 2 种方式q = *p;s = (*p)->lchild;//遍历，找到结点 p 的直接前驱while (s->rchild){q = s;s = s->rchild;}//直接改变结点 p 的值(*p)->data = s->data;//判断结点 p 的左子树 s 是否有右子树，分为两种情况讨论if (q != *p) {q->rchild = s->lchild;//若有，则在删除直接前驱结点的同时，令前驱的左孩子结点改为 q 指向结点的孩子结点}else {q->lchild = s->lchild;//否则，直接将左子树上移即可}free(s);}return TRUE;
}
int DeleteBST(BiTree *T, int key)
{if (!(*T)) {//不存在关键字等于key的数据元素return FALSE;}else{if (key == (*T)->data) {Delete(T);return TRUE;}else if (key < (*T)->data) {//使用递归的方式return DeleteBST(&(*T)->lchild, key);}else {return DeleteBST(&(*T)->rchild, key);}}
}
void order(BiTree t)//中序输出
{if (t == NULL) {return;}order(t->lchild);printf("%d ", t->data);order(t->rchild);
}
int main()
{int i;int a[5] = { 3,4,2,5,9 };BiTree T = NULL;for (i = 0; i < 5; i++) {InsertBST(&T, a[i]);}printf("中序遍历二叉排序树：\n");order(T);printf("\n");printf("删除3后，中序遍历二叉排序树：\n");DeleteBST(&T, 3);order(T);
}

运行结果：

中序遍历二叉排序树：
2 3 4 5 9
删除3后，中序遍历二叉排序树：
2 4 5 9

总结

使用二叉排序树在查找表中做查找操作的时间复杂度同建立的二叉树本身的结构有关。即使查找表中各数据元素完全相同，但是不同的排列顺序，构建出的二叉排序树大不相同。

例如：查找表 {45，24，53，12，37，93} 和表 {12，24，37，45，53，93} 各自构建的二叉排序树图下图所示：

图 5 不同构造的二叉排序树

**

5. 平衡二叉树（AVL树）及C语言实现

**
上一节介绍如何使用二叉排序树实现动态查找表，本节介绍另外一种实现方式——平衡二叉树。

平衡二叉树，又称为 AVL 树。实际上就是遵循以下两个特点的二叉树：

每棵子树中的左子树和右子树的深度差不能超过 1；

二叉树中每棵子树都要求是平衡二叉树；

其实就是在二叉树的基础上，若树中每棵子树都满足其左子树和右子树的深度差都不超过 1，则这棵二叉树就是平衡二叉树。

图 1 平衡与不平衡的二叉树及结点的平衡因子

平衡因子：每个结点都有其各自的平衡因子，表示的就是其左子树深度同右子树深度的差。平衡二叉树中各结点平衡因子的取值只可能是：0、1 和 -1。

如图 1 所示，其中 （a） 的两棵二叉树中由于各个结点的平衡因子数的绝对值都不超过 1，所以 （a） 中两棵二叉树都是平衡二叉树；而 （b） 的两棵二叉树中有结点的平衡因子数的绝对值超过 1，所以都不是平衡二叉树。

二叉排序树转化为平衡二叉树

为了排除动态查找表中不同的数据排列方式对算法性能的影响，需要考虑在不会破坏二叉排序树本身结构的前提下，将二叉排序树转化为平衡二叉树。

例如，使用上一节的算法在对查找表{13，24，37，90，53}构建二叉排序树时，当插入 13 和 24 时，二叉排序树此时还是平衡二叉树：

图 2 平衡二叉树

当继续插入 37 时，生成的二叉排序树如图 3（a），平衡二叉树的结构被破坏，此时只需要对二叉排序树做“旋转”操作（如图 3（b）），即整棵树以结点 24 为根结点，二叉排序树的结构没有破坏，同时将该树转化为了平衡二叉树：

图 3 二叉排序树变为平衡二叉树的过程

当二叉排序树的平衡性被打破时，就如同扁担的两头出现了一头重一头轻的现象，如图3（a）所示，此时只需要改变扁担的支撑点（树的树根），就能使其重新归为平衡。实际上图 3 中的 （b） 是对（a） 的二叉树做了一个向左逆时针旋转的操作。

继续插入 90 和 53 后，二叉排序树如图 4（a）所示，导致二叉树中结点 24 和 37 的平衡因子的绝对值大于 1 ，整棵树的平衡被打破。此时，需要做两步操作：

如图 4（b） 所示，将结点 53 和 90 整体向右顺时针旋转，使本该以 90 为根结点的子树改为以结点 53 为根结点；

如图 4（c） 所示，将以结点 37 为根结点的子树向左逆时针旋转，使本该以 37 为根结点的子树，改为以结点 53 为根结点；

图 4 二叉排序树转化为平衡二叉树

做完以上操作，即完成了由不平衡的二叉排序树转变为平衡二叉树。

当平衡二叉树由于新增数据元素导致整棵树的平衡遭到破坏时，就需要根据实际情况做出适当的调整，假设距离插入结点最近的“不平衡因子”为 a。则调整的规律可归纳为以下 4 种情况：
单向右旋平衡处理：若由于结点 a 的左子树为根结点的左子树上插入结点，导致结点 a 的平衡因子由 1 增至 2，致使以 a 为根结点的子树失去平衡，则只需进行一次向右的顺时针旋转，如下图这种情况：

图 5 单向右旋

单向左旋平衡处理：如果由于结点 a 的右子树为根结点的右子树上插入结点，导致结点 a 的平衡因子由 -1变为 -2，则以 a 为根结点的子树需要进行一次向左的逆时针旋转，如下图这种情况：

图 6 单向左旋

双向旋转（先左后右）平衡处理：如果由于结点 a 的左子树为根结点的右子树上插入结点，导致结点 a 平衡因子由 1 增至 2，致使以 a 为根结点的子树失去平衡，则需要进行两次旋转操作，如下图这种情况：

图 7 双向旋转（先左后右）

注意：图 7 中插入结点也可以为结点 C 的右孩子，则（b）中插入结点的位置还是结点 C 右孩子，（c）中插入结点的位置为结点 A 的左孩子。

双向旋转（先右后左）平衡处理：如果由于结点 a 的右子树为根结点的左子树上插入结点，导致结点 a 平衡因子由 -1 变为 -2，致使以 a 为根结点的子树失去平衡，则需要进行两次旋转（先右旋后左旋）操作，如下图这种情况：

图 8 双向旋转（先右后左）

注意：图 8 中插入结点也可以为结点 C 的右孩子，则（b）中插入结点的位置改为结点 B 的左孩子，（c）中插入结点的位置为结点 B 的左孩子。

在对查找表{13，24，37，90，53}构建平衡二叉树时，由于符合第 4 条的规律，所以进行先右旋后左旋的处理，最终由不平衡的二叉排序树转变为平衡二叉树。

构建平衡二叉树的代码实现

#include <stdio.h>
#include <stdlib.h>
//分别定义平衡因子数
#define LH +1
#define EH  0
#define RH -1
typedef int ElemType;
typedef enum {false,true} bool;
//定义二叉排序树
typedef struct BSTNode{ElemType data;int bf;//balance flagstruct BSTNode *lchild,*rchild;
}*BSTree,BSTNode;
//对以 p 为根结点的二叉树做右旋处理，令 p 指针指向新的树根结点
void R_Rotate(BSTree* p)
{//借助文章中的图 5 所示加以理解，其中结点 A 为 p 指针指向的根结点BSTree lc = (*p)->lchild;(*p)->lchild = lc->rchild;lc->rchild = *p;*p = lc;
}
对以 p 为根结点的二叉树做左旋处理，令 p 指针指向新的树根结点
void L_Rotate(BSTree* p)
{//借助文章中的图 6 所示加以理解，其中结点 A 为 p 指针指向的根结点BSTree rc = (*p)->rchild;(*p)->rchild = rc->lchild;rc->lchild = *p;*p = rc;
}
//对以指针 T 所指向结点为根结点的二叉树作左子树的平衡处理，令指针 T 指向新的根结点
void LeftBalance(BSTree* T)
{BSTree lc,rd;lc = (*T)->lchild;//查看以 T 的左子树为根结点的子树，失去平衡的原因，如果 bf 值为 1 ，则说明添加在左子树为根结点的左子树中，需要对其进行右旋处理；反之，如果 bf 值为 -1，说明添加在以左子树为根结点的右子树中，需要进行双向先左旋后右旋的处理switch (lc->bf){case LH:(*T)->bf = lc->bf = EH;R_Rotate(T);break;case RH:rd = lc->rchild;switch(rd->bf){case LH:(*T)->bf = RH;lc->bf = EH;break;case EH:(*T)->bf = lc->bf = EH;break;case RH:(*T)->bf = EH;lc->bf = LH;break;}rd->bf = EH;L_Rotate(&(*T)->lchild);R_Rotate(T);break;}
}
//右子树的平衡处理同左子树的平衡处理完全类似
void RightBalance(BSTree* T)
{BSTree lc,rd;lc= (*T)->rchild;switch (lc->bf){case RH:(*T)->bf = lc->bf = EH;L_Rotate(T);break;case LH:rd = lc->lchild;switch(rd->bf){case LH:(*T)->bf = EH;lc->bf = RH;break;case EH:(*T)->bf = lc->bf = EH;break;case RH:(*T)->bf = EH;lc->bf = LH;break;}rd->bf = EH;R_Rotate(&(*T)->rchild);L_Rotate(T);break;}
}
int InsertAVL(BSTree* T,ElemType e,bool* taller)
{//如果本身为空树，则直接添加 e 为根结点if ((*T)==NULL){(*T)=(BSTree)malloc(sizeof(BSTNode));(*T)->bf = EH;(*T)->data = e;(*T)->lchild = NULL;(*T)->rchild = NULL;*taller=true;}//如果二叉排序树中已经存在 e ，则不做任何处理else if (e == (*T)->data){*taller = false;return 0;}//如果 e 小于结点 T 的数据域，则插入到 T 的左子树中else if (e < (*T)->data){//如果插入过程，不会影响树本身的平衡，则直接结束if(!InsertAVL(&(*T)->lchild,e,taller))return 0;//判断插入过程是否会导致整棵树的深度 +1if(*taller){//判断根结点 T 的平衡因子是多少，由于是在其左子树添加新结点的过程中导致失去平衡，所以当 T 结点的平衡因子本身为 1 时，需要进行左子树的平衡处理，否则更新树中各结点的平衡因子数switch ((*T)->bf){case LH:LeftBalance(T);*taller = false;break;case  EH:(*T)->bf = LH;*taller = true;break;case RH:(*T)->bf = EH;*taller = false;break;}}}//同样，当 e>T->data 时，需要插入到以 T 为根结点的树的右子树中，同样需要做和以上同样的操作else{if(!InsertAVL(&(*T)->rchild,e,taller))return 0;if (*taller){switch ((*T)->bf){case LH:(*T)->bf = EH;*taller = false;break;case EH:(*T)->bf = RH;*taller = true;break;case  RH:RightBalance(T);*taller = false;break;}}}return 1;
}
//判断现有平衡二叉树中是否已经具有数据域为 e 的结点
bool FindNode(BSTree root,ElemType e,BSTree* pos)
{BSTree pt = root;(*pos) = NULL;while(pt){if (pt->data == e){//找到节点，pos指向该节点并返回true(*pos) = pt;return true;}else if (pt->data>e){pt = pt->lchild;}elsept = pt->rchild;}return false;
}
//中序遍历平衡二叉树
void InorderTra(BSTree root)
{if(root->lchild)InorderTra(root->lchild);printf("%d ",root->data);if(root->rchild)InorderTra(root->rchild);
}
int main()
{int i,nArr[] = {1,23,45,34,98,9,4,35,23};BSTree root=NULL,pos;bool taller;//用 nArr查找表构建平衡二叉树（不断插入数据的过程）for (i=0;i<9;i++){InsertAVL(&root,nArr[i],&taller);}//中序遍历输出InorderTra(root);//判断平衡二叉树中是否含有数据域为 103 的数据if(FindNode(root,103,&pos))printf("\n%d\n",pos->data);elseprintf("\nNot find this Node\n");return 0;
}

运行结果

1 4 9 23 34 35 45 98
Not find this Node  

总结

使用平衡二叉树进行查找操作的时间复杂度为 O(logn)。在学习本节内容时，紧贴本节图示比较容易理解。

**

6. 哈希表（散列表）详解（包含哈希表处理冲突的方法）

**
前面介绍了静态查找表以及动态查找表中的一些查找方法，其查找的过程都无法避免同查找表中的数据进行比较，查找算法的效率很大程度取决于同表中数据的查找次数。

而本节所介绍的哈希表可以通过关键字直接找到数据的存储位置，不需要进行任何的比较，其查找的效率相较于前面所介绍的查找算法是更高的。

哈希表的构建

在初中的数学课本中学习过函数的相关知识，给定一个 x，通过一个数学公式，只需要将 x 的值带入公式就可以求出一个新的值 y。

哈希表的建立同函数类似，把函数中的 x 用查找记录时使用的关键字来代替，然后将关键字的值带入一个精心设计的公式中，就可以求出一个值，用这个值来表示记录存储的哈希地址。即：

数据的哈希地址=f（关键字的值）
哈希地址只是表示在查找表中的存储位置，而不是实际的物理存储位置。f（）是一个函数，通过这个函数可以快速求出该关键字对应的的数据的哈希地址，称之为“哈希函数”。

例如，这里有一个电话簿（查找表），电话簿中有 4 个人的联系方式：

张三 13912345678
李四 15823457890
王五 13409872338
赵六 13805834722

假如想查找李四的电话号码，对于一般的查找方式最先想到的是从头遍历，一一比较。而如果将电话簿构建成一张哈希表，可以直接通过名字“李四”直接找到电话号码在表中的位置。

在构建哈希表时，最重要的是哈希函数的设计。例如设计电话簿案例中的哈希函数为：每个名字的姓的首字母的 ASCII 值即为对应的电话号码的存储位置。这时会发现，张三和赵六两个关键字的姓的首字母都是 Z ，最终求出的电话号码的存储位置相同，这种现象称为冲突。在设计哈希函数时，要尽量地避免冲突现象的发生。
对于哈希表而言，冲突只能尽可能地少，无法完全避免。

哈希函数的构造
常用的哈希函数的构造方法有 6 种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。

直接定址法：其哈希函数为一次函数，即以下两种形式：
H（key）= key 或者 H（key）=a * key + b
其中 H（key）表示关键字为 key 对应的哈希地址，a 和 b 都为常数。

例如有一个从 1 岁到 100 岁的人口数字统计表，如表 1 所示：

表 1 人口统计表

假设其哈希函数为第一种形式，其关键字的值表示最终的存储位置。若需要查找年龄为 25 岁的人口数量，将年龄 25 带入哈希函数中，直接求得其对应的哈希地址为 25（求得的哈希地址表示该记录的位置在查找表的第 25 位）。

数字分析法:如果关键字由多位字符或者数字组成，就可以考虑抽取其中的 2 位或者多位作为该关键字对应的哈希地址，在取法上尽量选择变化较多的位，避免冲突发生。

例如表 2 中列举的是一部分关键字，每个关键字都是有 8 位十进制数组成：

表 2

通过分析关键字的构成，很明显可以看到关键字的第 1 位和第 2 位都是固定不变的，而第 3 位不是数字 3 就是 4，最后一位只可能取 2、7 和 5，只有中间的 4 位其取值近似随机，所以为了避免冲突，可以从 4 位中任意选取 2 位作为其哈希地址。

平方取中法是对关键字做平方操作，取中间得几位作为哈希地址。此方法也是比较常用的构造哈希函数的方法。

例如关键字序列为{421，423，436}，对各个关键字进行平方后的结果为{177241，178929，190096}，则可以取中间的两位{72，89，00}作为其哈希地址。

折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。此方法适合关键字位数较多的情况。

例如，在图书馆中图书都是以一个 10 位的十进制数字为关键字进行编号的，若对其查找表建立哈希表时，就可以使用折叠法。

若某书的编号为：0-442-20586-4，分割方式如图 1 中所示，在对其进行折叠时有两种方式：一种是移位折叠，另一种是间界折叠：
移位折叠是将分割后的每一小部分，按照其最低位进行对齐，然后相加，如图 1（a）；

间界折叠是从一端向另一端沿分割线来回折叠，如图 1（b）。

图 1 移位折叠和间界折叠

除留余数法：若已知整个哈希表的最大长度 m，可以取一个不大于 m 的数 p，然后对该关键字 key 做取余运算，即：H（key）= key % p。
在此方法中，对于 p 的取值非常重要，由经验得知 p 可以为不大于 m 的质数或者不包含小于 20 的质因数的合数。

随机数法：是取关键字的一个随机函数值作为它的哈希地址，即：H（key）=random（key），此方法适用于关键字长度不等的情况。

注意：这里的随机函数其实是伪随机函数，随机函数是即使每次给定的 key 相同，但是 H（key）都是不同；而伪随机函数正好相反，每个 key 都对应的是固定的 H（key）。

如此多的构建哈希函数的方法，在选择的时候，需要根据实际的查找表的情况采取适当的方法。通常考虑的因素有以下几方面：

关键字的长度。如果长度不等，就选用随机数法。如果关键字位数较多，就选用折叠法或者数字分析法；反之如果位数较短，可以考虑平方取中法；

哈希表的大小。如果大小已知，可以选用除留余数法；

关键字的分布情况；

查找表的查找频率；

计算哈希函数所需的时间（包括硬件指令的因素）

处理冲突的方法

对于哈希表的建立，需要选取合适的哈希函数，但是对于无法避免的冲突，需要采取适当的措施去处理。

通常用的处理冲突的方法有以下几种：

开放定址法 H（key）=（H（key）+ d）MOD m（其中 m 为哈希表的表长，d 为一个增量） 当得出的哈希地址产生冲突时，选取以下 3 种方法中的一种获取 d 的值，然后继续计算，直到计算出的哈希地址不在冲突为止，这 3 种方法为：

线性探测法：d=1，2，3，…，m-1

二次探测法：d=12，-12，22，-22，32，…

伪随机数探测法：d=伪随机数

例如，在长度为 11 的哈希表中已填写好 17、60 和 29 这 3 个数据（如图 2（a） 所示），其中采用的哈希函数为：H（key）=key MOD 11，现有第 4 个数据 38 ，当通过哈希函数求得的哈希地址为 5，与 60 冲突，则分别采用以上 3 种方式求得插入位置如图 2（b）所示：

图 2 开放定址法

注释：在线性探测法中，当遇到冲突时，从发生冲突位置起，每次 +1，向右探测，直到有空闲的位置为止；二次探测法中，从发生冲突的位置起，按照 +12，-12，+22，…如此探测，直到有空闲的位置；伪随机探测，每次加上一个随机数，直到探测到空闲位置结束。

再哈希法

当通过哈希函数求得的哈希地址同其他关键字产生冲突时，使用另一个哈希函数计算，直到冲突不再发生。

链地址法

将所有产生冲突的关键字所对应的数据全部存储在同一个线性链表中。例如有一组关键字为{19,14,23,01,68,20,84,27,55,11,10,79}，其哈希函数为：H(key)=key MOD 13，使用链地址法所构建的哈希表如图 3 所示：

图 3 链地址法构建的哈希表
建立一个公共溢出区
建立两张表，一张为基本表，另一张为溢出表。基本表存储没有发生冲突的数据，当关键字由哈希函数生成的哈希地址产生冲突时，就将数据填入溢出表。

总结

本节主要介绍了哈希表的构造及其在构造过程中对产生的冲突进行处理的方法。在选择具体使用哪种方法时，要根据查找表的实际情况具体问题具体分析。