关键码集合{25,18,34,9,14,27,42,51,38},假定检索各关键码的概率相等,请画出其最佳二叉排序树。并求出E(n)
时间: 2023-12-13 09:04:02 浏览: 12
以下是关键码集合的最佳二叉排序树:
```
27
/ \
18 38
/ \ / \
14 25 34 51
/ \
9 42
```
其中,根节点为27,左子树为{9, 14, 18, 25},右子树为{34, 38, 42, 51}。
关键码集合的E(n)为:
E(n) = 1/9 * (2E(0) + e(1) + 2E(2) + E(3) + 2E(4) + E(5) + 2E(6) + E(7) + 2E(8))
其中,E(0)~E(8)分别表示集合中0~8个关键码的最小搜索代价。根据定义,E(0)为0,E(1)为1。
计算过程如下:
E(2) = 1/2 * (2 + 2) + 25 = 29
E(3) = 1/3 * (2 + 2 + 29) + 18 = 24.67
E(4) = 1/4 * (2 + 2 + 24 + 29) + 14 = 21.25
E(5) = 1/5 * (2 + 2 + 21.25 + 24 + 29) + 9 = 18.9
E(6) = 1/6 * (2 + 2 + 18.9 + 21.25 + 24 + 29) + 27 = 25.7
E(7) = 1/7 * (2 + 2 + 25.7 + 18.9 + 21.25 + 24 + 29) + 34 = 28.24
E(8) = 1/8 * (2 + 2 + 28.24 + 25.7 + 18.9 + 21.25 + 24 + 29) + 38 = 31.28
因此,E(n) = 1/9 * (2*0 + 1 + 2*29 + 24.67 + 2*21.25 + 18.9 + 2*25.7 + 28.24 + 2*31.28) = 25.06。