java实现常见查找算法

朴灿烈づ我的快乐病毒、 2022-06-16 12:40 199阅读 0赞

**查找**

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

在互联网上查找信息是我们的家常便饭。所有这些需要被查的数据所在的集合，我们给它一个统称叫查找表。

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

查找表按照操作方式来分有两大种:静态查找表和动态查找表。  
**静态查找表**(Static Search Table) :只作查找操作的查找表。它的主要操作有:  
( 1 ) 查询某个"特定的"数据元素是否在查找表中。  
( 2 ) 检索某个"特定的"数据元索和各种属性。  
按照我们大多数人的理解，查找，当然是在已经有的数据中找到我们需要的。静态查找就是在干这样的事情，不过，现实中还有存在这样的应用:查找的目的不仅仅只是查找,还可能边查找边作其它操作。  
**动态查找表**(Dynamic Search Table): 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。显然动态查找表的操作就是两个:  
( 1 ) 查找时插入数据元素。  
( 2 ) 查找时删除数据元素。  
为了提高查找的效率 ，我们需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。  
从逻辑上来说，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。可是要想获得较高的查找性能，我们就不得不改变数据元素之间的关系，在存储时可以将查找集合组织成表、树等结构。  
例如，对于静态查找表来说，我们不妨应用线性表结构来组织数据，这样可以使用顺序查找算法，如果再对主关键字排序，则可以应用折半查找等技术进行高效的查找。  
如果是需要动态查找，则会复杂一些，可以考虑二叉排序树的查找技术。另外，还可以用散列表结构来解决一些查找问题，这些技术都将在后面的讲解中说明。

# 顺序表查找 #

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

/**
     * 顺序查找
     * 
     * @param a
     *            数组
     * @param key
     *            待查找关键字
     * @return 关键字下标
     */
    public static int sequentialSearch(int[] a, int key) {
    	for (int i = 0; i < a.length; i++) {
    		if (a[i] == key)
    			return i;
    	}
    	return -1;
    }

这段代码非常简单，就是在数组a中查看有没有关键字key，当你需要查找复杂表结构的记录时，只需要把数组a与关键字key定义成你需要的表结构和数据类型即可。

## 顺序表查找优化 ##

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

/**
     * 有哨兵顺序查找
     * 
     * @param a
     *            数组(下标为0存放哨兵元素)
     * @param key
     *            待查询关键字
     * @return 关键字下标 返回0 则未找到
     */
    public static int sequentialSearch2(int[] a, int key) {
    	int index = a.length - 1;
    	a[0] = key;// 将下标为0的数组元素设置为哨兵
    	while (a[index] != key) {
    		index--;
    	}
    	return index;
    }

这种在查找方向的尽头放置"哨兵"免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。当然，"哨兵"也不一定就一定要在数组开始，也可以在末端。

对于这种顺序查找算法来说，查找成功最好的情况就是在第一个位置就找到了，算法时间复杂度为O(1)，最坏的情况是在最后一位置才找到，需要n次比较，时间复杂度为O(n)，当查找不成功时，需要n+1次比较，时间复杂度为O(n)。我们之前推导过，关键字在任何一位置的概率是相同的，所以平均查找次数为(n+1)/2 ，所以最终时间复杂度还是O(n)。

很显然，顺序查找技术是有很大缺点的，n很大时，查找效率极为低下，不过优点也是有的，这个算法非常简单，对静态查找表的记录没有任何要求，在一些小型数据的查找时，是可以适用的。  
另外，也正由于查找概率的不同，我们完全可以将容易查找到的记录放在前面，而不常用的记录放置在后面，效率就可以有大幅提高。

# 有序表查找 #

一个线性表有序时，对于查找总是很有帮助的。

## 折半查找 ##

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

我们来看折半查找的算法是如何工作的。

/**
     * 折半查找
     * 
     * @param a
     *            数组
     * @param key
     *            待查找关键字
     * @return 返回折半下标， -1表示不存在该关键字
     */
    public static int binarySearch(int[] a, int key) {
    	int low, mid, high;
    	low = 0;// 最小下标
    	high = a.length - 1;// 最大小标
    	while (low <= high) {
    		mid = (high + low) / 2;// 折半下标
    		if (key > a[mid]) {
    			low = mid + 1; // 关键字比 折半值 大，则最小下标 调成 折半下标的下一位
    		} else if (key < a[mid]) {
    			high = mid - 1;// 关键字比 折半值 小，则最大下标 调成 折半下标的前一位
    		} else {
    			return mid; // 当 key == a[mid] 返回 折半下标
    		}
    	}
    	return -1;
    }

该算法还是比较容易理解的，同时我们也能感觉到它的效率非常高。但到底高多少?关键在于此算法的时间复杂度分析。

首先，我们将数组的查找过程绘制成一棵二叉树，如果查找的关键字不是中间记录的话，折半查找等于是把静态有序  
查找表分成了两棵子树，即查找结果只需要找其中的一半数据记录即可，等于工作量少了一半，然后继续折半查找，效率当然是非常高了。

根据二叉树的性质4，具有n个结点的完全二叉树的深度为\[log2n\]+1。在这里尽管折半查找判定二叉树并不是完全二  
叉树，但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数为\[log2n\]+1，最好的情况是1次。  
因此最终我们折半算法的时间复杂度为O(logn)，它显然远远好于顺序查找的O(n)时间复杂度了。  
不过由于折主查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

## 插值查找 ##

现在我们的新问题是，为什么一定要折半，而不是折四分之一或者折更多呢?  
打个比方，在英文词典里查"apple"，你下意识里翻开词典是翻前面的书页还是后面的书页呢?如果再让你查"zoo"，你又怎么查?很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。  
同样的，比如要在取值范围0 - 10000之间100个元素从小到大均匀分布的数组中查找5，我们自然会考虑从数组下标较小的开始查找。  
看来，我们的折半查找，还是有改进空间的。折半计算mid的公式，我们略微等式变换后得到:

mid = (low+high)/2 = low + (high-low)/2

也就是mid等于最低下标low加上最高下标high与low的差的一半。算法科学家们考虑的就是将这个 1/2 进行改进，通过类比，改进为下面的计算方案:

mid = low + ((key - a\[low\])/(a\[high\] - a\[low\]))(high - low)

这样就可以大大提高查找的效率。

**插值查找(Interpolation Search)是根据要查找的关键字 key 与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式(key - a\[low\])/(a\[high\] - a\[low\])。**应该说，从时间复杂度来看，它也是O(logn)，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多 。反之， 数组中如果分布类似\{0，1，2，2000，2001，.......,999998, 999999\}这种极端不均匀的数据，用插值查找未必是很合适的选择。

/**
     * 插值查找
     * 
     * @param a
     *            数组
     * @param key
     *            待查找关键字
     * @return 返回折半下标， -1表示不存在该关键字
     */
    public static int interpolationSearch(int[] a, int key) {
    	int low, mid, high;
    	low = 0;// 最小下标
    	high = a.length - 1;// 最大小标
    	while (low < high) {
    		mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]);
    		// mid = (high + low) / 2;// 折半下标
    		if (key > a[mid]) {
    			low = mid + 1; // 关键字比 折半值 大，则最小下标 调成 折半下标的下一位
    		} else if (key < a[mid]) {
    			high = mid - 1;// 关键字比 折半值 小，则最大下标 调成 折半下标的前一位
    		} else {
    			return mid; // 当 key == a[mid] 返回 折半下标
    		}
    	}
    	return -1;
    }

## 斐波那契查找 ##

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

/** 斐波那契数列 */
    static int[] f = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 };
    
    /**
     * 斐波那契查找(黄金分割原理)
     * 
     * @param a
     *            待查询数组
     * @param key
     *            待查找关键字
     * @return 返回关键字在a数组中的下标，返回-1表示数组中不存在此关键字
     */
    public static int fibonaciSearch(int[] a, int key) {
    	int low, mid, high, k;
    	low = 0;
    	high = a.length - 1;
    	// 斐波那契数列下标
    	k = 0;
    	// 获取斐波那契分割值下标
    	while (high > f[k] - 1)
    		k++;
    	// 利用Java工具类Arrays构造长度为f[k]的新数组并指向引用a
    	a = Arrays.copyOf(a, f[k]);
    	// 对新数组后面多余的元素赋值最大的元素
    	for (int i = high + 1; i < f[k]; i++) {
    		a[i] = a[high];//当key是是最大值时候，防止角标越界异常
    	}
    	while (low <= high) {
    		// 前半部分有f[k-1]个元素，由于下标从0开始
    		// 减去 1 获取 分割位置元素的下标
    		mid = low + f[k - 1] - 1;
    
    		if (key < a[mid]) {// 关键字小于分割位置元素，则继续查找前半部分，高位指针移动
    			high = mid - 1;
    			// (全部元素) = (前半部分)+(后半部分)
    			// f[k] = f[k-1] + f[k-2]
    			// 因为前半部分有f[k-1]个元素， 则继续拆分f[k-1] = f[k-2] + f[k-3]成立
    			// 即在f[k-1]个元素的前半部分f[k-2]中继续查找，所以k = k - 1,
    			// 则下次循环mid = low + f[k - 1 - 1] - 1;
    			k = k - 1;
    		} else if (key > a[mid]) {// 关键字大于分割位置元素，则查找后半部分，低位指针移动
    			low = mid + 1;
    			// (全部元素) = (前半部分)+(后半部分)
    			// f[k] = f[k-1] + f[k-2]
    			// 因为后半部分有f[k-2]个元素， 则继续拆分f[k-2] = f[k-3] + f[k-4]成立
    			// 即在f[k-2]个元素的前半部分f[k-3]继续查找，所以k = k - 2,
    			// 则下次循环mid = low + f[k - 2 - 1] - 1;
    			k = k - 2;
    		} else {
    			// 当条件成立的时候，则找到元素
    			if (mid <= high)
    				return mid;
    			else
    				// 出现这种情况是查找到补充的元素
    				// 而补充的元素与high位置的元素一样
    				return high;
    		}
    	}
    	return -1;
    }

斐波那契查找算法的核心在于 :  
1 ) 当 key=a\[mid\] 时，查找就成功。  
2 ) 当 key<a\[mid\]时，新范围是第low个到第mid-l个，此时范围个数为f\[k-1\]-1个;  
3 ) 当 key>a\[mid\]时，新范围是第mid+l个到第high个，此时范围个数为f\[k-2\]-1个。

![Center][]

也就是说，如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于当中的大部分数据，其工作效率要高一些。所以尽管斐波那契查找的时间复杂也为O(logn)，但就平均性能来说，斐波那契查找要优于折半查找。可惜如果是最坏情况，比如这里key=l，那么始终都处于左侧长半区在查找，则查找效率要低于折半查找。

还有比较关键的一点，折半查找是进行加法与除法运算mid=(low+ high)/2,插值查找进行复杂的四则运算mid = low + ((key - a\[low\])/(a\[high\] - a\[low\]))(high - low),而斐波那契查找只是最简单加减法运算mid=low+f\[k-l\]-1,在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。  
应该说，**三种有序表的查找本质上是分隔点的选择不同，各有优劣**，实际开发时可根据数据的特点综合考虑再做出选择。

# 线性索引查找 #

我们前面讲的几种比较高效的查找方法都是基于有序的基础之上的，但事实上，很多数据集可能增长非常快，如果要保证记录全部是按照当中的某个关键字有序，其时间代价是非常高昂的，所以这种数据通常都是按先后顺序存储。

那么对于这样的查找表，我们如何能够快速查找到需要的数据呢?办法就是--索引。  
数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。**索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息**。索引技术是组织大型数据库以及磁盘文件的一种重要技术。

索引按照结构可以分为线性索引、树形索引和多级索引。我们这里就只介绍线性索引技术。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。我们重点介绍三种线性索引;稠密索引、分块索引和倒排索引。

## 稠密索引 ##

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

![Center 1][]

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

索引项有序也就意味着，我们要查找关键字时，可以用到折半、插值、斐被那契等有序查找算法，大大提高了效率 ，比如上图中，我要查找关键字是18的记录，如果直接从右侧的数据表中查找，那只能顺序查找，需要查找6次才可以查到结果。而如果是从左侧的索引表中查找，只需两次折半查找就可以得到18对应的指针，最终查找到结果。  
这显然是稠密索引优点，但是如果数据集非常大，比如上亿，那也就意味着索引也得同样的数据集长度规模，对于内存有限的计算机来说，可能就需要反复去访问磁盘，查找性能反而大大下降了。

## 分块索引 ##

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

分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件:  
• 块内无序，即每一块内的记录不要求有序。当然 ，你如果能够让块内有序对查找来说更理想，不过这就要付出大量时间和空间的代价，因此通常我们不要求块内有序 。  
• 块间有序，例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字……因为只有块间有序，才有可能在查找时带来放率。

**对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。**  
如下图所示，我们定义的分块索引的索引项结构分三个数据项 :  
• 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大;  
• 存储了块中的记录个数，以便于循环时使用;  
• 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

![Center 2][]

在分块索引表中查找，就是分两步进行:  
1. 在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。例如，在上图的数据集中查找62，我们可以很快可以从左上角的索引表中由57<62<96得到62在第三个块中。  
2. 根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。  
我们再来分析一下分块索引的平均查找长度。设 n 个记录的数据集被平均分成 m 块，每个块中有 t 条记录，显然 n=m×t，或者说 m=n/t。再假设 Lb 为查找索引表的平均查找长度，因最好与最差的等概率原则，所以Lb平均长度为(m+1)/2。Lw为块中查找记录的平均查找长度，同理可知它的平均查找长度为(t+1)/2。

这样分块索引查找的平均查找长度为:

ASLw = Lb + Lw = (m+1)/2 + (t+1)/2 = (m+t)/2 + 1 = (n/t + t)/2 + 1

注意上面这个式子的推导是为了让整个分块索引查找长度依赖 n 和 t 两个变量。从这里了我们也就得到，平均长度不仅仅取决于数据集的总记录数 n ，还和每一个块的记录个数 t 相关。最佳的情况就是分的块数m与块中的记录数 t相同，此时意味着n = m × t = t²，即ASLw = (n/t + t)/2 + 1 = √n + 1

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

## 倒排索引 ##

搜索引擎通常检索的场景是：给定几个关键词，找出包含关键词的记录。

我们来看样例，现在有两篇极短的英文"文章"--其实只能算是句子，我们暂认为它是文章，编号分别是1和2。  
1.Books and friends should be few but good.(读书如交友，应求少而精。)  
2.A good book is a good friend.(好书如挚友。)  
假设我们忽略掉如"books" 、"friends" 中的复数"s"以及如"A"这样的大小写差异。我们可以整理出这样一张单词表，如下表所示，并将单词做了排序，也就是表格显示了每个不同的单词分别出现在哪篇文章中，比如"good"在两篇文章中都有出现，而"is"只是在文章2中才有。

![Center 3][]

有了这样一张单词表，我们要搜索文章，就非常方便了。如果你在搜索框中填写"book"关键字。系统就先在这张单词表中有序查找"book"，找到后将它对应的文章编号1和2的文章地址(通常在搜索引擎中就是网页的标题和链接)返回，并告诉你，查找到两条记录，用时0.0001秒。由于单词表是有序的，查找效率很高，返回的又只是文章的编号，所以整体速度都非常快。  
如果没有这张单词表，为了能证实所有的文章中有还是没有关键字"book"，则需要对每一篇文章每一个单词顺序查找。在文章数是海量的情况下，这样的做法只存在理论上可行性，现实中是没有人愿意使用的。

在这里这张单词表就是索引表，索引项的通用结构是:  
• 次关键码，例如上面的"英文单词";  
• 记录号表，例如上面的"文章编号"。  
**其中记录号表存储具有相同次关键字的所有记录的记录号(可以是指向记录的指针或者是该记录的主关键字)。这样的索引方法就是倒排索引(inverted index)**。倒排索引源于实际应用中需要根据属性(或字段、次关键码)的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。**由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。**

# 二叉排序树 #

假设查找的数据集是普通的顺序存储，那么插入操作就是将记录放在表的末端，给表记录数加一即可，删除操作可以是删除后，后面的记录向前移，也可以是要删除的元素与最后一个元素互换，表记录数减一，反正整个数据集也没有什么顺序，这样的效率也不错。 应该说，插入和删除对于顺序存储结构来说，效率是可以接受的，但这样的表由于无序造成查找的效率很低。  
如果查找的数据集是有序线性表，并且是顺序存储的，查找可以用折半、插值、斐波那契等查找算法来实现，可惜，因为有序，在插入和删除操作上，就需要耗费大量的时间 。  
有没有一种即可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法呢?

我们把这种需要在查找时插入或删除的查找表称为动态查找表。现在就来看着什么样的结构可以实现动态查找表的高效率。  
如果在复杂的问题面前，我们束手无策的话，不妨先从最最简单的情况入手。现在我们的目标是插入和查找同样高效 。假设我们的数据集开始只有一个数\{62\}， 然后现在需要将88插入数据集，于是数据集成了\{62，88\}，还保持着从小到大有序。再查找有没有58，没有则插入，可此时要想在线性表的顺序存储中有序，就得移动 62 和  
88 的位置，如下左图，可不可以不移动呢?那就需要使用二叉树结构。当我们用二叉树的方式时，首先我们将第一个数62定为根结点，88因为比62大，因此让它做62的右子树，58因比62小，所以成为它的左子树。此时58的插入并没有影响到62与88的关系，如下右图所示。

![Center 4][]

也就是说， 若我们现在需要对集合\{62,88,58,47,35,73,51,99,37,93\}做查找，在我们打算创建此集合时就考虑用二叉树结构，而且是排好序的二叉树来创建。如下图所示，62、88、58创建好后，下一个数 47 因比58小，是它的左子树(见③)，35是47的左子树(见④)，73比62大，但却比88小，是88的左子树(见⑤)，51比62小、比58小、比47大，是 47的右子树(见⑥)，99比62、88都大，是它的右子树(见⑦)，37比62、58、47都小，但却比35大，是35的右子树(见③) ,93则因比62、88大是99的左子树(见⑨)。

![Center 5][]

这样我们就得到了一棵二叉树，并且当我们对它进行中序遍历时，就可以得到一个有序的序列\{35,37,47,51,58,62,73,88,93,99\}，所以我们通常称它为二叉排序树。  
**二叉排序树(Binary Sort Tree)，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。**  
**• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;  
• 若它的右子树不空 ，则右子树上所有结点的值均大于它的根结点的值;  
• 它的左、右子树也分别为二叉排序树。**

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

## 二叉排序树查找操作 ##

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

/**
     * 二叉树 数据结构
     */
    class BinTree {
    	int data;
    	BinTree lchild;
    	BinTree rchild;
    }

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

## 二叉排序树插入操作 ##

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

public class SearchBST {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		// 主要是表达查询，所以手动构造一棵二叉排序树
    		BinTree bt1 = new BinTree();
    		bt1.data = 62;
    		BinTree bt2 = new BinTree();
    		bt1.lchild = bt2;
    		bt2.data = 58;
    		BinTree bt3 = new BinTree();
    		bt2.lchild = bt3;
    		bt3.data = 47;
    		BinTree bt4 = new BinTree();
    		bt3.lchild = bt4;
    		bt4.data = 35;
    		BinTree bt5 = new BinTree();
    		bt4.rchild = bt5;
    		bt5.data = 37;
    		BinTree bt6 = new BinTree();
    		bt3.rchild = bt6;
    		bt6.data = 51;
    		BinTree bt7 = new BinTree();
    		bt1.rchild = bt7;
    		bt7.data = 88;
    		BinTree bt8 = new BinTree();
    		bt7.lchild = bt8;
    		bt8.data = 73;
    		BinTree bt9 = new BinTree();
    		bt7.rchild = bt9;
    		bt9.data = 99;
    		BinTree bt10 = new BinTree();
    		bt9.lchild = bt10;
    		bt10.data = 93;
    
    		insertBST(bt1,12);
    	}
    
    	/** 全局变量 存放查找到的关键字所在的父节点 */
    	static BinTree parentNode = new BinTree();
    	
    	/**
    	 * 二叉排序树
    	 * 
    	 * @param bt
    	 *            待查询二叉排序树
    	 * @param key
    	 *            查找关键字
    	 * @param parent
    	 *            指向bt的双亲，其初始调用值为null
    	 * @return 查找关键字key成功 返回true，并把树结点赋值给全局变量result，查找失败，返回false
    	 */
    	public static boolean searchBST(BinTree bt, int key, BinTree parent) {
    		if (null == bt || 0 == bt.data) {// 树节点不存在，返回
    			parentNode = parent;
    			return false;
    		} else if (key == bt.data) {// 查找成功
    			parentNode = bt;
    			return true;
    		} else if (key < bt.data) {// 关键字小于根节点则查找左子树
    			return searchBST(bt.lchild, key, bt);
    		} else// 关键字大于根节点则查找右子树
    			return searchBST(bt.rchild, key, bt);
    	}
    
    	/**
    	 * 在二叉排序树中插入关键字key(如果不存在)
    	 * 
    	 * @param bt
    	 *            二叉排序树
    	 * @param key
    	 *            sdddd
    	 * @return 插入成功返回true 错误返回false
    	 */
    	public static boolean insertBST(BinTree bt, int key) {
    		BinTree s;
    		if (!searchBST(bt, key, null)) {
    			s = new BinTree();
    			s.data = key;
    			s.lchild = s.rchild = null;
    			if (null == parentNode)// 不存在，则表明是父节点，将s指向bt成为新的根节点
    				bt = s;
    			else if (key < parentNode.data)
    				parentNode.lchild = s;// 当key小于子根结点，则插入为左孩子
    			else
    				parentNode.rchild = s;// 当key大于子根结点，则插入为右孩子
    
    			preOrderTraverse(bt);
    			return true;
    		} else
    			System.out.println("该节点已存在!");
    		return false;
    	}
    
    	/** 中序遍历打印线索二叉树 */
    	static void preOrderTraverse(BinTree t) {
    		if (null == t || 0 == t.data)
    			return;
    		if (null != t.lchild)
    			preOrderTraverse(t.lchild);/* 接着中序遍历左子树 */
    		if (0 != t.data)
    			System.out.print("[" + t.data + "]");/* 显示当前结点数据 */
    		if (null != t.rchild)
    			preOrderTraverse(t.rchild);/* 最后遍历右子树 */
    	}
    
    	/**
    	 * 二叉树 数据结构
    	 */
    	private static class BinTree {
    		int data;
    		BinTree lchild;
    		BinTree rchild;
    	}
    }

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

public class SearchBST {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    		int[] a = { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93 };
    		for (int i = 0; i < a.length; i++) {
    			generateBST(a[i]);
    			System.out.println();
    		}
    	}
    	
    	static BinTree newTree = new BinTree();
    
    	/** 全局变量 存放查找到的关键字所在的父节点 */
    	static BinTree parentNode = new BinTree();
    
    	/**
    	 * 二叉排序树
    	 * 
    	 * @param bt
    	 *            待查询二叉排序树
    	 * @param key
    	 *            查找关键字
    	 * @param parent
    	 *            指向bt的双亲，其初始调用值为null
    	 * @return 查找关键字key成功 返回true，并把树结点赋值给全局变量result，查找失败，返回false
    	 */
    	public static boolean searchBST(BinTree bt, int key, BinTree parent) {
    		if (null == bt || 0 == bt.data) {// 树节点不存在，返回
    			parentNode = parent;
    			return false;
    		} else if (key == bt.data) {// 查找成功
    			parentNode = bt;
    			return true;
    		} else if (key < bt.data) {// 关键字小于根节点则查找左子树
    			return searchBST(bt.lchild, key, bt);
    		} else// 关键字大于根节点则查找右子树
    			return searchBST(bt.rchild, key, bt);
    	}
    
    	/** 生成二叉排序树 */
    	public static boolean generateBST(int key) {
    
    		if (!searchBST(newTree, key, null)) {
    			BinTree s = new BinTree();
    			s.data = key;
    			s.lchild = s.rchild = null;
    			if (null == parentNode)// 不存在，则表明是父节点，将s指向bt成为新的根节点
    				newTree = s;
    			else if (key < parentNode.data)
    				parentNode.lchild = s;// 当key小于子根结点，则插入为左孩子
    			else
    				parentNode.rchild = s;// 当key大于子根结点，则插入为右孩子
    
    			preOrderTraverse(newTree);
    			return true;
    		} else
    			System.out.println("该节点已存在!");
    		return false;
    	}
    
    	/** 中序遍历打印线索二叉树 */
    	static void preOrderTraverse(BinTree t) {
    		if (null == t || 0 == t.data)
    			return;
    		if (null != t.lchild)
    			preOrderTraverse(t.lchild);/* 接着中序遍历左子树 */
    		if (0 != t.data)
    			System.out.print("[" + t.data + "]");/* 显示当前结点数据 */
    		if (null != t.rchild)
    			preOrderTraverse(t.rchild);/* 最后遍历右子树 */
    	}
    
    	/**
    	 * 二叉树 数据结构
    	 */
    	private static class BinTree {
    		int data;
    		BinTree lchild;
    		BinTree rchild;
    	}
    }

![Center 6][]

## 二叉排序树删除操作 ##

俗话说"请神容易送神难"，我们已经介绍了二叉排序树的查找与插入算法，但是对于二叉排序树的删除，就不是那么容易，我们不能因为删除了结点，而让这棵树变得不满足二叉排序树的特性，所以删除需要考虑多种情况。  
如果需要查找并删除如37、51、73、93这些在二叉排序树中是叶子的结点，那是很容易的，毕竟删除它们对整棵树来说，其他结点的结构并未受到影响，如图所示 。

![Center 7][]

对于要删除的结点只有左子树或只有右子树的情况，相对也比较好解决。那就是结点删除后，将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业。比如下图所示，就是先删除35和99结点，再删除58结点的变化图，最终，整个结构还是一个二叉排序树。

![Center 8][]

但是对于要删除的结点既有左子树又有右子树的情况怎么办呢?比下图中的47结点若要删除了，它的两儿子以及子孙们怎么办呢?

![Center 9][]

起初的想法，我们当47结点只有一个左子树，那么做法和一个左子树的操作一样，让35及它之下的结点成为58的左子树，然后再对47的右子树所有结点进行插人操作，如下图所示。 这是比较简单的想法，可是47的右子树有子孙共5个结点，这么做效率不高且不说， 还会导致整个二叉排序树结构发生很大的变化，有可能会增加树的高度。增加高度可不是个好事，这我们待会再说，总之这个想法不太好。

![Center 10][]

我们仔细观察一下，47的两个子树中能否找出一个结点可以代替47呢?果然有，37或者48都可以代替47，此时在删除 47后， 整个二叉排序树并没有发生什么本质的改变。  
为什么是37和48? 对的，它们正好是二叉排序树中比它小或比它大的最接近47的两个数。也就是说，如果我们对这棵二叉排序树进行中序遍历，得到的序列\{29，35，36，37，47，48，49，50，51，56，58，62，73，88，93.99\}，它们正好是47的前驱和后继。  
因此，比较好的办法就是，找到需要删除的结点p的直接前驱(或直接后继),用s来替换结点p,然后再删除此结点s,如下图所示。

![Center 11][]

![Center 12][]

根据我们对删除结点三种情况的分析:  
• 叶子结点;  
• 仅有左或右子树的结点 :  
• 左右子树都有的结点 ，我们来看代码，下面这个算法是递归方式对二叉排序树T查找key，查找到时删除。

public static boolean deleteBST(BinTree bt, int key) {
    	if (!searchBST(bt, key, null)) { // 不存在关键字等于key的元素
    		return false;
    	} else {
    		if (bt.data == key) {
    			return delete(bt);
    		} else if (key < bt.data) {
    			return deleteBST(bt.lchild, key);
    		} else {
    			return deleteBST(bt.rchild, key);
    		}
    	}
    }

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

/** 从二叉排序树中删除结点p，并重接它的左或右子树 */
    public static boolean delete(BinTree bt) {
    	BinTree q, s;
    	if (null == bt.rchild) {
    		bt = bt.lchild; // 右子树为空则只需重接左子树
    	} else if (null == bt.lchild) {
    		bt = bt.rchild;  左子树为空则只需重接右子树
    	} else {
    		q = bt;
    		s = bt.lchild;
    		while (null != s.rchild) {// 转左，然后向右到尽头(找到待删结点前驱)
    			q = s;
    			s = s.rchild;
    		}
    		bt.data = s.data;// s指向被删除结点的直接前驱
    		if (q != bt) {//
    			q.rchild = s.lchild;// 重接q的右子树
    		} else {// q.data == bt.data，则说明s.rchild == null
    			q.lchild = s.lchild; // 重接q的左子树
    		}
    	}
    	return true;
    }

## 二叉排序树总结 ##

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

![Center 13][]

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

# 平衡二叉树(AVL树) #

平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

从平衡二叉的英文名字(AVL树)，你也可以体会到，它是一种高度平衡的二叉排序树。

那什么叫做高度平衡呢?意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor) ，那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

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

![Center 14][]

## 平衡二叉树实现原理 ##

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

## 平衡二叉树实现算法 ##

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

/**
     * 二叉树的二叉树链表结构定义
     */
    private static class BinTree {
    	int data;// 结点数据
    	int bf;// 结点的平衡因子
    	BinTree lchild, rchild;// 左右孩子引用
    
    	@Override
    	public String toString() {
    		return "[结点值:" + data + ", 平衡因子:" + bf + ", 左孩子:" + lchild + ", 右孩子:" + rchild + "]";
    	}
    
    }

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

/** 右旋 */
    static BinTree rRotate(BinTree bt) {
    	BinTree l;
    	l = bt.lchild;//l指向bt的左子树的根节点
    	bt.lchild = l.rchild;//l的右子树指向bt的左子树
    	l.rchild = bt;//bt指向l的右子树
    	bt = l;//l指向新的根节点
    	return bt;
    }

此函数代码的意思是说，当传入一个二叉排序树bt，将它的左孩子结点定义为l，将l的右子树变成bt的左子树，再将 bt成l的右子树，最后将l替换bt成为根结点，这样就完成了一次右旋操作。

左旋操作代码如下。

/** 左旋 */
    static BinTree lRotate(BinTree bt) {
    	BinTree r;
    	r = bt.rchild;
    	bt.rchild = r.lchild;
    	r.lchild = bt;
    	bt = r;
    	return bt;
    }

这段代码与右旋代码是对称的。  
现在我们来看左平衡旋转处理的函数代码。

static final int LH = 1;// 左高
    static final int EH = 0;// 等高
    static final int RH = -1;// 右高
    /** 用于存放各个方法中返回的临时树结点 */
    static BinTree temp = new BinTree();
    /**
     * 处理完成后返回平衡二叉树bt
     * @param bt 待处理的左重右轻的二叉树
     * @return
     */
    static BinTree leftBalance(BinTree bt) {
    	BinTree l, lr;
    	l = bt.lchild;// l指向bt的左子树根节点
    	switch (l.bf) {
    	// 检查左子树的平衡度，并作相应平衡处理
    	case LH:/* 新结点插在bt左孩子的左子树上，需要进行右旋处理 */
    		bt.bf = l.bf = EH;
    		temp = rRotate(bt);
    		bt = temp;
    		break;
    	case RH:/* 新结点插在bt的左孩子的右子树上，需要作双旋处理 */
    		lr = l.rchild;/* lr指向bt左孩子的右子树根 */
    		switch (lr.bf) {/* 修改bt及其左孩子的平衡因子 */
    		case LH:
    			bt.bf = LH;
    			l.bf = EH;
    			break;
    		case EH:
    			bt.bf = l.bf = EH;
    			break;
    		case RH:
    			bt.bf = EH;
    			l.bf = LH;
    			break;
    		}
    		lr.bf = EH;
    		temp = lRotate(bt.lchild);/* 对bt的左孩子作左旋平衡处理 */
    		rRotate(temp);/* 对bt作右旋平衡处理 */
    		bt = temp;
    	}
    	return bt;
    }

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

/**
     * 处理完成后返回平衡二叉树 
     * @param bt 左轻右重的平衡二叉树
     * @return
     */
    static BinTree rightBalance(BinTree bt) {
    	BinTree r, rr;
    	r = bt.rchild;// r指向bt的右子树根节点
    	switch (r.bf) {
    	// 检查右子树的平衡度，并作相应平衡处理
    	case RH:/* 新结点插在bt右孩子的右子树上，需要进行左旋处理 */
    		bt.bf = r.bf = EH;
    		temp = lRotate(bt);
    		bt = temp;
    		break;
    	case LH:/* 新结点输入在bt的右孩子的左子树上，需要作双旋处理 */
    		rr = r.lchild;/* rr指向bt右孩子的左子树根 */
    		switch (rr.bf) {/* 修改bt及其左孩子的平衡因子 */
    		case LH:
    			bt.bf = RH;
    			r.bf = EH;
    			break;
    		case EH:
    			bt.bf = r.bf = EH;
    			break;
    		case RH:
    			bt.bf = LH;
    			r.bf = EH;
    			break;
    		}
    		rr.bf = EH;
    		temp = rRotate(bt.rchild);/* 对bt的右孩子作右旋平衡处理 */
    		bt.rchild = temp;
    		temp = lRotate(bt);/* 对bt作左旋平衡处理 */
    		bt = temp;
    	}
    	return bt;
    }

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

/** 全局变量,用于标识树是否增高 */
    static boolean taller = false;
    
    /**
     * 在平衡二叉树t中若不存在与e有相同关键字的结点则插入t中并返回
     * t，若插入e后使得t失去平衡则需要作平衡处理
     * @param t 平衡二叉排序树
     * @param e 待插入元素
     * @return
     */
    static BinTree insertAVL(BinTree t, int e) {
    	if (null == t) {
    		// 插入新结点。树长高，taller为true
    		t = new BinTree();
    		t.data = e;
    		t.lchild = t.rchild = null;
    		t.bf = EH;
    		taller = true;
    	} else {
    		if (e == t.data) {
    			// 树中已存在和e有相同关键字的结点则不再插入
    			taller = false;
    			return t;
    		} else if (e < t.data) {
    			// 当e小于根结点或子根节点则应继续在t的左子树中进行搜索
    			BinTree lchild = insertAVL(t.lchild, e);
    			t.lchild = lchild;
    			if (!taller)
    				return t;
    			if (taller) {// 已插入到t的左子树中且左子树"长高"
    				switch (t.bf) {// 检查t的平衡度
    				case LH:// 原本左子树比右子树高，需要作左平衡处理
    					temp = leftBalance(t);
    					t = temp;
    					taller = false;
    					break;
    				case EH:// 原本左右子树等高，现因左子树增高而树增高
    					t.bf = LH;
    					taller = true;
    					break;
    				case RH:// 原本右子树比左子树高，现左右子树等高
    					t.bf = EH;
    					taller = false;
    					break;
    				}
    			}
    		} else {// 应继续在t的右子树中进行搜索.
    			BinTree rchild = insertAVL(t.rchild, e);
    			t.rchild = rchild;
    			if (!taller)
    				return t;
    			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:// 原本右子树比左子树高，需要作右平衡处理
    					temp = rightBalance(t);
    					t = temp;
    					taller = false;
    					break;
    				}
    			}
    		}
    	}
    	return t;
    }

对于这段代码来说，在main函数中我们只需要在需要构建平衡二叉树的时候执行如下列代码即可在内存中生成一棵如下图所示相同的平衡的二叉树。

int[] a = { 3, 2, 1, 4, 5, 6, 7, 10, 9, 8 };
    BinTree t = null;
    for (int i = 0; i < a.length; i++) {
    	t = insertAVL(t, a[i]);
    	System.out.println(t+"\n");
    }

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

# 多路查找树(B树) #

我们前面讨论过的数据结构，处理数据都是在内存中，因此考虑的都是内存中的运算时间复杂度。  
但如若我们要操作的数据集非常大，大到内存已经没办法处理了怎么办呢?如数据库中的上千万条记录的数据量、硬盘中的上万个文件等。 在这种情况下，对数据的处理需要不断从硬盘等存储设备中调入或调出内存页面。  
一旦涉及到这样的外部存储设备，关于时间复杂度的计算就会发生变化，访问该集合元素的时间已经不仅仅是寻找该元素所需比较次数的函数，我们必须考虑对硬盘等外部存储设备的访问时间以及将会对该设备做出多少次单独访问。  
试想一下，为了要在一个拥有几十万个文件的磁盘中查找一个文本文件，你设计的算法需要读取磁盘上万次还是读取几十次，这是有本质差异的。此时，为了降低对外存设备的访问次数，我们就需要新的数据结构来处理这样的问题。  
我们之前谈的树，都是一个结点可以有多个孩子，但是它自身只存储一个元素。二叉树限制更多，结点最多只能有两个孩子。  
一个结点只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大(结点拥有子树的个数的最大值)，要么树的高度非常大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多，这显然成了时间效率上的瓶颈，这迫使我们要打破每一个结点只存储一个元素的限制 ，为此号引入了多路查找树的概念。  
**多路查找树，其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。**  
在这里，每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的。为此，我们讲解它的4种特殊形式 : 2-3 树、2-3-4 树、B 树和B+树。

## 2-3 树 ##

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

![Center 15][]

### 2-3树的插入实现 ###

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

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

![Center 16][]

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成为它的右孩子，如下右图所示。

![Center 17][]

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

![Center 18][]

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

![Center 19][]

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

### 2-3树的删除实现 ###

对于2-3树的删除来说，如果对前面插入的理解足够到位的话，应该不是难事了。2-3树的删除也分为三种情况。与插入相反，我们从3结点开始说起。  
1)所删除元素位于一个 3 结点的叶子结点上，这非常简单，只需要在该结点处删除该元素即可，不会影响到整棵树的其他结点结构。如下图所示，删除元素9，只需要将此结点改成只有元素10的2结点即可。

![Center 20][]

2)所删除的元素位于一个2结点上，即要删除的是一个只有一个元素的结点。如果按照以前树的理解，删除即可， 可现在的2- 树的定义告诉我们这样做是不可以的 . 比如下图所示，如果我们删除了结点1，那么结点4本来是一个2结点(它拥有两个孩子 )，此时它就不满足定义了。

![Center 21][]

因此，对于删除叶子是2结点的情况，我们需要分四种情形来处理。  
情形一，此结点的双亲也是2结点，且拥有一个3结点的右孩子。 如下图所示，删除结点1，那么只需要左旋，即6成为双亲，4成为6的左孩子，7是6的右孩子。

![Center 22][]

情形二，此结点的双亲是2结点，它的右孩子也是2结点。如下图，此时删除结点1，如果直接左旋会造成没有右孩子，因此需要对整棵树变形，办法就是，我们目标是让结点7变成3结点，那就得让比7稍大的元素8下来，随即就得让  
比元素8稍大的元素9补充结点8的位置，于是就有了下面中间图，于是再用左旋的方式，变成右图结果。

![Center 23][]

情形三，此结点的双亲是一个3结点。如下图所示，此时删除结点10，意味着双亲12、14这个结点不能成为3结点了 ，于是将此结点拆分，并将12与13合并成为左孩子。

![Center 24][]

情形四，如果当前树是一个满二叉树的情况，此时删除任何一个叶子都会使得整棵树不能满足2-3树的定义。如下图所示，删除叶子结点8时(其实删除任何一个结点都一样)，就不得不考虑要将2-3的层数减少，办法是将8的双亲7和其在子树6合并为3结点，再将14与9合并为3结点 ，最后成为右图的样子。

![Center 25][]

3)所删除的元素位于非叶子的分支结点。此时我们通常是将树按中序遍历后得到此元素的前驱或后继元素，考虑让它们来补位即可。

如果我们要删除的分支结点是2结点。如下图所示我们要删除4结点，分析后得到它的前驱是1后继是6，显然，由于 6、7是3结点，只需要用6来补位即可，如下右图所示。

![Center 26][]

如果我们要删除的分支结点是3结点的某一元素，如下图所示我们要删除12、14 结点的12，此时，经过分析，显然应该是将是3结点的左孩子的10上升到删除位置合适。

![Center 27][]

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

## 2-3-4树 ##

有了2\-3树的讲解，2-3-4树就很好理解了，它其实就是2-3树的概念扩展，包括了4结点的使用。一个4结点包含小中大三个元素和四个孩子(或没有孩子)，一个4结点要么没有孩子，要么具有4个孩子。如果某个4结点有孩子的话，左子树包含小于最小元素的元素;第二子树包含大于最小元素，小于第二元素的元素;第三子树包含大于第二元素，小于最大元素的元素;右子树包含大于最大元素的元素。

## B树 ##

我们本节名称叫B树，但到了现在才开始提到它，似乎这主角出来的实在大晚了，可其实，我们前面一直都在讲B树。  
B树(B-Tree)是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶(order) ，因此，2-3树是3阶B树， 2-3-4树是4阶B树。

一个m阶的B树具有如下属性:  
• 如果根结点不是叶结点，则其至少有两棵子树。  
• 每一个非根的分支结点都有k-l个元素和k个孩子，其中\[m/2\]<=k<=m。  
每一个叶子结点n都有k-l个元素，其中\[m/2\]<=k<=m。  
• 所有叶子结点都位于同一层次。  
•所有分支结点包含下列信息数据(n，A0，K1，A1，K2，......KN，AN)，其中:Ki(i=1，2…,n)为关键字，且Ki(i =1，2…，n);为关键字，且Ki<K(i+1)(i=0，2，…，n)为指向子树根结点的指针，且指针Ai所指子树中所有结点的关键字均小于Ki(i=1，2，…，n)，An所指子树中所有结点的关键字均大于Kn，n( \[m/2\]-1<=n<=m-l)为关键字的个数(或n+1为子树的个数)。

例如，2-3-4树中插入9个数后的图转成 B 树示意就如下图的右图所示。左侧灰色方块表示当前结点的元素个数。

![Center 28][]

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

## B+树 ##

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

![Center 29][]

为了能够解决所有元素遍历等基本问题，我们在原有的B树结构基础上，加上了新的元素组织方式，这就是B+树。  
B+树是应文件系统所需而出的一种B树的变形树，注意严格意义上讲，它其实已经不是第之前所定义的树了。在B树中 ，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者(叶子结点)中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。  
例如下图所示，就是一棵B+树的示意，灰色关键字即是根结点中的关键字  
在叶子结点再次列出，并且所有叶子结点都链接在一起。

![Center 30][]

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

**引用《大话数据结构》作者：程杰**

[Center]: /images/20220616/cc305f34f4e944f4813b032bbdf68ef0.png
[Center 1]: /images/20220616/955bbdeadbe34f4fb53b799d13c07ca9.png
[Center 2]: /images/20220616/10414450c7774d49bad5cf2549274e71.png
[Center 3]: /images/20220616/ed7e3e1fc9e04cad905ac241b266c6a9.png
[Center 4]: /images/20220616/53ca290b2e154a56ad11a7d104737a47.png
[Center 5]: /images/20220616/6c38224ad5a34e15a10ae9d9c368a4b1.png
[Center 6]: /images/20220616/143787132680434998fd4f1bae87f4ff.png
[Center 7]: /images/20220616/01f0b462dafb43f88ec1e18f51985956.png
[Center 8]: /images/20220616/986e2a8f9af44ddcb3b56369e51bcd8f.png
[Center 9]: /images/20220616/84f9ff9af9574d69812b31470fd5daa2.png
[Center 10]: /images/20220616/07615eacece947fbaf24dde0262f51b4.png
[Center 11]: /images/20220616/853b39a7c2e74ff9876e18ae4dca61ab.png
[Center 12]: /images/20220616/db0ff36482af4142bcf37240885ae7ae.png
[Center 13]: /images/20220616/026232c0809b4e5db6f174a0a1507e64.png
[Center 14]: /images/20220616/d0c07cb820bd4939ad1056491dbd27e9.png
[Center 15]: /images/20220616/009c09b7e42d45aea5daee282740ab38.png
[Center 16]: /images/20220616/abd36bba68da48afa872a5074ba1f1c1.png
[Center 17]: /images/20220616/fa334332e5fe4e1ba4cc68215b65acc3.png
[Center 18]: /images/20220616/326e9e842198466596bb03a9ab1e258a.png
[Center 19]: /images/20220616/c0fbbe8c46114d3ca39fb3c4f5162b47.png
[Center 20]: /images/20220616/41c9cae722ba4c93b5c53895bd6526a4.png
[Center 21]: /images/20220616/eff43bf1e3b04ac79dceb79709486707.png
[Center 22]: /images/20220616/f8a782b7a2bf4177b5b81c185ba7c42e.png
[Center 23]: /images/20220616/bde4c8405bfe42efa15766ab2c2a318e.png
[Center 24]: /images/20220616/0a7d84717770443a8272e904f173a9b8.png
[Center 25]: /images/20220616/dca683b2c0bf410ab185e8c524e5eebd.png
[Center 26]: /images/20220616/925d3c32af3f424a88b094bf43507613.png
[Center 27]: /images/20220616/2496bf63102342ea9f754a69ea6b5981.png
[Center 28]: /images/20220616/15955124d0804b3ca76e6655b612d6de.png
[Center 29]: /images/20220616/3d5a31ae0b7b4381afae49d466471125.png
[Center 30]: /images/20220616/490d0a92a77e4817bf55c18b60eeb1ac.png