证明一个平衡二进制的高度
二进制搜索算法需要log（n）时间，因为树（有n个节点）的高度为log（n）。
你会如何证明这一点？
我们首先假设树是完整的 - 它有2 ^ N个叶节点。 我们试图证明您需要N个二进制搜索的递归步骤。
通过每次递归步骤，您都可以精确地将候选叶节点的数量减半（因为我们的树已经完成）。 这意味着在N次减半操作之后，只剩下一个候选节点。
由于我们二进制搜索算法中的每个递归步骤恰好对应一个高度级别，所以高度恰好为N.
对所有平衡二叉树的推广：如果树节点少于2 ^ N，我们当然不需要更多的二分之一。 我们可能需要更少或相同的金额，但从不需要更多。
现在我在这里没有给出数学证明。 尝试使用登录到基地来了解问题2. Log2是登录计算机科学的正常含义。
首先，了解它是二进制对数（log2n）（以2为底的对数）。 例如，
对于每个高度，完全平衡树中的节点数量为
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的任何数字的log2是3。
在平衡二叉树中，待解决问题的大小在每次迭代中减半。 因此，需要大致log2n迭代来获得大小为1的问题。
我希望这有帮助。
假设我们有一棵完整的树来工作，我们可以说在深度k处有2k个节点。 您可以使用简单的归纳法来证明这一点，基于这样的直觉，即向树添加额外的级别将会增加整个树中节点的数量，使其达到前一级中节点数量的两倍。
树的高度k是log（N），其中N是节点的数量。 这可以表述为
log2（N）= k，
这相当于
N = 2k
为了理解这个，下面是一个例子：
16 = 24 => log2（16）= 4
树的高度和节点数目呈指数关系。 取得节点数量的日志只是让你向后查找高度。
链接地址: http://www.djcxy.com/p/40035.html