java实现常见查找算法(7)

对于这段代码来说，在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)。这显然是比较理想的一种动态查找表算法。

我们前面讨论过的数据结构，处理数据都是在内存中，因此考虑的都是内存中的运算时间复杂度。

cpu只能访问存储在内存中的数据，外存中的数据只有先调入内存后才能被cpu访问和处理。此外，内存存储的数据一般和传统存储的数据有相对性，即内存存储的数据一般有更低的时效性，通常在内存中，每一个数据都有相关规定的有效时间和有效期限，假如数据存储时间或读取时间超过这个有效时间以外，则原有的数据就会失效，同时产生新的数据进行替换和替代。仔细一想，uwf的功能就是保护硬盘，一旦开启保护后，那个分区的一切操作都会写入到内存当中，既然就所有的操作都通过内存，内存的速度比硬盘快很多，运行速度快也是自然的了，由于对c盘系统的任何操作都不真实的写入c盘，这就能使系统永远保持新鲜，不会越来越慢，这对那些一辈子只装一次系统的人来说真是再好不过了。

一旦涉及到这样的外部存储设备，关于时间复杂度的计算就会发生变化，访问该集合元素的时间已经不仅仅是寻找该元素所需比较次数的函数，我们必须考虑对硬盘等外部存储设备的访问时间以及将会对该设备做出多少次单独访问。

试想一下，为了要在一个拥有几十万个文件的磁盘中查找一个文本文件，你设计的算法需要读取磁盘上万次还是读取几十次，这是有本质差异的。此时，为了降低对外存设备的访问次数，我们就需要新的数据结构来处理这样的问题。

我们之前谈的树，都是一个结点可以有多个孩子，但是它自身只存储一个元素。二叉树限制更多，结点最多只能有两个孩子。

一个结点只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大(结点拥有子树的个数的最大值)，要么树的高度非常大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多，这显然成了时间效率上的瓶颈，这迫使我们要打破每一个结点只存储一个元素的限制 ，为此号引入了多路查找树的概念。

多路查找树，其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。

在这里，每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的。为此，我们讲解它的4种特殊形式 : 2-3 树、2-3-4 树、B 树和B+树。

2-3树是这样的一棵多路查找树;其中的每一个结点都具有两个孩子(我们称它为2结点)或三个孩子(我们称它为3结点) 。

一个2结点包含一个元素和两个孩子(或没有孩子)，且与二叉排序树类似，左子树包含的元素小子该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个2结点要么没有孩子，要有就有两个，不能只有一个孩子 。一个3结点包含一小一大两个元素和三个孩子(或没有孩子)，一个3结点要么没有孩子，要么具有3个孩子。如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。并且2-3树中所有的叶子都在同一层次上。如下图，就是一棵有效的2-3树。

事实上，2-3树复杂的地方就在于新结点的插入和已有结点的删除。毕竟，每个结点可能是2结点也可能是3结点，要保证所有叶子都在同一层次，是需要进行一番复杂操作的。

但由于b-树结点中的关键字个数必须≥ceil(m／2)-1，因此，每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则要产生结点的“分裂”，。堆排序是一种树形选择排序，在排序过程中，将a[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。set和map容器都有基于哈希存储和排序树的两种实现版本，基于哈希存储的版本理论存取时间复杂度为o(1)，而基于排序树版本的实现在插入或删除元素时会按照元素或元素的键（key）构成排序树从而达到排序和去重的效果。

2-3树插入可分为三种情况。

1) 对于空树，插入一个2结点即可，这很容易理解。

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

3)要往3结点中插入一个新元素。 因为3结点本身已经是2-3树的结点最大容量(已经有两个元素)，因此就需要将其拆分，且将树中两元素或插入元素的三者中选择其一向上移动一层。复杂的情况也正在于此。

双链表的插入操作在双链表中p所指的结点之后插入结点*s，其指针的变化过程如图2-9所示。如图4.6所示： 图4.6 新结点在双链表尾部插入1操作继续进行，结点91的后继指针指向新结点100。（注意：在使用这个函数获得尾结点指针时，必须在每次插入结点元素后重新获得，因为链表尾部结点是会随着结点的插入而发生变化）。

另一种情况，如下图所示，需要向左图中插入元素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-3树的删除来说，如果对前面插入的理解足够到位的话，应该不是难事了。2-3树的删除也分为三种情况。与插入相反，我们从3结点开始说起。

1)所删除元素位于一个 3 结点的叶子结点上，这非常简单，只需要在该结点处删除该元素即可，不会影响到整棵树的其他结点结构。如下图所示，删除元素9，只需要将此结点改成只有元素10的2结点即可。

2)所删除的元素位于一个2结点上，即要删除的是一个只有一个元素的结点。如果按照以前树的理解c 二叉排序树，删除即可， 可现在的2- 树的定义告诉我们这样做是不可以的 . 比如下图所示，如果我们删除了结点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的双亲7和其在子树6合并为3结点，再将14与9合并为3结点 ，最后成为右图的样子。

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

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

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

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

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

我们本节名称叫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为子树的个数)。

如图4.3所示： 图4.3 结点在链表中间插入1操作继续进行，将结点62的后继指针指向结点91，同时去掉它的结点91到46的前驱指针。如图4.6所示： 图4.6 新结点在双链表尾部插入1操作继续进行，结点91的后继指针指向新结点100。[例如]，在图4.2(c)的b-树中删去关键字37之后，双亲b结点中剩余信息(“指针c”)应和其双亲*a结点中关键字45一起合并至右兄弟结点*e中，删除后的b-树如图4.2(d)所示。

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-106859-7.html