证明平衡二分查找树的高度为log(n) [英] Proof that the height of a balanced binary-search tree is log(n)

问题描述

由于树的高度(具有n个节点)将为log(n)，因此二分查找算法需要log(n)的时间.

The binary-search algorithm takes log(n) time, because of the fact that the height of the tree (with n nodes) would be log(n).

您将如何证明这一点?

推荐答案

现在我不在此提供数学证明.尝试使用基础日志2来了解问题.Log ₂ 是计算机科学中日志的正常含义.

Now here I am not giving mathematical proof. Try to understand the problem using log to the base 2. Log₂ is the normal meaning of log in computer science.

首先，了解它是二进制对数(log ₂ n)(以2为底的对数). 例如，

First, understand it is binary logarithm (log₂n) (logarithm to the base 2). For example,

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

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

For each height the number of nodes in a fully balanced tree are

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

请考虑一个具有8到15个节点(任意数量，例如10个)的平衡树.它总是要成为高度3，因为log ₂ 的8到15之间的任何数字都是3.

Consider a balanced tree with between 8 and 15 nodes (any number, let's say 10). It is always going to be height 3 because log₂ of any number from 8 to 15 is 3.

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

In a balanced binary tree the size of the problem to be solved is halved with every iteration. Thus roughly log₂n iterations are needed to obtain a problem of size 1.

我希望这会有所帮助.

这篇关于证明平衡二分查找树的高度为log(n)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！