二分查找怎么画二叉树 折半查找时若数据元素个数为偶数怎么画判定树？

折半查找时若数据元素个数为偶数怎么画判定树？

构建半搜索的决策树就足够了

第一层有一个节点

第二层有两个节点

第三层有四个节点

第四层有八个节点，共124个节点[8=15

剩下的30-15=15都在第五层，也就是说比较的次数是5，所以答案是正确的

二进制搜索一个有n个元素的有序数组。要分析的比较数可以通过绘制二叉决策树来分析。二叉决策树的高度为[log2（n）]1级，这是二叉搜索的最大比较次数。例如，如果n=1000，则最大比较次数为[log2（1000）]1=9，1=10。如果要计算平均比较次数，则需要分析二叉决策树中的每个节点。第一级比较一次，第二级比较两次，第三级比较三次，以此类推，将每个节点的比较次数相加，然后节点数（元素数）就是平均比较次数。这里，假设搜索是在等概率条件下进行的。例如：有一个由九个元素组成的有序数组，每个元素用1，2，3。。。8, 9. 然后二叉决策树如下：如图所示，如果要查找的元素位于第五个位置，则只需进行一次比较即可找到它。如果找到第九个元素，就需要四个比较。该算法分别比较第五、第七、第八和第九个元素。因此，平均比较次数如下：你能理解这个分析吗？希望能对你有所帮助。

C语言，二分法查找次数公式怎么推导？

1. 例如，长度为10的二叉搜索决策树的具体生成过程遵循左子节点<根节点<右子节点

2。对于长度为10的有序表中的二进制搜索，无论搜索哪个记录，都必须与中间记录进行比较，中间记录为（1，10）/2=5（注意四舍五入，即向下舍入），即判定数的根为5。

3. 考虑决策树的左子树，即将搜索区域调整到左半部分，搜索间隔为[1,4]，则中值为（1,4）/2=2（注：舍入），所以子根节点为2

4。考虑决策树的右子树，即将搜索区域调整到右半部分，搜索间隔为[6,10]，则中值为（6,10）/2=85。重复上述步骤，依次确定左右子项

二分查找怎么画二叉树 12个元素的折半查找判定树 折半查找判定树

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。