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

现在我们来讨论在查找所有内部结点和外部结点的概率均相等的情况下，二叉排序树的查找效率。前边已经说过，二叉排序树的查找过程就是首先用待查的关键字K与根结点的关键字进行比较，若相等，则找到了要查找的关键字，即查找成功；若不等且待查的关键字K小于根结点的关键字，则下一次与根的左子树的根进行比较；否则与根的右子树的根比较。如此递归地进行下去，直到某一次比较相等，即查找成功；或者一直比较到树叶都不相等，即查找失败。在查找过程中，每进行一次比较，就进入下面的一层，因此，对于成功的查找，其比较的次数就是关键字所在的层次加1。对于不成功的查找，被查找的关键字属于哪个外部结点所代表的可能关键字集合，比较次数就等于此外部结点的层数。二叉排序树的建立在等概率的情况下，在二叉排序树里，查找一个关键字的平均比较次数为 其中li 是第i个内部结点的层数； li' 是第i个外部结点的层数。 ⑴我们把平均比较次数最小，也就是平均查找长度ASLn为最小的二叉排序树称作最佳二叉排序树。因为对于给定的关键字集合，n为确定值，因此，要使平均比较次数ASLn为最小，就是要使内部路径长度I为最小。然而，在一棵二叉树中，路径长度为0的结点仅有一个，路径长度为1的结点至多有两个，路径长度为2的结点至多有四个，…，路径长度为k的结点至多有2k个 k 0, 1, 2, … ，因此，对于有n个结点的二叉树，其内部路径长度I的最小值应为如下序列0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4 ,4, …前n项的和。

即 ⑵（ 注：⑵式的证明在本小节的最后给出 ）将 ⑵ 式代入 ⑴ 式，则有这种最佳二叉排序树实际上就是以前讲过的二叉判定树，因此，可以用折半查找的方法来构造最佳二叉排序树。具体方法是：1. 将给定的关键字集合里的关键字排序；2. 用折半查找法依次查找这些关键字，并把在查找过程中遇到的在二叉排序树里还没有的关键字依次插入到二叉排序树中。例9.7对于给定的关键字集合 5, 7, 4, 9, 3, 2, 11, 16, 21, 15 ，构造最佳二叉排序树的过程如下：首先将给定的关键字集合 5, 7, 4, 9, 3, 2, 11, 16, 21, 15 n 10 里的关键字进行排序，可得到如下的有序序列2, 3, 4, 5, 7, 9, 11, 15, 16, 21然后按方法2，从1到n依次在二叉排序树中查找这些关键字，由于查找过程中使用的是折半查找的方法，所以在不断折半中所遇到的各中点上的关键字，若二叉排序树里没有，则依次插入到二叉排序树中。最后可得到图9-10所示的最佳二叉排序树。从形状上看，最佳二叉排序树与完全二叉树很相似，除下面一层外其余各层的结点数均为满额,只有最下面一层可能不满,但可以不像完全二叉树那样向左集中。

这是因为：虽然结点在同层上的位置不同，但结点的路径长度不变 相等 ，从而不会导致最佳二叉排序树的内部路径长度I的变化。反过来，如果关键字按值不减 或不增 的顺序依次插入到二叉排序树中，则将得到退化为线性的二叉排序树 如图9-11所示 。对这样的二叉排序树进行查找，实际上就是对线性表的顺序查找，平均查找长度为 n 。如果将关键字集合中的关键字按任意次序插入到二叉排序树中，它从查找效率会怎样呢？平均查找长度是接近最坏情况 n 呢？还是接近最好的情况 log2n ？可以证明：对n! 种二叉排序树进行平均，得到的平均查找长度仍是 log2n ，也就是说大多数的二叉排序树与最佳二叉排序树的查找效率差别不大，只有少数情况，查找的平均查找长度为 n 。注：以下是 ⑵ 式的证明：首先证明一个求和公式： nan －证：因为 － － － － － － nan － a1 － nan －故移项后有 nan －现在证明： log2 k n+1 log2 n － 2 log2 n + 1 + 2 令 ak log2 k ， 于是 ak+1 － ak n log2 n － n log2 n － n log2 n － + log2 n n +1 log2 n － 2 log2n +1 － 2 / 2 – 1 n +1 log2 n － 2 log2n +1 + 2 。

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