algorithm - 在具有 635 个元素的 BST 中查找元素的比较次数？

Question

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

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

Answer 1

这里有一种思考方式。每次在二叉搜索树中进行比较时，都会发生以下情况之一:

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

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

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

这很重要的原因是如果你有一个高度为 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次比较查找。

希望这对您有所帮助!