查找：查找(Searching)就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

一、概论

查找表(Search Table) 是由同一类型的数据元素(或记录)构成的集合。
关键字(Key) 是数据元素中某个数据项的值，又称为键值，用它可以标识一个记录的某个数据项（字段），我们称为关键码。
主关键字(Primary Key)，若关键字可以唯一地标识一个记录，则称此关键字为主关键字(Primary Key)注意这也就意味着，对不同的记录，其主关键字均不相同。主关键字所在的数据项称为主关键码。
那么对于那些可以识别多个数据元素(或记录)的关键字，我们称为次关键字(Secondary Key)，那么对于那些可以识别多个数据元素(或记录)的关键字，我们称为次关键字(Secondary Key)。

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

若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。
查找表按照操作方式来分有两大种:静态查找表和动态查找表。
静态查找表(StaticSearchTable):只作查找操作的查找表。
它的主要操作有:

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

动态查找表(DynamicSearch Tabke):在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。动态查找表的操作就是两个：

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

为了提高查找的效率，我们需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。

从逻辑上来说，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。可是要想获得较高的查找性能，我们就不能不改变数据元素之间的关系，在存储时可以将查找集合组织成表、树等结构。

二、顺序表查找

试想一下，要在散落的一大堆书中找到你需要的那本有多么麻烦。碰到这种情况的人大都会考虑做一件事，那就是把这些书排列整齐，比如竖起来放置在书架上，这样根据书名，就很容易查找到需要的图书，如图所示。

散落的图书可以理解为一个集合，而将它们排列整齐，就如同是将此集合构造成一个线性表。我们要针对这一线性表进行查找操作，因此它就是静态查找表。
顺序查找(SequentialSearch)又叫线性查找，是最基本的查找技术，它的查找过程是:从表中第一个(或最后一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录;如果直到最后一个(或第一个)记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

2.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;
}

2.2 顺序表查找算法优化

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

/* 有哨兵的顺序查找算法 */
int Sequential_Search2(int *a,int n,int key)
{
	int i;
	a[0]=key;  /* 设置a[0]为关键字值，我们称之为“哨兵” */
	i=n;       /* 循环从数组尾部开始 */
	while(a[i]!=key)
	{
		i--;
	}
	return i;  /* 返回0则说明查找失败 */
}

此时代码是从尾部开始查找，由于 a[0]=key，也就是说，如果在a[i]中有key则返回i值，查找成功。否则一定在最终的a[0]处等于key，此时返回的是0，即说明a[1]~a[n]中没有关键字key,查找失败。
这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。当然，“哨兵”也不一定就一定要在数组开始，也可以在末端。
对于这种顺序查找算法来说，查找成功最好的情况就是在第一个位置就找到了算法时间复杂度为 O(1)，最坏的情况是在最后一位置才找到，需要n次比较，时间复杂度为 O(n)，当查找不成功时，需要n+1次比较，时间复杂度为O(n)。我们之前推导过，关键字在任何一位置的概率是相同的，所以平均查找次数为(n+1)/2，所以最终时间复杂度还是 O(n)。
很显然，顺序查找技术是有很大缺点的，n很大时，查找效率极为低下，不过优点也是有的，这个算法非常简单，对静态查找表的记录没有任何要求，在一些小型数据的查找时，是可以适用的。
另外，也正由于查找概率的不同，我们完全可以将容易查找到的记录放在前面而不常用的记录放置在后面，效率就可以有大幅提高。

三、有序表查找

如果我们在整理书架时，将图书按照书名的拼音排序放置，那么要找到某一本书就相对容易了。说白了，就是对图书做了有序排列，一个线性表有序时，对于查找总是很有帮助的。

3.1 折半查找

我们在讲树结构的二叉树定义时，曾经提到过一个小游戏，我在纸上已经写好了一个100以内的正整数数字请你猜，问几次可以猜出来，当时已经介绍了如何最快猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找，如图所示。

折半查找(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;
}

1. 程序开始运行，参数a={0,1,16,24,35,47,59,62,73,88,99}，n=10，key=62，第3~5行，此时low=1，high=10，如图所示。
   
2. 第 6~15 行循环，进行查找。
3. 第8行，mid计算得5，由于a[5]=47<key，所以执行了第12行，low=5+1=6，如图所示。
   
4. 再次循环，mid=(6+10)/2=8，此时a[8]=73>key，所以执行第10行，high=8-1=7，如图所示。
   
5. 再次循环，mid=(6+7)/2=6，此时a[6]=59<key，所以执行12行，low=6+1=7，如图所示。
   
6. 再次循环，mid=(7+7)/2=7，此时a[7]=62=key，查找成功，返回7。
   该算法还是比较容易理解的，同时我们也能感觉到它的效率非常高。但到底高多少?关键在于此算法的时间复杂度分析。
   首先，我们将这个数组的查找过程绘制成一棵二叉树，如图所示，从图上就可以理解，如果查找的关键字不是中间记录 47的话，折半查找等于是把静态有序查找表分成了两棵子树，即查找结果只需要找其中的一半数据记录即可，等于工作量少了一半，然后继续折半查找，效率当然是非常高了。
   
   二叉树性质4，有过对"具有n个结点的完全二叉树的深度为[log2N]+1"，可以推断出最坏情况是查到关键字或者查找失败的次数为[log2N]+1。
   折半查找算法的时间复杂度为O(logn)，它显然远好于顺序查找的O(n)时间复杂度。
   不过由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

3.2 插值查找

改进折半查找的方案：

mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]);  //插值

就得到了另一种有序表查找算法，插值查找法。插值插值（Interpolation Search）是根据要查找的关键字Key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于计算公式。
但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。但是对于极端不均匀的数据，用插值法不一定合适。

3.3 斐波那契查找

斐波那契查找，利用黄金分割原理进行查找。

int Fibonacci_Search(int *a,int n,int key)
{
	int low,high,mid,i,k;
	low=1;  // 定义最低下标为记录首位
	high=n;  // 定义最高下标为记录末位
	k=0;
	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;  //最高下标调整到分隔下标mid-l处
			k = k-1;    //斐波那契数列下标减一位
		}
		else if(key>a[mid]) //若查找记录大于当前分隔记录
		{
			low=mid+1;  //最低下标调整到分隔下标mid+l处
			k=k-2;  //斐波那契数列下标减2位
		}
		else
		{
			if(mid <= n)
				return mid;  //若相等则说明mid即为查找的位置
			else
				return n;  //若mid>n说明是补全数组值
		}
	}
}

1. 程序开始运行，参数 a={0,1,16,24,35,47,59,62,73,88,99}，n=10，要查找的关键字 key=59。注意此时我们已经有了事先计算好的全局变量数组F的具体数据，它是斐波那契数列，F=(0,1,1,2,3,5,8,13,21,…}。
   
2. 第6~8行是计算当前的n处于斐波那契数列的位置。现在=10，F[6]<n<F[7]，所以计算得出 k=7。
3. 第9~10行，由于 k=7，计算时是以F[7]=13为基础，而a中最大的仅是a[10]，后面的 a[11]，a[12]均未赋值，这不能构成有序数列，因此将它们都赋值为最大的数组值，所以此时 a[11]=a[12]=a[10]=99(此段代码作用后面还有解释)。
4. 第11~31行查找正式开始。
5. 第13行，mid=1+F[7-1]-1-8，也就是说，我们第一个要对比的数值是从下标为8开始的。
6. 由于此时key=59 而a[8]=73，因此执行第16~17 行，得到 high=7，k=6。
   
7. 再次循环，mid=1+F[6-1]-1=5。此时 a[5]=47<key，因此执行第 21~22行，得到 low=6，k=6-2=4。注意此时k下调2个单位。
   
8. 再次循环，mid=6+F[4-1]-1=7。此时a[7]=62>key，因此执行第 16~17行，得到 high=6，k=4-1=3。
   
9. 再次循环，mid=6+F[3-1]-1=6。此时 a[6]=59=key，因此执行第 26~27行，得到返回值为 6。程序运行结束。
   如果 key=99，此时查找循环第一次时，mid=8 与上例是相同的，第二次循环时mid=11，如果 a[11]没有值就会使得与 key 的比较失败，为了避免这样的情况出现，第 9~10 行的代码就起到这样的作用。

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

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个;
   

四、线性索引查找

我们前面讲的几种比较高效的查找方法都是基于有序的基础之上的，但事实上，很多数据集可能增长非常快，例如，某些微博网站或大型论坛的帖子和回复总数每天都是成百万上千万条，如图所示，或者一些服务器的日志信息记录也可能是海量数据，要保证记录全部是按照当中的某个关键字有序，其时间代价是非常高昂的，所以这种数据通常都是按先后顺序存储。
那么对于这样的查找表，我们如何能够快速查找到需要的数据呢?办法就是索引。
数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。
索引按照结构可以分为线性索引、树形索引和多级索引。我们这里就只介绍线性索引技术。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。我们重点介绍三种线性索引:稠密索引、分块索引和倒排索引。

4.1 稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。

对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。
索引项有序也就意味着，我们要查找关键字时，可以用到折半、插值、斐波那契等有序查找算法，大大提高了效率。

4.2 分块索引

稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。
分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件:

• 块内无序，即每一块内的记录不要求有序。当然，你如果能够让块内有序对查找来说更理想，不过这就要付出大量时间和空间的代价，因此通常我们不要求块内有序。
• 块间有序，例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字……因为只有块间有序，才有可能在查找时带来效率。
  对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。如图所示，我们定义的分块索引的索引项结构分三个数据项:
• 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大;
• 存储了块中的记录个数，以便于循环时使用;
• 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。
  
  在分块索引表中查找，就是分两步进行:

1. 在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的因此很容易利用折半、插值等算法得到结果。例如，在图8-5-4的数据集中查找62，我们可以很快可以从左上角的索引表中由57<62<96得到62在第三个块中。
2. 根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。
   分析一下分块索引的平均查找长度，设n个记录的数据集被平分为m块，每个块中有t个记录，显然n=mxt，或者说m=n/t。再假设Lb为查找索引表的平均查找长度，因最好与最差的等概率原则，所以Lb的平均长度为(m+1)/2。Lw为块中查找记录的平均查找长度，同理可知它的平均查找长度为(t+1)/2。
   
   注意上面这个式子的推导是为了让整个分块索引查找长度依赖n和t两个变量。从这里了我们也就得到，平均长度不仅仅取决于数据集的总记录数n，还和每一个块的记录个数t相关。最佳的情况就是分的块数m与块中的记录数t相同，此时意味着
   即，。
   可见，分块索引的效率比之顺序查找的 O(n)是高了不少，不过显然它与折半查找的 O(logn)相比还有不小的差距。因此在确定所在块的过程中，由于块间有序，所以可以应用折半、插值等手段来提高效率。
   总的来说，分块索引在兼顾了对细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据库表查找等技术的应用当中。

4.3 倒排索引

最基础的搜索技术——倒排索引
实现原理就是索引表，索引项的通用结构是：

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

五、二叉排序树

有没有一种即可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法呢?还真有。
这样我们就得到了一棵二叉树，并且当我们对它进行中序遍历时，就可以得到一个有序的序列{35,37,47,51,58,62,73,88,93,99}，所以我们通常称它为二叉排序树。
二叉排序树(Binary Sort Tree)，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值;
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值;
• 它的左、右子树也分别为二叉排序树。
  从二叉排序树的定义也可以知道，它前提是二叉树，然后它采用了递归的定义方法，再者，它的结点间满足一定的次序关系，左子树结点一定比其双亲结点小，右子树结点一定比其双亲结点大。
  构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二又排序树这种非线性的结构，也有利于插入和删除的实现。

5.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);  /* 在右子树继续查找 */
}

1. SearchBST 函数是一个可递归运行的函数，函数调用时的语句为SearchBST(T,93,NULL,P)，参数T是一个二叉链表，其中数据如图所示，key 代表要查找的关键字，目前我们打算查找93，二叉树f指向T的双亲，当T指向根结点时，f的初值就为 NULL，它在递归时有用，最后的参数p是为了查找成功后可以得到查找到的结点位置。
   
2. 第 3~7行，是用来判断当前二叉树是否到叶子结点，显然图告诉我们当前T指向根结点 62 的位置，T 不为空，第5~6 行不执行。
3. 第 8~12 行是查找到相匹配的关键字时执行语句，显然93≠62，第10~11行不执行。
4. 第 13~14 行是当要查找关键字小于当前结点值时执行语句，由于93>62，第14 行不执行。
5. 第 15~16 行是当要查找关键字大于当前结点值时执行语句，由于93>62，所以递归调用 SearchBST(T->rchikd,key,T,p)。此时T指向了62 的右孩子 88,如下图所示。
   
6. 此时第二层SearchBST，因93比88大，所以执行第16行，再次递归调用SearchBST(T->rchild,key,T,p)。此时T指向了88的右孩子99，如图所示。
   
7. 第三层的SearchBST，因93比99小，所以执行第14行，递归调用SearchBST(T->lchild,key,T,p)。此时T指向了99的左孩子 93，如图所示。
   
8. 第四层 SearchBST，因 key 等于 T->data，所以执行第10~11 行，此时指针p指向 93所在的结点，并返回True 到第三层、第二层、第一层，最终函数返回 True 。

5.2 二叉排序树插入操作

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

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

这段代码非常简单。如果你调用函数是“InsertBST(T，93);"，那么结果就是FALSE，如果是“InsertBST(T，95);"，那么一定就是在93的结点增加一个右孩子95，并且返回 True。如图所示。

有了二叉排序树的插入代码，我们要实现二又排序树的构建就非常容易了。下面的代码就可以创建一棵树。

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]);
}

5.3 二叉排序树删除操作

对于二叉排序树的删除，需要在不能改变二叉排序树的特性的前提下删除结点，会存在多种情况。
如果需要查找并删除如 37、51、73、93 这些二叉排序树中的叶子的结点，那很简单，因为删除它们不影响整个二叉排序树。

对于要删除的结点只有左子树或者只有右子树的情况，相对也比较好解决的，可以理解为子承父业。比如下图，先删除35和99，再删除58结点的变化图，最终整个树还是一颗二叉排序树。

但是对于要删除的结点既有左子树又有右子树该怎么办？
如图47结点删除了，它的两个儿子及子孙怎么办？

如图，我们可以发现可以使用37和48替代47，此时删除47之后，整个二叉排序树没有发生本质改变。
为什么是37和48，因为在中序遍历后的所有结点序列中37和48分别在47左右，正好是47的直接前驱和后继。
因此，比较好的办法就是，找到需要删除的结点p的直接前驱或者后继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方法的代码：

Status Delete(BiTree *p)
{
	BiTree 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)  /* 转左，然后向右到尽头（找到待删结点的前驱） */
		{
			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;
}

1. 程序开始执行，代码第4~7行目的是为了删除没有右子树只有左子树的结点。此时只需将此结点的左孩子替换它自己，然后释放此结点内存，就等于删除了。
2. 代码第 8~11行是同样的道理处理只有右子树没有左子树的结点删除问题。
3. 第 12~25 行处理复杂的左右子树均存在的问题。
4. 第14行，将要删除的结点p赋值给临时的变量q，再将p的左孩子p->lchild赋值给临时的变量s。此时q指向47结点，s指向 35 结点，如图所示。
   
5. 第15~18行，循环找到左子树的右结点，直到右侧尽头。就当前例子来说就是让q指向35，而s指向了37这个再没有右子树的结点，如图所示。
   
6. 第19行，此时让要删除的结点p的位置的数据被赋值为s->data，即让p->data=37，如图所示。
   
7. 第20~23 行，如果p和q指向不同，则将s->Ichild 赋值给 q->rchild，否则就是将 s->lchild 赋值给 q->lchild。显然这个例子p不等于q，将 s->lchild 指向的36 赋值给 q->rchild，也就是让 q->rchild 指向 36 结点，如图所示。
   
8. 第24行，free(s)，就非常好理解了，将 37 结点删除，如图所示
   
   从这段代码也可以看出，我们其实是在找删除结点的前驱结点替换的方法，对于用后继结点来替换，方法上是一样的，两种不同的策略而已。

5.4 二叉排序树总结

总之，二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即根结点就是要找的结点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。
例如{62,88,58,47,35,73,51,99,37,93}这样的数组，我们可以构建如图 8-6-18 左图的二叉排序树。但如果数组元素的次序是从小到大有序，如{35,37,47,51,58,62,73,8893,99}，则二叉排序树就成了极端的右斜树，注意它依然是一棵二叉排序树，如图的右图。此时，同样是查找结点 99，左图只需要两次比较，而右图就需要10次比较才可以得到结果，二者差异很大。

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为log2n+1，那么查找的时间复杂也就为O(logn)，近似于折半查找，事实上，左图也不够平衡，明显的左重右轻。
不平衡的最坏情况就是像右图的斜树，查找时间复杂度为O(n)，这等同于顺序查找。
因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。这样我们就引申出另一个问题，如何让二叉排序树平衡的问题。

5.5 平衡二叉树（AVL树）

平衡二叉树(Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree)，是一种高度平衡的二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(BalanceFactor)，那么平衡一叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。下图 ，当新插入结点 37 时，距离它最近的平衡因子绝对值超过1的结点是 58(即它的左子树高度2减去右子树高度0)，所以从 58 开始以下的子树为最小不平衡子树。

5.5.1 平衡二叉树实现原理

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
为了能在讲解算法时轻松一些，我们先讲一个平衡二叉树构建过程的例子。假设我们现在有一个数组 a[10]={3,2,1,4,5,6,7,10,9,8}需要构建二叉排序树。在没有学习平衡二叉树之前，根据二叉排序树的特性，我们通常会将它构建成如图1所示的样子。虽然它完全符合二叉排序树的定义，但是对这样高度达到8的二叉树来说，查找是非常不利的。我们更期望能构建成如图2的样子，高度为4的二叉排序树才可以提供高效的查找效率。那么现在我们就来研究如何将一个数组构建出图2的树结构。

对于数组 a[10]={3,2,1,4,5,6,7,10,9,8}的前两位3和2，我们很正常地构建，到了第3 个数“1”时，发现此时根结点“3”的平衡因子变成了 2，此时整棵树都成了最小不平衡子树，因此需要调整，如下图1(结点左上角数字为平衡因子BF值)。因为BF值为正，因此我们将整个树进行右旋(顺时针旋转)，此时结点2成了根结点，3成了2的右孩子，这样三个结点的BF值均为0，非常的平衡，如下图 2 所示。


然后我们再增加结点4，平衡因子没发生改变，如图3。增加结点5时，结点3的 BF值为-2，说明要旋转了。由于BF 是负值，所以我们对这棵最小平衡子树进行左旋(逆时针旋转)，如图4，此时我们整个树又达到了平衡。
继续，增加结点6时，发现根结点2的BF值变成了一2，如图6。所以我们对根结点进行了左旋，注意此时本来结点3是4的左孩子，由于旋转后需要满足二叉排序树特性，因此它成了结点2的右孩子，如图7。增加结点7，同样的左旋转，使得整棵树达到平衡，如图8和图9所示。

当增加结点 10 时，结构无变化，如图10。再增加结点9，此时结点7的 BF 变成了-2，理论上我们只需要旋转最小不平衡子树 7、9、10 即可，但是如果左旋转后，结点9就成了10的右孩子，这是不符合二叉排序树的特性的，此时不能简单的左旋，如图11所示。

仔细观察图 11，发现根本原因在于结点7的BF是-2，而结点10的BF是1，也就是说，它们俩一正一负，符号并不统一，而前面的几次旋转，无论左还是右旋，最小不平衡子树的根结点与它的子结点符号都是相同的。这就是不能直接旋转的关键。那怎么办呢?
不统一，不统一就把它们先转到符号统一再说，于是我们先对结点9和结点10进行右旋，使得结点10成了9的右子树，结点9的BF为-1，此时就与结点7的BF 值符号统一了，如图12所示。
这样我们再以结点7为最小不平衡子树进行左旋，得到图13。接着插入8，情况与刚才类似，结点6的BF是-2，而它的右孩子9的BF是1，如图14，因此首先以9为根结点，进行右旋，得到图15，此时结点6和结点7的号都是负，再以6为根结点左旋，最终得到最后的平衡二叉树，如图16所示。

5.5.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成为根结点。这样就完成了一次右旋操作，如图所示。图中三角形代表子树，N代表新增结点。

左旋操作代码如下：

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

这段代码与右旋代码是对称的，在此不做解释了。上面例子中的新增结点5、6、7，都是左旋操作。现在我们来看左平衡旋转处理的函数代码。

#define LH +1  /* 左高 */
#define EH 0   /* 等高 */
#define RH -1  /* 右高 */
/* 对以指针里所指结点为根的二叉树作左平衡旋转处理,本算法结束时，指针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:  /* 新结点插入在里的左孩子的右子树上，要作双旋处理 */
			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行，进行右旋操作。
5. 当L的平衡因子为RH，即为-1时，表明它与根结点的BF值符号相反，此时需要做双旋处理。第13~22行，针对L的右孩子Lr的BF 作判断，修改根结点T和L的BF值。第24行将当前L的BF改为0。
6. 第 25 行，对根结点的左子树进行左旋。
7. 第 26 行，对根结点进行右旋，如图的第三图所示，完成平衡操作。
   
   同样的，右平衡旋转处理的函数代码非常类似，直接看代码，不做讲解了我们前面例子中的新增结点9和8就是典型的右平衡旋转，并且双旋完成平衡的例子。
   有了这些准备，我们的主函数才算是正式登场了。

/* 若在平衡的二叉排序树!中不存在和e有相同关键字的结点，则插入一个,数据元素为e的新结点并返回1，否则返回0。若因插入而使二叉排序树,失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 */
Status InsertAVL(BiTree *T, int e,Status *taller)
{
	if(!*T)
	{  /* 插入新结点，树“长高”，置traller为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;
}

1. 程序开始执行时，第3~10 行是指当前T为空时，则申请内存新增一个结点。
2. 第 13~17 行表示当存在相同结点，则不需要插入。
3. 第18~40行，当新结点e小于T的根结点值时，则在T的左子树查找。
4. 第 20~21行，递归调用本函数，直到找到则返回false，否则说明插入结点成功，执行下面语句。
5. 第22~39 行，当taller 为TRUE 时，说明插入了结点，此时需要判断T的平衡因子，如果是1，说明左子树高于右子树，需要调用LeftBalance 函数进行左平衡旋转处理。如果为 0或-1，则说明新插入结点没有让整棵二叉排序树失去平衡性，只需要修改相关的 BF 值即可。
6. 第41~63行，说明新结点e大于T的根结点的值，在T的右子树查找。代码上述类似，不再详述。
   对于这段代码来说，我们只需要在需要构建平衡二叉树的时候执行如下列代码即可在内存中生成一棵平衡的二叉树。

int i;
int a[10]={3,2,1,4,5,6,7,10,9,8};
BiTree T=NULL;
Status taller;
for(i=0;i<10;i++)
{
	InsertAVL(&T,a[i],&taller);
}

如果我们需要查找的集合本身没有顺序，在频繁查找的同时也需要经常的插入和删除操作，显然我们需要构建一棵二叉排序树，但是不平衡的二叉排序树，查找效率是非常低的，因此我们需要在构建时，就让这棵二叉排序树是平衡二叉树，此时我们的查找时间复杂度就为 O(logn)，而插入和删除也为O(logn)。这显然是比较理想的种动态查找表算法。

六、多路查找树(B树)

一个结点只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大(结点拥有子树的个数的最大值)，要么树的高度非常大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多，这显然成了时间效率上的瓶颈，这迫使我们要打破每一个结点只存储一个元素的限制，为此引入了多路查找树的概念。
多路查找树(muitlway search tee)，其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
在这里，每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的。为此，我们讲解它的4种特殊形式:2-3树、2-3-4树、B 树和 B+树。

6.1 2-3树

2-3树是这样的一棵多路查找树:其中的每-一个结点都具有两个孩子(我们称它为2结点)或三个孩子(我们称它为3结点)。
一个2结点包含一个元素和两个孩子(或没有孩子)，且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个2结点要么没有孩子，要有就有两个，不能只有一个孩子。
一个3结点包含一小一大两个元素和三个孩子(或没有孩子)，一个3结点要么没有孩子，要么具有3个孩子。如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
并且 2-3 树中所有的叶子都在同一层次上。如图所示，就是一棵有效的2-3 树。
事实上，2-3 树复杂的地方就在于新结点的插入和已有结点的删除。毕竟，每个结点可能是2结点也可能是3结点，要保证所有叶子都在同一层次，是需要进行一番复杂操作的。

1. 2-3 树的插入实现

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

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

第一种情况，见图，需要向左图中插入元素5。经过遍历可得到元素5比8小比4大，因此它应该是需要插入在拥有6、7 元素的3结点位置。问题就在于，6和7结点已经是3结点，不能再加。此时发现它的双亲结点4是个2结点，因此考虑让它升级为3结点，这样它就得有三个孩子，于是就想到，将6、7结点拆分，让6与4结成3结点，将5成为它的中间孩子，将7成为它的右孩子，如图的右图所示。

另一种情况，如图所示，需要向左图中插入元素11。经过遍历可得到元素11比12、14 小比 9、10大，因此它应该是需要插入在拥有 9、10 元素的3结点位置。同样道理，9和10结点不能再增加结点。此时发现它的双亲结点12、14也是一个3结点，也不能再插入元素了。再往上看，12、14结点的双亲，结点8是个2结点。于是就想到，将9、10拆分，12、14也拆分，让根结点8升级为3结点，最终形成如右图样子。

再来看个例子，如图所示，需要在左图中插入元素2。经过遍历可得到元素2比4小、6比1大，因此它应该是需要插入在拥有1、3元素的3结点位置。与上例一样，你会发现，1、3结点，4、6结点都是3结点，都不能再插入元素了，再往上看，8、12 结点还是一个3结点，那就意味着，当前我们的树结构是三层已经不能满足当前结点增加的需要了。于是将1、3拆分，4、6拆分，连根结点 8、12 也拆分，最终形成如右图样子。

通过这个例子，也让我们发现，如果2-3树插入的传播效应导致了根结点的拆分，则树的高度就会增加。

2. 2-3 树的删除实现

对于 2-3 树的删除来说，如果对前面插入的理解足够到位的话，应该不是难事了。2-3树的删除也分为三种情况。与插入相反，我们从3结点开始说起。

1. 所删除元素位于一个3结点的叶子结点上，这非常简单，只需要在该结点处删除该元素即可，不会影响到整棵树的其他结点结构。如图所示，删除元素 9，只需要将此结点改成只有元素10的2结点即可。
   
2. 所删除的元素位于一个2结点上，即要删除的是一个只有一个元素的结点。如果按照以前树的理解，删除即可，可现在的 2-3树的定义告诉我们这样做是不可以的。比如图 8-8-8所示，如果我们删除了结点1，那么结点4本来是一个2 结点(它拥有两个孩子)，此时它就不满足定义了。
   
   因此，对于删除叶子是2结点的情况，我们需要分四种情形来处理。
   情形一，此结点的双亲也是2结点，且拥有一个3结点的右孩子。如图，删除结点1，那么只需要左旋，即6成为双亲，4成为6的左孩子，7是6的右孩子。
   
   情形二，此结点的双亲是2结点，它的右孩子也是2结点。如图所示，此时删除结点1，如果直接左旋会造成没有右孩子，因此需要对整棵树变形，办法就是，我们目标是让结点7变成3结点，那就得让比7稍大的元素8下来，随即就得让比元素8稍大的元素9补充结点8的位置，于是就有了中间的图，于是再用左旋的方式，变成右图结果。
   
   情形三，此结点的双亲是一个3结点。如图所示，此时删除结点 10，意味着双亲12、14这个结点不能成为3结点了，于是将此结点拆分，并将12与13合并成为左孩子。
   
   情形四，如果当前树是一个满二叉树的情况，此时删除任何一个叶子都会使得整棵树不能满足 2-3 树的定义。如图所示，删除叶子结点8时(其实删除任何一个结点都一样)，就不得不考虑要将 2-3 的层数减少，办法是将8的双亲和其左子树6合并为一3个结点，再将14与9合并为3结点，最后成为右图的样子。
   
3. 所删除的元素位于非叶子的分支结点。此时我们通常是将树按中序遍历后得到此元素的前驱或后继元素，考虑让它们来补位即可。
   如果我们要删除的分支结点是2结点。如图所示我们要删除4结点，分析后得到它的前驱是1后继是6，显然，由于6、7是3结点，只需要用6来补位即可，如右图所示。
   
   如果我们要删除的分支结点是3结点的某一元素，如图所示我们要删除12、14 结点的12，此时，经过分析，显然应该是将是3结点的左孩子的10上升到删除位置合适。
   

6.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 树的过程，如图所示。图1是在分别插入7、1、2 时的结果图，因为3个元素满足 2-3-4 树的单个4结点定义，因此此时不需要拆分，接着插入元素5，因为已经超过了4结点的定义，因此拆分为图2的形状。之后的图其实就是在元素不断插入时最后形成了图7的2-3-4树。

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

6.3 B树

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

• 如果根结点不是叶结点，则其至少有两棵子树。
• 每一个非根的分支结点都有k-1个元素和k个孩子，其中。每一个叶子结点n都有k-1个元素，其中。
• 所有叶子结点都位于同一层次。
• 所有分支结点包含下列信息数据(n,A0,K1,A,,K2,A2,…,Kn,An)，其中:Ki(i=1,2,…,n)为关键字，且Ki<Ki+1(i=1,2,…,n-1);Ai(i=0,2,…,n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki(i=1,2,……,n)，An所指子树中所有结点的关键字均大于 Kn。n·([m/2]-1≤n≤m-1)为关键字的个数(或n+1为子树的个数)。
  例如，在讲 2-3-4树时插入9个数后的图转成B树示意就如右图所示。左侧灰色方块表示当前结点的元素个数。

在B树上查找的过程是一个顺指针查找结点和在结点中查找关键字的交叉过程。
比方说，我们要查找数字7，首先从外存(比如硬盘中)读取得到根结点3、5、8三个元素，发现7不在当中，但在5和8之间，因此就通过A2再读取外存的6、7结点，查找到所要的元素。
至于B树的插入和删除，方式是与2-3树和2-3-4 树相类似的，只不过阶数可能会很大而已。
在一个典型的 B 树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。因此我们会对 B树进行调整，使得B树的阶数(或结点的元素)与硬盘存储的页面大小相匹配。比如说一棵B树的阶为1001(即1个结点包含1000个关键字)，高度为 2，它可以储存超过 10 亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。这就好比我们普通人数钱都是一张一张的数，而银行职员数钱则是五张、十张，甚至几十张一数，速度当然是比常人快了不少。
通过这种方式，在有限内存的情况下，每一次磁盘的访问我们都可以获得最大数量的数据。由于 B 树每结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少了必须访问结点和数据块的数量，从而提高了性能。可以说，B树的数据结构就是为内外存的数据交互准备的。
那么对于n个关键字的m阶B树，最坏情况是要查找几次呢?
也就是说，在含有n个关键字的B树上查找时，从根结点到关键字结点的路径上涉及的结点数不超过

6.4 B+树

尽管前面我们已经讲了 B树的诸多好处，但其实它还是有缺陷的。对于树结构来说，我们都可以通过中序遍历来顺序查找树中的元素，这一切都是在内存中进行。可是在 B树结构中，我们往返于每个结点之间也就意味着，我们必须得在硬盘的页面之间进行多次访问，如图所示，我们希望遍历这棵B树，假设每个结点都属于硬盘的不同页面，我们为了中序遍历所有的元素，页面2→页面1→页面 3→页面 1→页面 4→页面 1→页面5。而且我们每次经过结点遍历时，都会对结点中的元素进行一次遍历，这就非常糟糕。有没有可能让遍历时每个元素只访问一次呢?

为了说明这个解决的办法，我举个例子。一个优秀的企业尽管可能有非常成熟的树状组织结构，但是这并不意味着员工也很满意，恰恰相反，由于企业管理更多考虑的是企业的利益，这就容易忽略员工的各种诉求，造成了管理者与员工之间的矛盾。正因为此，工会就产生了，工会原意是指基于共同利益而自发组织的社会团体。这个共同利益团体诸如为同一雇主工作的员工，在某一产业领域的个人。工会组织成立的主要作用，可以与雇主谈判工资薪水、工作时限和工作条件等。这样，其实在整个企业的运转过程中，除了正规的层级管理外，还有一个代表员工的团队在发挥另外的作用。
同样的，为了能够解决所有元素遍历等基本问题，我们在原有的B树结构基础上，加上了新的元素组织方式，这就是 B+树。
B+树是应文件系统所需而出的一种 B树的变形树，注意严格意义上讲，它其实已经不是第六章定义的树了。在B树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在B+中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者(叶子结点)中再次列出。另外，每一个子结点都会保存一个指向后一叶子结点的指针。
例如图示就是一棵 B+树的示意，灰色关键字即是根结点中的关键字在叶子结点再次列出，并且所有叶子结点都链接在一起。

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

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

七、散列表（哈希表）

在本章前面的顺序表查找时，我们曾经说过，如果你要查找某个关键字的记录就是从表头开始，挨个的比较记录 a[i]与 key 的值是“=”还是“≠”，直到有相等才算是查找成功，返回i。到了有序表查找时，我们可以利用a[i]与key的“<”或“>”来折半查找，直到相等时查找成功返回1。最终我们的目的都是为了找到那个i，其实也就是相对的下标，再通过顺序存储的存储位置计算方法，LOC(ai)=LOC(a1)·+(i-1) x c，也就是通过第一个元素内存存储位置加上i-1 个单元位置，得到最后的内存地址。
此时我们发现，为了查找到结果，之前的方法“比较”都是不可避免的，但这是否真的有必要?能否直接通过关键字 key 得到要查找的记录内存存储位置呢?

7.1 散列表查找的定义

试想这样的场景，你很想学太极拳，听说学校有个叫张三丰的人打得特别好，于是你到学校学生处找人，学生处的工作人员可能会拿出学生名单，一个一个的查找，最终告诉你，学校没这个人，并说张三丰几百年前就已经在武当山作古了。可如果你找对了人，比如在操场上找那些爱运动的同学，人家会告诉你，“哦，你找张三丰呀有有有，我带你去。”于是他把你带到了体育馆内，并告诉你，那个教大家打太极的小伙子就是“张三丰”，原来“张三丰”是因为他太极拳打得好而得到的外号。
学生处的老师找张三丰，那就是顺序表查找，依赖的是姓名关键字的比较。而通过爱好运动的同学询问时，没有遍历，没有比较，就凭他们“欲找太极'张三丰’，必在体育馆当中”的经验，直接告诉你位置。
也就是说，我们只需要通过某个函数f，使得
存储位置=f(关键字)
那样我们可以通过查找关键字不需要比较就可获得需要的记录的存储位置。这就是一种新的存储技术——散列技术。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字 key对应一个存储位置f(key)。查找时，根据这个确定的对应关系找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。
这里我们把这种对应关系f称为散列函数，又称为哈希(Hash)函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(Hash table)。那么关键字对应的记录存储位置我们称为散列地址。

7.2 散列表的查找步骤

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

1. 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。就像张三丰我们就让他在体育馆，那如果是'爱因斯坦’我们让他在图书馆，如果是'居里夫人’，那就让她在化学实验室，如果是'巴顿将军’，这个打仗的将军一一我们可以让他到网吧。总之，不管什么记录，我们都需要用同一个散列函数计算出地址再存储。
   
2. 当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。说起来很简单，在哪存的，上哪去找，由于存取用的是同一个散列函数，因此结果当然也是相同的。

所以说，散列技术既是一种存储方法，也是一种查找方法。然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向查找的存储结构。
散列技术最适合的求解问题是查找与给定值相等的记录。 对于查找来说，简化了比较过程，效率就会大大提高。但万事有利就有弊，散列技术不具备很多常规数据结构的能力。
比如那种同样的关键字，它能对应很多记录的情况，却不适合用散列技术。一个班级几十个学生，他们的性别有男有女，你用关键字“男”去查找，对应的有许多学生的记录，这显然是不合适的。只有如用班级学生的学号或者身份证号来散列存储，此时一个号码唯一对应一个学生才比较合适。
同样散列表也不适合范围查找，比如查找一个班级18~22岁的同学，在散列表中没法进行。想获得表中记录的排序也不可能，像最大值、最小值等结果也都无法从散列表中计算出来。
我们说了这么多，散列函数应该如何设计?这个我们需要重点来讲解，总之设计一个简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题。

另一个问题是冲突。在理想的情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。我们时常会碰到两个关键字 key1≠key2，但是却有f(key1)=f(key2)，这种现象我们称为冲突(collision)，并把 key1 和key2称为这个散列函数的同义词(synonym)。出现了冲突当然非常糟糕，那将造成数据查找错误。尽管我们可以通过精心设计的散列函数让冲突尽可能的少，但是不能完全避免。于是如何处理冲突就成了一个很重要的课题，这在我们后面也需要详细讲解。

7.3 散列函数的构造方法

不管做什么事要达到最优都不容易，既要付出尽可能的少，又要得到最大化的多。那么什么才算是好的散列函数呢?这里我们有两个原则可以参考。

1. 计算简单
   你说设计一个算法可以保证所有的关键字都不会产生冲突，但是这个算法需要很复杂的计算，会耗费很多时间，这对于需要频繁地查找来说，就会大大降低查找的效率了。因此散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
2. 散列地址分布均匀
   我们刚才也提到冲突带来的问题，最好的办法就是尽量让散列地址均匀地分布在存储空间中，这样可以保证存储空间的有效利用，并减少为处理冲突而耗费的时间。接下来我们就要介绍几种常用的散列函数构造方法。估计设计这些方法的前辈们当年可能是从事间谍工作，因为这些方法都是将原来数字按某种规律变成另一个数字而已。

1. 直接定址法

如果我们现在要对 0~100岁的人口数字统计表，如表8-10-1所示，那么我们对年龄这个关键字就可以直接用年龄的数字作为地址。此时f(key)=key。

如果我们现在要统计的是 80后出生年份的人口数，如表所示，那么我们对出生年份这个关键字可以用年份减去1980来作为地址。此时f(key)=key-1980。

也就是说，我们可以取关键字的某个线性函数值为散列地址，即

这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。

2. 数字分析法

如果我们的关键字是位数较多的数字，比如我们的11位手机号“130xxxx1234”，其中前三位是接入号，一般对应不同运营商公司的子品牌，如 130是联通如意通、136 是移动神州行、153是电信等;中间四位是HLR识别号，表示用户号的归属地;后四位才是真正的用户号，如表所示。

若我们现在要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的。那么我们选择后面的四位成为散列地址就是不错的选择。如果这样的抽取工作还是容易出现冲突问题，还可以对抽取出来的数字再进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环位移、甚至前两数与后两数叠加(如1234改成12+34=46)等方法。总的目的就是为了提供一个散列函数，能够合理地将关键字分配到散列表的各位置。
这里我们提到了一个关键词——抽取。抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。

3. 平方取中法

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

4. 折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(注意最后一部分位数不够时可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如我们的关键字是9876543210，散列表表长为三位，我们将它分为四组9871654132110，然后将它们叠加求和987+654+321+0=1962，再求后3位得到散列地址为 962。
有时可能这还不能够保证分布均匀，不妨从一端向另一端来回折叠后对齐相加。比如我们将987和321反转，再与654和0相加，变成789+654+123+0=1566，此时散列地址为566。
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

5. 除留取余法

此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为:

mod 是取模(求余数)的意思。事实上，这方法不仅可以对关键字直接取，也可在折叠、平方取中后再取模。
很显然，本方法的关键就在于选择合适的p，p如果选得不好，就可能会容易产生同义词。
例如下表，我们对于有12 个记录的关键字构造散列表时，就用了f(key)=key mod 12的方法。比如29 mod 12=5，所以它存储在下标为5的位置。

不过这也是存在冲突的可能的，因为12=2x6=3x4。如果关键字中有像18(3x6)、30(5x6)、42(7x6)等数字，它们的余数都为6，这就和 78 所对应的下标位置冲突了。
甚至极端一些，对于表的关键字，如果我们让p为12的话，就可能出现下面的情况，所有的关键字都得到了0这个地址数，这未免也太糟糕了点。

我们不选用 p=12 来做除留余数法，而选用p=11，如表所示。

此就只有12 和144有冲突，相对来说，就要好很多。因此根据前辈们的经验，若散列表表长为m，通常为小于或等于表长(最好接近m)的最小质数或不包含小于20 质因子的合数。

6. 随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是f(key)=random(key)。这里random 是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
有同学问，那如果关键字是字符串如何处理?其实无论是英文字符，还是中文字符，也包括各种各样的符号，它们都可以转化为某种数字来对待，比如ASCII码或者Unicode 码等，因此也就可以使用上面的这些方法。

总之，现实中，应该视不同的情况采用不同的散列函数。我们只能给出一些考虑的因素来提供参考:

1. 计算散列地址所需的时间。
2. 关键字的长度。
3. 散列表的大小。
4. 关键字的分布情况。
5. 记录查找的频率。综合这些因素，才能决策选择哪种散列函数更合适。

7.4 处理散列冲突的方法

我们每个人都希望身体健康，虽然疾病能够预防，但是不可避免，没有任何成年人生下来到现在没有生过一次病。
从刚才除留余数法的例子也可以看出，我们设计得再好的散列函数也不可能完全避免冲突，这就像我们再健康也只能尽量预防疾病，但却无法保证永远不得病一样，既然冲突不能避免，就要考虑如何处理它。
那么当我们在使用散列函数后发现两个关键字key1≠key2，但是却有f(key1)=f(key2)，即有冲突时，怎么办呢?我们可以从生活中找寻思路。
试想一下，当你观望很久很久，终于看上一套房打算要买了，正准备下订金，人家告诉你，这房子已经被人买走了，你怎么办?
对呀，再找别的房子呗!这其实就是一种处理冲突的方法——开放定址法。

1. 开放定址法

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

比如说，我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34}，表长为 12。
我们用散列函数f(key)=key mod 12。
当计算前5 个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入，如表所示。

计算 key=37时，发现f(37)=1，此时就与25所在的位置冲突。于是我们应用上面的公式f(37)=(f(37)+1)mod 12=2。于是将37存入下标为2的位置。这其实就是房子被人买了于是买下一间的作法，如表 所示。

接下来 22,29,15,47都没有冲突，正常的存入，如表所示。

到了key=48，我们计算得到f(48)=0，与12所在的0位置冲突了，不要紧我们f(48)=(f(48)+1)mod12=1，此时又与25 所在的位置冲突。于是f(48)=(f(48)+2)mod12=2，还是冲突…一直到f(48)=(f(48)+6)mod12=6 时，才有空位，机不可失，赶快存入，如表所示。

我们把这种解决冲突的开放定址法称为线性探测法。
从这个例子我们也看到，我们在解决冲突的时候，还会碰到如48和37 这种本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。很显然，堆积的出现，使得我们需要不断处理冲突，无论是存入还是查找效率都会大大降低。
另外增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为二次探测法。

还有一种方法是，在冲突时，对于位移量di采用随机函数计算得到，我们称之为随机探测法。

总之，开放定址法只要在散列表未填满时，总是能找到不发生冲突的地址，是我们常用的解决冲突的办法。

2. 再散列函数

我们继续用买房子来举例，如果你看房时的选择标准总是以市中心、交通便利、价格适中为指标，这样的房子凤毛麟角，基本上当你看到时，都已经被人买去了。我们不妨换一种思维，选择市郊的房子，交通尽管要差一些，但价格便宜很多也许房子还可以买得大一些、质量好一些，并且由于更换了选房的想法，很快就找到了你需要的房子了。
对于我们的散列表来说，我们事先准备多个散列函数。

这里 RHi 就是不同的散列函数，你可以把我们前面说的什么除留余数、折叠、平方取中全部用上。每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个可以把冲突解决掉。这种方法能够使得关键字不产生聚集，当然，相应地也增加了计算的时间。

3. 链地址法

思路还可以再换一换，为什么有冲突就要换地方呢，我们直接就在原地想办法不可以吗?于是我们就有了链地址法。
将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。对于关键字集合{12,67,56,16,25,3722,29,15,47,48,34}，我们用前面同样的12为除数，进行除留余数法，可得到如图结构，此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。

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

4. 公共溢出区法

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

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

7.5 散列表查找实现

1. 散列表查找算法实现

首先是需要定义一个散列表的结构以及一些相关的常数。其中HashTabe 就是散列表结构。结构当中的 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;
}

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

2. 散列表查找性能分析

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

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

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

八、总结

我们这一章全都是围绕一个主题“查找”来作文章的。
首先我们要弄清楚查找表、记录、关键字、主关键字、静态查找表、动态查找表等这些概念。
然后，对于顺序表查找来说，尽管很土(简单)，但它却是后面很多查找的基础注意设置“哨兵”的技巧，可以使得本已经很难提升的简单算法里还是提高了性能。

有序查找，我们着重讲了折半查找的思想，它在性能上比原来的顺序查找有了质的飞跃，由O(n)变成了O(logn)。之后我们又讲解了另外两种优秀的有序查找:插值查找和斐波那契查找，三者各有优缺点，望大家要仔细体会。

线性索引查找，我们讲解了稠密索引、分块索引和倒排索引。索引技术被广泛的用于文件检索、数据库和搜索引擎等技术领域，是进一步学习这些技术的基础。

二叉排序树是动态查找最重要的数据结构，它可以在兼顾查找性能的基础上，让插入和删除也变得效率较高。不过为了达到最优的状态，二叉排序树最好是构造成平衡的二叉树才最佳。因此我们就需要再学习关于平衡二叉树(AVL树)的数据结构了解 AVL, 树是如何处理平衡性的问题。这部分是本章重点，需要认真学习掌握。

B 树这种数据结构是针对内存与外存之间的存取而专门设计的。由于内外存的查找性能更多取决于读取的次数，因此在设计中要考虑B树的平衡和层次。我们讲解时是先通过最最简单的 B树(2-3树)来理解如何构建、插入、删除元素的操作，再通过 2-3-4树的深化，最终来理解B树的原理。之后，我们还介绍了B+树的设计思想。

散列表是一种非常高效的查找数据结构，在原理上也与前面的查找不尽相同，它回避了关键字之间反复比较的烦琐，而是直接一步到位查找结果。当然，这也就带来了记录之间没有任何关联的弊端。应该说，散列表对于那种查找性能要求高，记录之间关系无要求的数据有非常好的适用性。在学习中要注意的是散列函数的选择和处理冲突的方法。