Proof that the height of a balanced binary search tree is log (n)

Question

The binary search algorithm takes log (n) time because the height of the tree (with n nodes) is log (n).

How would you prove it?

Answer 1

Assume first that the tree is complete - it has 2 ^ N leaf nodes. We are trying to prove that you need N recursive steps for binary search.

With each recursion step, you reduce the number of potential leaf nodes by exactly half (because our tree is complete). This means that after N smaller operations, exactly one candidate node remains on the left.

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

A generalization for all balanced binary trees: if a tree has fewer nodes than 2 ^ N, we certainly do not need more than half. We may need less or the same amount, but not more.

Answer 2

Now I do not give mathematical proofs. Try to understand the problem using a log for base 2. Log ₂ is the normal value of a log in computer science.

First you need to understand the binary logarithm (log ₂ n) (the logarithm to 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, etc.

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

  Height Nodes Log calculation
       0 1 log 2 1 = 0
       1 3 log 2 3 = 1
       2 7 log 2 7 = 2
       3 15 log 2 15 = 3

Consider a balanced tree between 8 and 15 nodes (any number, say, 10). It will always be height 3 because log _{2 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 each iteration. Thus, coarse log ₂ n iterations are needed to get a size 1 problem.

Hope this helps.

Answer 3

Assuming we have a complete tree for work, we can say that at a depth k there are 2 ^k nodes. You can prove this using simple intuition-based induction 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 at the previous level every two times.

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

log ₂ (N) = k,

and it is equivalent

N = 2 ^k

To understand this, here is an example:

16 = 2 ⁴ => log ₂ (16) = 4

Tree height and number of nodes are connected exponentially. Taking a log of the number of nodes simply allows you to work backwards to find the height.

Answer 4

Just look at the rigorous proof in Book of Whip, Volume 3 - Finding and Sorting Algorithms ... He does it much more strictly than anyone else I can think of.

http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming

You can find it in any good Computer Science library and on the bookshelves of many (very) old geeks.