给定序列{3,5,7,9,11,13,15,17}:按表中元素的顺序依次插入一棵初始为空的二叉搜索树。画出插入完成后的二叉搜索树,并求其在等概率情况下搜索成功的平均搜索长度;
时间: 2023-12-06 16:03:22 浏览: 62
二叉搜索树的结构是左子树的所有节点值都小于根节点,右子树的所有节点值都大于根节点。按照给定的序列依次插入节点,我们可以得到以下的二叉搜索树:
```
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$。
相关问题
给定序列{3,5,7,9,11,13,15,17}: (1)按表中元素的顺序依次插入一棵初始为空的二叉搜索树。画出插入完成后的二叉搜索树,并求其在等概率情况下搜索成功的平均搜索长度; (2)按表中元素顺序构造一棵平衡二叉树,求其等概率情况下搜索成功的平均搜索长度,与(1)比较,可得出什么结论?
好的,我会根据您的问题进行回答。
(1) 初始为空的二叉搜索树的插入过程如下所示:
```
3
\
5
\
7
\
9
\
11
\
13
\
15
\
17
```
二叉搜索树的搜索成功的平均搜索长度是节点深度的期望值,对于等概率情况下的二叉搜索树,节点深度的期望值为:
```
E(h) = (1/n) * (1 + 2 + ... + n) = (n+1)/2
```
所以,对于这棵二叉搜索树,搜索成功的平均搜索长度为 (8+1)/2 = 4.5。
(2) 按照表中元素顺序构造的平衡二叉树如下所示:
```
9
/ \
5 13
/ \ / \
3 7 11 15
\ \
12 17
```
平衡二叉树的搜索成功的平均搜索长度同样是节点深度的期望值,对于这棵平衡二叉树,节点深度的期望值为:
```
E(h) = log2(n+1)
```
所以,对于这棵平衡二叉树,搜索成功的平均搜索长度为 log2(9) ≈ 3.17。
通过比较可以发现,平衡二叉树的搜索成功的平均搜索长度比普通的二叉搜索树更小。这是因为平衡二叉树的高度比较小,节点深度更加均衡,搜索时需要遍历的节点数量更少。
给定关键字序列为{16,5,17,29,11,3,15,20},按表中元素的顺序依次插入,建立相应的二叉排序树,给出其中序序列。
按照给定的关键字序列,依次插入二叉排序树中,建立的二叉排序树如下所示:
```
16
/ \
5 17
/ / \
3 15 29
/
20
```
中序遍历二叉排序树,得到的中序序列为:`3 5 15 16 17 20 29`。