CSC 378: Data Structures and Algorithm Analysis

Height of a Complete Binary Tree

Height of a Complete Binary Tree

In the analysis of heaps, we've assumed that the height of the tree is index1.gif . Here, we'll prove it.

Theorem

The height of a complete, balanced tree of index2.gif nodes is index3.gif .

Intuition

tree
n
log (n+1)
1
1
3
2
7
3
etc.
...
...

Proof

With trees, induction is useful. We'll use induction on the height, index4.gif .

Basis

index5.gif

Inductive Hypothesis

Assume that the theorem is true for heights index6.gif .

Inductive Step

We must prove that the inductive hypothesis is true for height index7.gif .

Let index8.gif . Note that the theorem is true (by the inductive hypothesis) of the subtrees of the root, since they have height index9.gif .

index10.gif

Thus, the inductive hypothesis is true for height index11.gif and, hence (by induction), true for all heights. A complete binary tree of index12.gif nodes has height index13.gif .




Back to the lecture index

Copyright 1998 James Stewart