performance - 证明平衡二叉搜索树的高度为 log(n)

Question

二进制搜索算法需要 log(n) 时间，因为树的高度（具有 n 个节点）将是 log(n)。

你将如何证明这一点？

score 30 · Accepted Answer

现在在这里我不给出数学证明。尝试使用 log to base 2 来理解问题。 Log ₂是计算机科学中 log 的正常含义。

首先，了解它是二进制对数（log ₂ n）（以 2 为底的对数）。例如，

对于每个高度，完全平衡树中的节点数为

    高度节点日志计算
      0 1 对数₂ 1 = 0
      1 3 对数₂ 3 = 1
      2 7 对数₂ 7 = 2
      3 15 对数₂ 15 = 3

考虑一个具有 8 到 15 个节点（任意数量，比如说 10）的平衡树。它总是高度 3，因为从 8 到 15 的任何数字的log _{2都是 3。}

在平衡二叉树中，每次迭代要解决的问题的大小减半。因此，大约需要 log ₂ n 次迭代才能获得大小为 1 的问题。

我希望这有帮助。

score 11 · Accepted Answer

让我们首先假设树是完整的——它有 2^N 个叶子节点。我们试图证明你需要 N 个递归步骤来进行二分搜索。

在每个递归步骤中，您将候选叶节点的数量精确地减少了一半（因为我们的树是完整的）。这意味着在 N 次减半操作之后，只剩下一个候选节点。

由于我们的二进制搜索算法中的每个递归步骤都对应于一个高度级别，因此高度正好是 N。

推广到所有平衡二叉树：如果树的节点少于 2^N，我们肯定不需要更多的减半。我们可能需要更少或相同的数量，但永远不会更多。

score 8 · Accepted Answer

假设我们有一个完整的树可以使用，我们可以说在深度 k 处有^2k个节点。您可以使用简单的归纳来证明这一点，基于这样的直觉，即向树添加额外的级别将使整个树中的节点数增加前一层中的节点数乘以 2。

树的高度 k 是 log(N)，其中 N 是节点数。这可以表述为

日志₂ (N) = k,

它相当于

N = 2^千

为了理解这一点，这里有一个例子：

16 = 2 ⁴ => 对数₂ (16) = 4

树的高度和节点的数量呈指数关系。记录节点数量的日志只允许您向后工作以找到高度。

score 0 · Accepted Answer

只需查看 Knuth, Volume 3 - Searching and Sorting Algorithms 中的严格证明……他做的比我能想到的任何人都严格得多。

你可以在任何好的计算机科学图书馆和许多（非常）老极客的书架上找到它。

4 回答 4