二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(12)

情况 ⑶：结点 *p的平衡因子不为0，且较矮的子树又被缩短，则出现了不平衡，结点 *p为“危急结点”。此时，需进行平衡旋转来恢复平衡。让指针q指向结点 *p的较高子树的根结点，则根据结点 *p和 *q的平衡因子值，有如下三种平衡旋转的操作：? 如果结点 *q的平衡因子为0，则只需要做一个单旋转就可以恢复结点 *p的平衡。图9-20 3 - ? 所示的是 *p的左子树的高度被缩短、进行RR型单旋转的情形。? 如果结点 *p的平衡因子与结点 *q的平衡因子相同，则也只需做一个单旋转就可恢复结点 *p的平衡，旋转调整后，结点 *p和结点 *q的平衡因子均改为0。图9-20 3 - ? 所示的是结点 *p和结点 *q的平衡因子均为 -1、进行LL型单旋转的情形。? 如果结点 *p与结点 *q的平衡因子的符号相反，则需做一个双旋转来恢复平衡，先围绕 *q旋转、再围绕 *p旋转。其他结点的平衡因子做相应修改。图9-20 3 - ? 所示的是结点 *p和结点 *q的平衡因子分别为 +1与 -1、进行RL型双旋转的情形。在上述情况 ⑶的三种情形中，旋转的方向取决于结点 *p的哪一棵子树的高度被缩短，在图9-20中只是给出了某些可能的情况，实际上还有与之对称的情况，其处理方法原则上是一致的。

例9.11 图9-21给出了在L树中删除关键字为40和80结点时所做的平衡调整过程。另外，删除和插入之间的一个重要差别是：删除一个结点时，可能需要多次平衡旋转 即p沿着到根的反向路径逐层地指向更高辈份的祖先结点的过程中可能要进行多次平衡旋转的处理 ，而插入一个结点至多平衡旋转一次。四、L树的性能分析显然，L树的查找、插入和删除运算的时间代价都不会超过L树的高度，设含有n个结点的L树的高度为h。则其时间复杂度应为O h 。这与一般的二叉排序树相同。但对于一棵不一定平衡的二叉排序树来说，树可能的最大高度是h n-1，因此，最坏情况下，在二叉排序树中进行这几种运算的时间复杂度为O n 。那么，对于L树，h的最大值是多少呢？设Nh是高度为h的L树中所含有的最少结点数。容易得出：N-1 0 空树 , N0 1 仅有一个根结点 ， Nh Nh-1 + Nh-2 + 1, h 0这个递归定义的式子与Fibonacci数列 F0 0，F1 1，Fn Fn-1 + Fn-2 非常相似并且两者的项值之间有对应关系。用归纳法可以证明，当h≥0时，有Nh Fh+3 -1成立。而且，Fibonacci数满足渐近公式：由此可得近似公式：整理得两边取对数由换底公式可得由此L树的高度h的上限值，可得出其复杂度应为O log2n 。

9.3.4 B－树与B + 树前面讲过的二叉排序树、最佳二叉排序树和L树上的查找均属于内部查找，它们仅适合于组织较小的、在内存中的索引。而对于存放在外存上较大的文件系统，用二叉树来组织索引就不太适合了。若以结点作为内外存交换的单位，则在查找过程中平均需要对外存进行log2n次访问，这显然是非常费时的。因此，对于外部查找，在大型的文件检索系统中大量使用的是每个结点含有多个关键字的B－树或B+ 树做文件索引。一、m路静态查找树对于外部查找的问题，组织索引一般不采用二叉树而是采用多路树，这样可明显地减少访问外存的次数。考虑图9-22所示的大型二叉查找树，并想象它已经存储在外存中。如果简单地应用已学过的内部查找方法，则大约要做log2n次的外存访问，才能完成查找。当结点个数n为100万时，则需要做20次左右的访外寻找。但假如把这个图按7个结点一组来构成新的结点—“页块”，如图9-22中所示的三角形阴影部分。如果现在一次访问一个页块，则仅需前述次数的三分之一，所以查找大约快了3倍。以这种方式把结点组合成页块，实际上把图中的二叉树变成了八叉树，每个页块结点处有8路分支。如果让页块更大一些，即带有更多路的分支，就能以更少的访外次数来完成查找。

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