2

我是计算机科学大学的新生，所以请给我一个可以理解的理由。

我有一棵由高度平衡的二叉树，它有 635 个节点。在最坏的情况下会发生多少比较，为什么？

4

3 回答 3

5

这是思考这个问题的一种方法。每次在二叉搜索树中进行比较时，都会发生以下情况之一：

  • 你已经从树上走了下来。在这种情况下，你就完成了。
  • 您正在寻找的值与您当前正在探索的节点相匹配。在这种情况下，你就完成了。
  • 您正在寻找的值与您正在探索的节点不匹配。在这种情况下，您要么向左下降，要么向右下降。

这里的关键观察是，在每一步之后，您要么终止（耶！），要么在树中下降。在每一点上，您都会进行一次比较。由于您不能永远下降，因此您只能进行这么多比较 - 具体而言，如果树的高度为 h，则您可以进行的最大比较次数为 h + 1，如果您在每个级别进行一次比较，则会发生这种情况.

在您的问题中，您有一个 635 个节点的平衡二叉搜索树。在这种情况下，“平衡”的含义并不是 100% 清楚，因为有许多不同的方法可以确定一棵树是否平衡，并且它们都会导致不同的树高。我将假设您得到一个完整的二叉搜索树，其中除了最后一个之外的所有级别都已填充。

这很重要的原因是，如果你有一棵高度为 h 的完整二叉搜索树，它最多可以有 2 h + 1 - 1 个节点。如果我们尝试根据节点数来求解树的高度，我们会得到：

n = 2 h+1 - 1

n + 1 = 2 h+1

lg (n + 1) = h + 1

lg (n + 1) - 1 = h

因此，如果你有n个节点，你可以确定一个包含n个节点的完全二叉搜索树的最小高度。在你的情况下，n = 635，所以我们得到

lg (635 + 1) - 1 = h

lg (636) - 1 = h

9.312882955 - 1 = h

8.312882955 = h

因此，树的高度为 8.312882955。当然，树不能有分数高度，所以我们可以通过天花板来发现树的高度为 9。由于进行的最大比较次数为 h + 1，因此最多进行 10 次比较查找。

希望这可以帮助！

于 2013-06-13T18:59:34.427 回答
0

Without any loss of generality you can say the maximum no. of comparison will be the height of the BST ... you dont have to visit every node in the node because each comparison takes you closer to the node...

于 2013-06-13T19:32:18.780 回答
0

假设它是一个平衡的 BST（除最后一个之外的所有节点都有 2 个子节点）。

例如，
级别 0 --> 高度 1 --> 节点数 = 1
级别 1 --> 高度 2 --> 节点数 = 2
级别 2 --> 高度 3 --> 节点数 = 3
级别 3 --> 高度 4 --> 节点数 = 8
......
......
第 n 级 --> 高度 n+1 --> 节点数 = 2^n 或 2^(h- 1)

使用上述逻辑，您可以得出最佳、最坏或平均情况的搜索时间。

于 2018-04-06T04:26:49.857 回答