Proof that the height of a balanced binary

 

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).

How would you prove this?

Let's assume at first that the tree is complete - it has 2^N leaf nodes. We try to prove that you need N recursive steps for a binary search.

With each recursion step you cut the number of candidate leaf nodes exactly by half (because our tree is complete). This means that after N halving operations there is exactly one candidate node left.

As each recursion step in our binary search algorithm corresponds to exactly one height level the height is exactly N.

Generalization to all balanced binary trees: If the tree has less nodes than 2^N we for sure don't need more halvings. We might need less or the same amount but never more.

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

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

  • the binary logarithm of 1 is 0
  • the binary logarithm of 2 is 1
  • the binary logarithm of 3 is 1
  • the binary logarithm of 4 is 2
  • the binary logarithm of 5, 6, 7 is 2
  • the binary logarithm of 8-15 is 3
  • the binary logarithm of 16-31 is 4 and so on.

    • 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

    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 log2 of any number from 8 to 15 is 3.

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

    I hope this helps.

    Assuming that we have a complete tree to work with, we can say that at depth k, there are 2k nodes. You can prove this using simple induction, based on the intuition that adding an extra level to the tree will increase the number of nodes in the entire tree by the number of nodes that were in the previous level times two.

    The height k of the tree is log(N), where N is the number of nodes. This can be stated as

    log2(N) = k,

    and it is equivalent to

    N = 2k

    To understand this, here's an example:

    16 = 24 => log2(16) = 4

    The height of the tree and the number of nodes are related exponentially. Taking the log of the number of nodes just allows you to work backwards to find the height.

    链接地址: http://www.djcxy.com/p/40036.html

    上一篇: 为什么斐波那契序列大O（2 ^ n）而不是O（logn）？

    下一篇: 证明一个平衡二进制的高度