二叉排序树查找选择题_二叉排序树查找算法_c语言哈希查找算法

15.4.5 平均查找长度(ASL)的计算举例

例3－5 一有序表的关键字序列是（11，16，37，51，55，76，88，90，101，105）采用折半查找求其等概率情况下，查找成功的平均查找长度。

解按照折半查找算法，对序列中10个元素的查找过程如下：

⑴mid =（1＋10）/2 查找到元素55。

⑵mid =（1＋4）/2 查找到元素16。

或者mid =（6＋10）/2 查找到元素90。

⑶mid =（1＋1）/2 查找到元素16。

或者mid =（3＋4）/2 查找到元素37。

或者mid =（6＋7）/2 查找到元素76。

或者mid =（9＋10）/2 查找到元素101。

⑷mid =（1＋10）/2 查找到元素51。

或者mid =（7＋7）/2 查找到元素105。

这棵二叉树又称为折半查找判定树。

从判定树上可知，查找某一个元素所要进行的比较次数等于该元素结点在判定树中的层数。故：

ASL ＝ （3＋2＋3＋4＋1＋3＋4＋2＋3＋4）/10 = 2.9

从上例可以看出，折半查找成功的平均查找长度与序列中的具体元素无关，只取决于序列中元素的数目。二叉排序树查找算法所以，折半查找判定树只与查找表中元素的数目有关。

例 3－6 已知长度为10的表是（Jan，Feb，Mar，Apr，May，June，July，Aug，Sept，Oct），按表中元素的顺序依次插入，组织成包含这10个元素的二叉排序树，并求其在等概率情况下二叉排序树查找成功的平均查找长度。二叉排序树查找算法

解 所得二叉排序树的形状见下图。

根据二叉排序树查找算法，查找某一个元素所要进行的比较次数等于该元素在二叉树中的层数。故：

ASL = （1＋2＋2＋3＋3＋3＋4＋4＋4＋5）/10= 3.1

二叉排序树查找成功的平均查找长度取决于二叉排序树的形状，而二叉排序树的形状既与结点数目有关，更取决于建立二叉排序树时结点的插入顺序。

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