关键字(1,10,11,14,19,20,23,27,55,68,79,84),求折半查找的判定树和平均查找长度、27和哪些元素比较才能找到这个元素
时间: 2023-09-22 11:07:36 浏览: 75
采用折半查找和顺序查找来查找某个数
首先,折半查找的判定树如下:
```
50
/ \
11 79
/ \ / \
1 19 68 84
/ \ /
14 20 55
/ \
23 27
```
其中,每个节点表示在该节点处进行一次比较,左子树表示比较结果小于节点值,右子树表示比较结果大于等于节点值。
对于这个有序序列,平均查找长度为 log2(n),其中 n 为序列长度。这里 n = 11,所以平均查找长度为 log2(11) ≈ 3.46。
要找到元素 27,需要先与节点 50 进行比较,然后进入左子树,与节点 11 进行比较,再进入右子树,与节点 19 进行比较,再进入右子树,与节点 23 进行比较,最后进入右子树,与节点 27 相等,找到该元素。因此,27 需要与节点 50、11、19、23 进行比较。
阅读全文