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

判定树的形态只与表中的结点个数n有关，而与表中的n个结点具体取值无关。例如，10 n 个结点的有序表R[1..10] 对应的二叉判定树如图9-3所示。有序表中的每一个结点的关键字都对应树中的一个椭圆形结点，并把关键字的值R[i].key 1≤i≤n 写在其中。椭圆形结点外边标出的数字是该结点在表中的位置 下标值 。当椭圆形结点出现空的子树时，就增补新的、特殊的虚拟结点 图中的方形结点 。显然它们在树中均为树叶，故称其为外部结点，相对应的原来二叉树中的结点 椭圆形结点 称为内部结点。这种增加了外部结点的二叉树叫作扩充二叉树 扩充二叉树的概念在第5章讲述Huffman树时已经介绍过 。在扩充的二叉树中不存在度为1的结点，且外部结点的个数等于内部结点的个数加1。在扩充二叉树中，关键字最小的内部结点的左子女 外部结点 代表着其值小于该内部结点的所有可能关键字的集合；关键字最大的内部结点的右子女 外部结点 代表着其值大于该内部结点的所有可能关键字的集合；除此之外的每个外部结点代表着其值处于原来二叉树中两个相邻结点关键字之间的所有可能关键字的集合。例如在图9-3所示的二叉树里，根结点的左子树中的最右下结点－外部结点表示着值在R[4].key与R[5].key之间的所有可能的关键字的集合 图中方框结点中标为：R[4]～R[5]，这是一种简记法，它表示的是一个开区间： R[4].key, R[5].key 。

树中内部结点R[i].key到左 右 子女的分支上的标记' ' ' ' 表示：当给定值K R[i].key K R[i].key 时，应沿着左 右 分支进入左 右 子树，继续用K与左 右 子女进行比较；若相等，则查找过程结束 查找成功 ，否则继续用K的值与下一层内结点进行比较。如果经比较后进入了外部结点中 即落入到方框结点中 ，则以查找失败而告终。由图示不难看出，对于成功的查找，其比较次数为与给定值K相等的内部结点所在的层数加1；对于失败的查找，给定值K属于哪个外部结点所代表的可能关键字的集合，其比较次数就等于的此外部结点的层数。例如在图9-3中，如果给定值K与椭圆形结点外边标出的数字6的内部结点相等，即K R[6].key，则比较次数为该结点的层数加1，即为3。如果给定值K在R[4].key与R[5].key之间，经4次比较后必落入内部结点R[4].key的右子女这个外部结点之中，而该外部结点的层数为4，所以对于这次失败的查找其比较次数也正好比较4次。借助于二叉判定树，可以很容易地求得折半查找的平均查找长度。不失一般性，不妨设内部结点的总数 即有序表的长度 为n 2h -1，则对应的判定树仅由内部结点所构成二叉树的是高度为h-1的满二叉树，h -1 log2 n+1 -1，h log2 n+1 。

树中第k层有2k个结点，查找它们所需的比较次数为k+1。假设每个结点被查找的概率相等，则查找成功的平均查找长度为：因此，折半查找成功时的平均查找长度为O log2n 。折半查找在查找失败时所做的比较次数不会超过判定树的高度。在最坏情况下查找成功的比较次数也不会超过判定树的高度。因为判定树中度小于2的结点至多可能在最下面的两层上 不计外部结点 ，所以，n个结点的判定树与n个结点的完全二叉树的高度相同，即为 log2 n+1 -1。这也就是说，折半查找的平均查找长度与最大查找长度相差不多，这是由于比较次数越大，所能涉及的结点个数越多，能涉及的结点个数是比较次数的指数函数。折半查找的优点是比较次数少，查找效率高，但它要求表顺序存储且按关键字排序。而排序是一种很费时的运算，即使采用高效的排序方法也要花费O nlog2n 的时间。另外，为保持表的有序性，在顺序的结构里进行插入和删除运算都需要移动大量的结点。因此，折半查找适用于一经建立就很少改动，而经常进行的是查找操作的线性表。对于那些查找少而又经常要改动的线性表，可采用链接存储结构、进行顺序查找的方法。9.2.3 分块查找如果要处理的线性表即希望有较快的查找速度又需要适合于动态变化，则可以采用分块查找的方法。

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