给定序列{3,5,7,9,11,13,15,17}:按表中元素的顺序依次插入一棵初始为空的二叉搜索树。画出插入完成后的二叉搜索树,并求其在等概率情况下搜索成功的平均搜索长度;
时间: 2023-12-06 19:03:22 浏览: 180
二叉排序树 平均查找长度的操作
二叉搜索树的结构是左子树的所有节点值都小于根节点,右子树的所有节点值都大于根节点。按照给定的序列依次插入节点,我们可以得到以下的二叉搜索树:
```
3
\
5
\
7
\
9
\
11
\
13
\
15
\
17
```
在等概率情况下搜索成功的平均搜索长度可以用以下公式计算:
$$
E = \frac{\sum_{i=1}^{n}dep_i}{n}
$$
其中 $dep_i$ 表示搜索元素 $i$ 时的深度,$n$ 表示二叉搜索树中元素的个数。
对于本题中的二叉搜索树,它的深度为 $8$,元素个数为 $8$。我们可以用递归的方式计算每个节点的深度并求和,得到:
$$
E = \frac{1+2+2+3+3+4+4+4}{8} = \frac{23}{8} \approx 2.88
$$
因此,在等概率情况下搜索成功的平均搜索长度为 $2.88$。
阅读全文