c++ - 在具有 191 个节点且高度等于 9 的二叉树中找到一个键所需的最大比较次数是多少？

Question

我知道对于完全填充的二叉树，该树的高度等于floor(log2(N))，并且找到给定键的最大比较次数是h+1，或floor(log2(N)) + 1。

这个问题出现在我们期末考试的评论中，我不记得如何找到答案。给出的可能答案是7, 8, 9, 10。我相当肯定答案是9or 10，但我不知道，因为我不确定我是否应该根据数字512( 2^9) 或来计算答案191。

帮助表示赞赏！

Answer 1

由于指定了高度，这无疑是最简单的工作方式。

最大比较次数是从根到叶节点可以遍历的最大非叶节点数。取决于他如何定义高度（不幸的是，这并没有得到普遍认可），这将是高度或比高度小一。

Answer 2

这是一棵非常不平衡的二叉树，它有 6 个高度为 5 的节点。

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

假设你想找到 6。你必须需要 6 个比较。(6 = 5 + 1)

因此，在您的情况下，您必须进行 10 次比较（10 = 9 + 1）。节点数不影响答案。

Answer 3

假设二叉树是排序的，从根节点开始，需要将key与当前节点进行比较，判断是左遍历还是右遍历，匹配则返回当前节点，想要分支则返回失败选择不存在。

在最坏的情况下，您需要 9 次比较才能到达叶节点。您仍然需要与叶节点再进行一次比较，以查看值是否匹配。所以你需要10个比较。

如果它保证键是树的一部分，则只需要 9 次比较。否则为 10。