假设一个有序序列 { 12, 25, 46, 62, 78, 80 }, 画出进行二分查找的判定树,并计算查找成功的ASL和查找不成功的ASL。
时间: 2024-01-18 22:03:44 浏览: 257
二分查找树
下面是二分查找的判定树:
```
62
/ \
25 78
/ \ / \
12 46 80 nil
/ \
nil nil
```
其中,nil表示空节点。
对于查找成功的情况,有:
- 查找12:路径长度为1,ASL为1
- 查找25:路径长度为1,ASL为1
- 查找46:路径长度为2,ASL为2/3
- 查找62:路径长度为0,ASL为0
- 查找78:路径长度为1,ASL为1
- 查找80:路径长度为2,ASL为2/3
所以查找成功的ASL为 (1+1+2/3+0+1+2/3) / 6 = 7/9。
对于查找不成功的情况,假设要查找的数为50,那么它会落在节点46和62之间,路径长度为3,ASL为3/6 = 1/2。
因此,查找成功的ASL为7/9,查找不成功的ASL为1/2。
阅读全文