关键码集合{25,18,34,9,14,27,42,51,38},假定检索各关键码的概率相等,请画出其最佳二叉排序树。
时间: 2024-03-03 10:47:18 浏览: 30
以下是该关键码集合的最佳二叉排序树的图形:
```
27
/ \
18 38
/ \ / \
9 14 34 42
\ \
25 51
```
在这个二叉排序树中,每个节点代表一个关键码,它们按照从小到大的顺序排列。每个节点的左子树中的关键码都小于该节点,每个节点的右子树中的关键码都大于该节点。最佳二叉排序树的定义是,它的期望搜索代价最小,即所有关键码被搜索的平均次数最少。
在这个例子中,所有关键码的检索概率相等,因此我们可以使用 Huffmancoding 算法来构造最佳二叉排序树。该算法的基本思想是,将所有关键码按照概率从小到大排序,然后依次选择两个概率最小的关键码,将它们合并为一个节点,并将它们的概率相加作为该节点的概率。重复这个过程,直到所有关键码都被合并成一个根节点为止。在这个过程中,每次合并的节点都应该是该子树中概率最小的两个节点。
在这个例子中,按照概率从小到大排序的顺序是:{9,14,18,25,27,34,38,42,51}。首先,我们将最小的两个概率为9和14的关键码合并为一个节点,概率为23;然后将概率为18和25的关键码合并为一个节点,概率为43;将概率为23和27的关键码合并为一个节点,概率为50;将概率为34和38的关键码合并为一个节点,概率为72;将概率为42和51的关键码合并为一个节点,概率为93;最后将概率为50和72的节点合并为一个根节点,概率为122。这样就得到了最佳二叉排序树。
相关问题
关键码集合{25,18,34,9,14,27,42,51,38},假定检索各关键码的概率相等,请画出其最佳二叉排序树。并求出E(n)
以下是关键码集合的最佳二叉排序树:
```
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。
假定一个计算机系统有4096个b的磁盘块,存储每一条记录中4 b是关键码,64 b是数据域
这个计算机系统具有4096个磁盘块,每个磁盘块的大小为4字节。假设每条记录有一个4字节的关键码和一个64字节的数据域。
假设我们想要存储1000条记录,每条记录包括关键码和数据域。首先,我们需要计算每条记录所需的空间。每个记录包括4字节的关键码和64字节的数据域,因此每条记录总共需要占用68字节的空间。
然后,我们可以计算出存储1000条记录所需的总空间。每条记录需要占用68字节,所以1000条记录需要占用68 * 1000 = 68000字节的空间。
接下来,我们将计算所需的磁盘块数量。由于每个磁盘块的大小为4字节,我们可以通过将总空间除以磁盘块的大小来得出所需的磁盘块数量。总空间为68000字节,磁盘块大小为4字节,所以所需的磁盘块数量为68000 / 4 = 17000块。
因此,如果这个计算机系统有4096个磁盘块,那么存储1000条记录所需的空间将超过4096个磁盘块的总容量。为了存储这些记录,我们需要对数据进行压缩或者使用其他存储方法来节省空间。