将关键字序列(10,2,26,4,18,24,21,15,8,23,12,14)依次插入到初态为空的二叉排序树中,请: (1)画出所得到的树T; (2)计算等概率情况下查找成功的平均查找长度ASLsucc。
时间: 2023-11-10 12:06:20 浏览: 61
(1) 将关键字序列依次插入到二叉排序树中,得到的树 T 如下图所示:
```
10
/ \
2 26
/ /
4 18
/ \
15 24
/ \
12 23
/
21
/
14
/
8
```
(2) 计算等概率情况下查找成功的平均查找长度 ASLsucc。
首先,我们需要计算出树 T 的深度 d 和叶子结点个数 n。从根结点开始,向下遍历树 T,可以发现最大深度为 5,因此 d = 5。叶子结点的关键字是 2、4、8、12、14、15、21、23、24、26 和 10,共 11 个,因此 n = 11。
接下来,我们可以使用公式 ASLsucc = (Σ(di+1)) / n 来计算等概率情况下查找成功的平均查找长度,其中 di 是查找到第 i 个叶子结点的路径长度。
对于每个叶子结点,我们可以沿着从根结点到该叶子结点的路径计算出路径长度 di。例如,对于关键字 2,其路径为 10 -> 2,路径长度为 2。因此,每个叶子结点的路径长度如下表所示:
| 关键字 | 路径长度 di |
|--------|-------------|
| 2 | 2 |
| 4 | 3 |
| 8 | 4 |
| 12 | 4 |
| 14 | 5 |
| 15 | 4 |
| 21 | 5 |
| 23 | 4 |
| 24 | 4 |
| 26 | 3 |
| 10 | 1 |
因此,等概率情况下查找成功的平均查找长度 ASLsucc 为:
ASLsucc = (Σ(di+1)) / n
= (2+3+4+4+5+4+5+4+4+3+1) / 11
= 3.727
因此,等概率情况下查找成功的平均查找长度为 3.727。