将数列 24,15, 38, 27, 121,76,130)的各元素依次插入一棵初始为空的二叉排序树中,等概率情况下该 二叉排序树查找成功的平均查找长度为
时间: 2023-11-24 16:08:05 浏览: 72
将这些数插入二叉排序树的过程如下:
```
24
\
15
\
\
38
/ \
27 121
\
\
76
\
130
```
根据二叉排序树的性质,左子树中的所有节点的值都小于根节点的值,右子树中的所有节点的值都大于根节点的值。因此,在等概率情况下,每个节点被查找到的概率都是相等的,即 $p_i = \frac{1}{n}$,其中 $n$ 是树中节点的个数。
根据二叉排序树的查找过程,查找成功的平均查找长度为:
$$
ASL=\sum_{i=1}^{n}p_i \cdot d_i
$$
其中 $d_i$ 是节点 $i$ 的深度(根节点的深度为 $1$)。因此,我们需要先计算出每个节点的深度,然后再根据上面的公式计算平均查找长度。
根据上面的插入过程,各节点的深度如下:
```
24 (1)
\
15 (2)
\
\
38 (3)
/ \
(4) 27 121 (4)
\
\
76 (5)
\
130 (6)
```
因此,各节点的深度为 1、2、3、4、4、5、6。根据上面的公式,平均查找长度为:
$$
\begin{aligned}
ASL&=\sum_{i=1}^{n}p_i \cdot d_i \\
&=\frac{1}{7} \cdot (1+2+3+4+4+5+6) \\
&=\frac{25}{7} \\
&\approx 3.57
\end{aligned}
$$
因此,等概率情况下该二叉排序树查找成功的平均查找长度为 $\frac{25}{7} \approx 3.57$。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)