数据结构之算法（二叉排序树的查找分析） 在二叉排序树上查找其关键字等于给定值的结点的过程,恰是走了一条从根结点到该结点的路径的过程,和给定值比较的关键字个数等于路径长度加1(或结点所在层次数),因此,和折半查找类似,与给定值比较的关键字个数不超过树的深度。然而,折半查找长度为n的表的判定树是惟一的,而含有n个结点的二叉排序树却不惟一。图1中(a)和(b)的两棵二叉排序树中结点的值都相同,但前者由关键字序列(45,24,53,12,37,93)构成,而后者由关键字序列(12,24,37,45,53,93)构成。(a)树的深度为3,而(b)树的深度为6。再从平均查找长度来看,假设6个记录的查找概率相等,为1/6,则(a)树的平均查找长度为 ![ASL_{（a）} =\frac{1}{6} [1 + 2 + 2 + 3 + 3 + 3] = 14/6](https://sigusoft.com/wp-content/themes/justnews/themer/assets/images/lazy.png "二叉排序树的查找算法代码实现_折半查找和二叉排序树的时间性能插图1")
而(b)树的平均查找长度为： ASL_{(b)} = \frac{1}{6} [1 + 2 + 3 + 4 + 5 + 6] = 21/6
图1 不同形态的二叉查找树（a）关键字排序为（45,24,53,12,37,93）的二叉排序树（b）关键字排序为（12,24,37,45,53,93）的单支树 因此,含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树。树的深度为n,其平均查找长度为 (和顺序查找相同),这是最差的情况。显然,最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和 成正比。那么,它的平均性能如何呢? 假设在含有n(n≥1)个关键字的序列中,i个关键字小于第一个关键字,n-i-1个关键字大于第个关键字,则由此构造而得的二叉排序树在n个记录的查找概率相等的情况下,其平均查找长度为 P（n，i）= [1 + i * (P(i) + 1) + (n – i -1 )(P(n – i – 1)+1)] (9-17) 其中P(i)为含有主个结点的二叉排序树的平均查找长度,则P(i)＋1为查找左子树中每个关键字时所用比较次数的平均值,P(n一i一1)＋1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的,即任一个关键字在序列中将是第1个,或第2个……,或第n个的概率相同,则可对(9-17)式从主等于0至n-1取平均值
容易看出上式括弧中的第一项和第二项对称。又，i=0时iP(i)=o,则上式可改写为
由此可见,在随机的情况下,二叉排序树的平均查找长度和 logn是等数量级的。然而,在某些情况下(有人研究证明,这种情况出现的概率约为46.5%)0,尚需在构成二叉排序树的过程中进行“平衡化”处理,成为二叉平衡树。 如果你想学编程，可以来小编的C/C++编程秃头俱乐部
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/28979.html
