查找失败asl值这是本人的经验之谈：百试不爽!用12个字母表示结点：ABCDEFGHIJKL画二叉查找树：成功：失败F:1*1=1/\CI:2*2=4/\/ADGK:3*4=12\\\/BEHJL:4*5=204*3=125*10=50加和：37

Question

查找失败asl值
这是本人的经验之谈：百试不爽!
用12个字母表示结点：
A B C D E F G H I J K L
画二叉查找树：成功 ：失败
F :1*1=1
/ \
C I :2*2=4
/ \ / A D G K :3*4=12
\ \ \ / B E H J L :4*5=20 4*3=12
5*10=50
加和：37 62
结论：37/12 62/13
不会的多看两遍!最好自己画
还有为什么50只加12不加前面的几个数.另外,麻烦解释一下查找失败求ASL值的原理.

Answer 1

对照图表仔细研究
这里的回复不能把格式很清晰的画出来,让你感到困惑很抱歉．
拿第２层来解释（C I :2*2=4 ）
比如你查找第二次成功的话,即Ｃ和Ｉ中有一个值是你想要的那么平均查找长度就是２＊２＝４
查找成功的值有1*1=1　2*2=4　3*4=12 4*5=20
查找到B E H J L,不是还有３个分支是查找失败么,所以有4*3=12
查找完整个树,发现没有一个值是符合要求的,可以理解成第５层全失败5*10．其中的１０是因为第４层只有B E H J L５个节点,每个节点可以有２个分之．所以是１０
以上,希望对你有所帮助．