关键字序列{13,25,17,10,12,8,22,4,45,30}构造二叉排序树,查找概率相同的情况下,查找成功的平均查找长度为( ) 。
时间: 2023-08-06 18:05:45 浏览: 75
构造的二叉排序树如下所示:
```
13
/ \
10 25
/ / \
8 17 45
\
22
\
30
\
4
```
其中,每个节点的左子树的所有关键字都小于该节点的关键字,右子树的所有关键字都大于该节点的关键字。
查找关键字时,从根节点开始比较,若待查找关键字小于当前节点的关键字,则在左子树中继续查找;若大于,则在右子树中继续查找;若相等,则查找成功。
由于查找概率相同,每个关键字被查找到的概率为1/10。因此,查找成功的平均查找长度为:
(1/10)*1 + (1/10)*2 + (1/10)*2 + (1/10)*3 + (1/10)*3 + (1/10)*4 + (1/10)*4 + (1/10)*5 + (1/10)*6 + (1/10)*7 = 3.5
因此,答案为3.5。
相关问题
对关键字序列{13,25,17,10,12,8,22,4,30}构造二叉排序树,查找概率相同的情况 下,查找成功的平均查找长度为( )。
根据输入的关键字序列,可以构造出如下的二叉排序树:
13
/ \
10 25
/ \ / \
8 12 17 30
/
4
在查找概率相同的情况下,查找成功的平均查找长度为3.7。
1、按关键字序列(45,24,53,36,12,28,90,68)的顺序构造二叉排序树,等概率查找失败的平均查找长度为_________________。
按照给定的关键字序列,构造出的二叉排序树如下:
```
45
/ \
24 53
/ \ \
12 36 90
/ \
28 68
```
等概率查找失败的平均查找长度就是每个关键字查找失败的概率乘以查找该关键字时需要遍历的平均结点数,所有关键字的平均查找长度之和。
因为每个关键字在二叉排序树中的位置是等概率的,所以每个关键字查找失败的概率都是1/8。
对于每个关键字,查找该关键字时需要遍历的平均结点数是其深度加1。因此,可以计算出每个关键字的深度如下:
```
45 (深度1)
/ \
24(2) 53(2)
/ \ \
12(3) 36(3) 90(3)
/ \
28(4) 68(4)
```
因此,每个关键字查找失败时需要遍历的平均结点数如下:
```
12: (2 + 1) * 1/8 = 3/8
28: (3 + 1) * 1/8 = 1/2
36: (3 + 1) * 1/8 = 1/2
68: (4 + 1) * 1/8 = 5/8
90: (3 + 1) * 1/8 = 1/2
24: (2 + 1) * 1/8 = 3/8
53: (2 + 1) * 1/8 = 3/8
45: (1 + 1) * 1/8 = 1/4
```
因此,所有关键字的平均查找长度之和为:
```
(3/8 + 1/2 + 1/2 + 5/8 + 1/2 + 3/8 + 3/8 + 1/4) = 19/8
```
因此,等概率查找失败的平均查找长度为19/8。