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

Question

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

你会怎么证明这一点？

Answer 1

现在我在这里,我没有给出数学证明.尝试使用日志到基础2来理解问题.日志₂是登录计算机科学的正常含义.

首先,理解它是二进制对数(log ₂ n)(对数2的对数).例如,

• 二进制对数1为0
• 二进制对数为2
• 3的二进制对数为1
• 4的二进制对数是2
• 5,6,7的二进制对数为2
• 8-15的二进制对数是3
• 16-31的二进制对数是4,依此类推.

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

    Height  Nodes  Log calculation
      0        1      log21 = 0
      1        3      log23 = 1
      2        7      log27 = 2
      3       15      log215 = 3

考虑一个8到15个节点之间的平衡树(任意数字,比方说10).它始终是高度3,因为从8到15的任何数字的log ₂是3.

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

我希望这有帮助.

Answer 2

我们首先假设树已完成 - 它有2 ^ N个叶节点.我们试图证明你需要N个递归步骤进行二进制搜索.

在每个递归步骤中,您将候选叶节点的数量精确减少一半(因为我们的树已完成).这意味着在N个减半操作之后,只剩下一个候选节点.

由于我们的二分搜索算法中的每个递归步骤恰好对应于一个高度级别,因此高度恰好为N.

对所有平衡二叉树的推广:如果树的节点数少于2 ^ N,我们肯定不需要更多的减半.我们可能需要更少或相同数量但不会更多.

Answer 3

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

树的高度k为log（N），其中N为节点数。可以说是

log ₂（N）= k，

相当于

N = 2 ^k

要了解这一点，下面是一个示例：

16 = 2 ⁴ =>对数₂（16）= 4

树的高度和节点数呈指数关系。取节点数的对数仅允许您向后工作以查找高度。