对于给定结点的关键字集合K={4,8,2,9,1,3,6,7,5}, (1)试构造一棵二叉排序树; (2)求等概率情况下的平均查找长度ASL
时间: 2023-06-12 12:02:16 浏览: 172
好的,我明白了。下面是回答:
1. 构造二叉排序树:
我们可以选择第一个结点4作为二叉排序树的根节点,然后依次将后面的结点插入到树中。以下是具体步骤:
- 将8插入到根节点的右子树中;
- 将2插入到根节点的左子树中;
- 将9插入到8的右子树中;
- 将1插入到2的左子树中;
- 将3插入到2的右子树中;
- 将6插入到8的左子树中;
- 将7插入到6的右子树中;
- 将5插入到7的左子树中。
最终得到的二叉排序树如下图所示:
4
/ \
/ \
2 8
/ \ / \
1 3 6 9
\
7
/
5
2. 求等概率情况下的平均查找长度ASL:
平均查找长度ASL是指,在进行查找时平均需要遍历的结点数。在等概率情况下,每个结点被查找的概率都是相等的,即P(k) = 1/n,其中n为树中结点的个数。因此,可以根据以下公式来计算ASL:
ASL = ∑ i=1^n (深度i × P(ki))
其中,ki表示第i个结点,深度i表示ki的深度,即从根节点到ki的路径长度。对于给定的二叉排序树,ASL的计算如下:
- P(4) = 1/9, 深度1,ASL(4) = 1/9;
- P(2) = 1/9, 深度2,ASL(2) = 2/9;
- P(1) = 1/9, 深度3,ASL(1) = 3/9;
- P(3) = 1/9, 深度3,ASL(3) = 3/9;
- P(8) = 1/9, 深度2,ASL(8) = 2/9;
- P(6) = 1/9, 深度3,ASL(6) = 3/9;
- P(9) = 1/9, 深度3,ASL(9) = 3/9;
- P(7) = 1/9, 深度4,ASL(7) = 4/9;
- P(5) = 1/9, 深度5,ASL(5) = 5/9;
因此,等概率情况下的平均查找长度ASL为:
ASL = (1/9) × 1 + (2/9) × 2 + (3/9) × (1+1+1) + (4/9) × 1 + (5/9) × 1.667
ASL = 1.889
最终结果保留三位小数,即ASL = 1.889。