已知由(30,22,56,15,25,50,60)序列构成的二叉排序树,等概率下查找成功时的平均查找长度为()。 A. 17/7 B. 16/7 C. 19/7 D. 18/7
时间: 2024-03-25 17:40:57 浏览: 12
首先,我们根据给出的序列构造二叉排序树,得到如下的一棵树:
```
30
/ \
22 56
/ \ / \
15 25 50 60
```
由于这是一棵二叉排序树,因此对于任意节点 $x$,它的左子树中所有节点的值都小于 $x$,它的右子树中所有节点的值都大于 $x$。因此,在查找一个节点 $x$ 的过程中,如果当前节点的值比 $x$ 大,就只需要在左子树中查找;如果比 $x$ 小,就只需要在右子树中查找。因此,查找一个节点的平均查找长度等于从根节点开始到这个节点的路径长度的期望值。
对于这棵二叉排序树,我们可以计算出每个节点的深度(即从根节点到该节点的路径长度),并且计算出每个节点的概率。这里假设概率是等概率的,即每个节点被查找的概率都是 $1/7$。那么,每个节点的深度和概率如下:
| 节点 | 深度 | 概率 |
| ---- | ---- | ---- |
| 30 | 1 | 1/7 |
| 22 | 2 | 1/7 |
| 56 | 2 | 1/7 |
| 15 | 3 | 1/7 |
| 25 | 3 | 1/7 |
| 50 | 3 | 1/7 |
| 60 | 3 | 1/7 |
因此,查找成功时的平均查找长度为:
$$\frac{1}{7}(1\cdot 1 + 2\cdot 2 + 2\cdot 2 + 3\cdot 1 + 3\cdot 1 + 3\cdot 1 + 3\cdot 1) = \frac{16}{7}$$
因此,答案是 B. 16/7。