假设一个有序序列 { 12, 25, 46, 62, 78, 80 }, 画出进行二分查找的判定树,并计算查找成功的ASL和查找不成功的ASL。
时间: 2024-01-18 09:03:44 浏览: 73
下面是二分查找的判定树:
```
62
/ \
25 78
/ \ / \
12 46 80 nil
/ \
nil nil
```
其中,nil表示空节点。
对于查找成功的情况,有:
- 查找12:路径长度为1,ASL为1
- 查找25:路径长度为1,ASL为1
- 查找46:路径长度为2,ASL为2/3
- 查找62:路径长度为0,ASL为0
- 查找78:路径长度为1,ASL为1
- 查找80:路径长度为2,ASL为2/3
所以查找成功的ASL为 (1+1+2/3+0+1+2/3) / 6 = 7/9。
对于查找不成功的情况,假设要查找的数为50,那么它会落在节点46和62之间,路径长度为3,ASL为3/6 = 1/2。
因此,查找成功的ASL为7/9,查找不成功的ASL为1/2。
相关问题
有序关键字序列{13, 18, 25, 39, 42, 55, 62, 87},画出其二分查找判定树,并计算查找成功的平均查找长度(ASL)。
好的,我知道了。这是一个关于二分查找的问题。首先,我们来画出这个有序关键字序列的二分查找判定树。根据二分查找的原理,我们可以将序列分成左右两个子序列,然后在其中一个子序列中继续查找,直到找到目标元素或者序列为空为止。
下面是判定树的示意图:
```
42
/ \
25 62
/ \ / \
18 39 55 87
/ \
13 (NIL)
```
其中,NIL表示空节点。根据判定树,我们可以得到以下查找成功的平均查找长度(ASL):
```
ASL = (1/8)*[1 + 2 + 2 + 3 + 3 + 3 + 3 + 4] = 2.625
```
所以,对于这个有序关键字序列,二分查找的平均查找长度为2.625。
二分查找判定树怎么画
二分查找判定树的画法如下:
1. 首先,根据给定的序列长度n,确定二分查找判定树的最大满二叉树结构。最大满二叉树是指除了最底层的叶子节点外,每一层都是满的二叉树。
2. 然后,计算剩余的结点个数。如果序列长度n为奇数,左右子树的结点个数相等;如果序列长度n为偶数,左子树的结点个数等于右子树的结点个数减1。
3. 接下来,按照上述规律将剩余的结点依次填入最底层,形成二分查找判定树的树形。
4. 最后,按照中序遍历的顺序,将给定的序列依次填入各个结点。
通过以上步骤,就可以画出二分查找判定树。
相关推荐
![](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)