已知一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功和查找不成功情况下的平均查找长度。
时间: 2023-09-01 18:13:38 浏览: 105
二叉排序树 平均查找长度的操作
插入顺序为25、18、46、2、53、39、32、4、74、67、60、11。初始为空的二叉排序树如下图所示:
```
25
/ \
18 46
/ / \
2 39 53
\ /
4 32
\
74
/
67
/
60
/
11
```
在等概率的情况下查找成功和查找不成功情况下的平均查找长度分别为:
对于查找成功的情况,每个元素被查找到的概率均为1/12,因此平均查找长度为(1+2+2+3+3+3+3+4+4+4+4+5)/12=3.08。
对于查找不成功的情况,需要遍历到每个叶子结点才能确定查找失败,因此平均查找长度为(4+3+3+4+4+4+4+5+5+5+5+6)/12=4.42。
阅读全文