根据初始关键字序列(25,22,11,38,30,10)建立的二叉排序树的高度为多少,等概率情况下查找成功的平均查找长度是多少
时间: 2023-08-21 14:03:29 浏览: 64
根据给出的关键字序列,可以构建如下的二叉排序树:
```
25
/ \
22 38
/ \ /
11 30 10
```
该二叉排序树的高度为 3。
等概率情况下,查找成功的平均查找长度(ASL)是:
ASL = (1/6)*(1+2+2+3+3+3) = 2.17
其中,1/6 表示每个关键字被查找的概率,1、2、3 分别表示每个关键字的查找长度,将它们加起来再除以总的关键字个数,即可得到 ASL。
相关问题
根据初始关键字序列(25,22,11,38,30,10)建立的二叉排序树的高度为_________;等概率情况下查找成功的平均查找长度是 。
根据初始关键字序列(25,22,11,38,30,10)建立的二叉排序树的高度为3;等概率情况下查找成功的平均查找长度是2.5。
二叉排序树的高度是指从根节点到最深的叶子节点的距离(边数)。对于这个初始关键字序列,建立的二叉排序树如下所示:
```
25
/ \
22 38
/ \ /
11 30 10
```
可以看出,树的高度为3。
对于等概率情况下查找成功的平均查找长度,根据二叉排序树的性质,每个节点的左子树中的所有节点都小于该节点,右子树中的所有节点都大于该节点。因此,在等概率情况下,每个节点的查找概率都是相等的,即1/n,其中n为关键字的个数。因此,查找成功的平均查找长度为(h+1)/2,其中h为树的高度。
因此,在这个二叉排序树中,等概率情况下查找成功的平均查找长度为(3+1)/2=2.5。
将关键字序列(9,1,23,14,55,20,84,27)顺序依次插入初始为空的二叉排序树,并求出等概率情况下
二叉排序树的结构。
将关键字序列(9,1,23,14,55,20,84,27)依次插入初始为空的二叉排序树,得到的树结构如下:
```
9
/ \
1 23
\ / \
14 20 55
/ \
27 84
```
对于等概率情况下的二叉排序树,需要满足以下条件:
1. 根结点为序列中的中位数。
2. 左子树为关键字序列中小于中位数的子序列构成的等概率的二叉排序树。
3. 右子树为关键字序列中大于中位数的子序列构成的等概率的二叉排序树。
由于关键字序列中共有8个数,因此中位数为第4个数,即14。因此,等概率情况下的二叉排序树的根结点为14。将关键字序列分为两个子序列:{9, 1, 14, 23}和{55, 20, 84, 27}。左子树为{9, 1, 14, 23}构成的等概率的二叉排序树,右子树为{55, 20, 84, 27}构成的等概率的二叉排序树。对左子树和右子树分别递归地构造等概率的二叉排序树,得到最终的等概率的二叉排序树。
相关推荐
![](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)
![](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)