对于给定结点的关键字集合K={5,7,3,1,9,6,4,8,2,10}不用代码求等概率情况下的平均查找长度
时间: 2024-03-18 15:42:52 浏览: 26
在等概率情况下,二叉排序树的平均查找长度ASL可以用公式计算:
ASL = (Hn - 1) / n + 1/2
其中,Hn为n个节点的完全二叉树的深度,n为关键字的数量。
对于给定的关键字集合K={5,7,3,1,9,6,4,8,2,10},它包含10个关键字,因此n=10。
完全二叉树的深度可以通过以下公式计算:
Hn = log2(n+1)
因此,H10 = log2(11) ≈ 3.4594。
将H10和n代入ASL的公式中,可以得到:
ASL = (H10 - 1) / n + 1/2 ≈ (3.4594 - 1) / 10 + 1/2 ≈ 0.34594 + 0.5 ≈ 0.84594
因此,等概率情况下的平均查找长度ASL约为0.84594。
相关问题
对于给定结点的关键字集合K={5,7,3,1,9,6,4,8,2,10}不用代码求等概率情况下的平均查找长度ASL
在等概率情况下,二叉排序树的平均查找长度ASL可以用公式计算:
ASL = (Hn - 1) / n + 1/2
其中,Hn为n个节点的完全二叉树的深度,n为关键字的数量。
对于给定的关键字集合K={5,7,3,1,9,6,4,8,2,10},它包含10个关键字,因此n=10。
完全二叉树的深度可以通过以下公式计算:
Hn = log2(n+1)
因此,H10 = log2(11) ≈ 3.4594。
将H10和n代入ASL的公式中,可以得到:
ASL = (H10 - 1) / n + 1/2 ≈ (3.4594 - 1) / 10 + 1/2 ≈ 0.34594 + 0.5 ≈ 0.84594
因此,等概率情况下的平均查找长度ASL约为0.84594。
对于给定结点的关键字集合K={5,7,3,1,9,6,4,8,2,10}, 构造一棵二叉排序树
首先,将第一个关键字5当作根节点。接下来,依次将每个关键字插入到树中。
插入7时,由于7>5,因此插入到根节点的右子树中。现在,根节点的右子树为7。
插入3时,由于3<5,因此插入到根节点的左子树中。现在,根节点的左子树为3,右子树为7。
插入1时,由于1<5,因此插入到根节点的左子树中。现在,根节点的左子树为3,左子树的左子树为1,右子树为7。
插入9时,由于9>5,因此插入到根节点的右子树中。现在,根节点的左子树为3,左子树的左子树为1,右子树为7,右子树的右子树为9。
插入6时,由于6<7,因此插入到7的左子树中。现在,根节点的左子树为3,左子树的左子树为1,右子树为7,右子树的左子树为6,右子树的右子树为9。
插入4时,由于4<5,因此插入到5的左子树中。现在,根节点的左子树为3,左子树的左子树为1,左子树的右子树为4,右子树为7,右子树的左子树为6,右子树的右子树为9。
插入8时,由于8>7,因此插入到7的右子树中。现在,根节点的左子树为3,左子树的左子树为1,左子树的右子树为4,右子树为7,右子树的左子树为6,右子树的右子树为9,右子树的右子树的左子树为8。
插入2时,由于2<3,因此插入到3的左子树中。现在,根节点的左子树为3,左子树的左子树为1,左子树的左子树的右子树为2,左子树的右子树为4,右子树为7,右子树的左子树为6,右子树的右子树为9,右子树的右子树的左子树为8。
插入10时,由于10>9,因此插入到9的右子树中。现在,根节点的左子树为3,左子树的左子树为1,左子树的左子树的右子树为2,左子树的右子树为4,右子树为7,右子树的左子树为6,右子树的右子树为9,右子树的右子树的左子树为8,右子树的右子树的右子树为10。
最终,得到的二叉排序树如下所示:
```
5
/ \
3 7
/ \ / \
1 4 6 9
/ / \
2 8 10
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)