Data Structures, Algorithms, & Applications in C++
Chapter 11, Exercise 61
The height increases only when two trees of the same height
are combined. We can prove that the number of elements
in a tree of height h is at least
2h-1. We shall do this by
induction on h.
For the induction base use h = 1.
A tree of height 1
has exactly 1 >= 2h-1
element/node.
For the induction hypothesis assume that trees of height
h for
h < m, where
m is an arbitrary integer >= 1,
have at least
2h-1 elements.
In the induction step we must show that all trees of height
m + 1 created using the height rule
have at least
2m elements.
Consider a height m + 1 tree created
using the height rule. Consider the union operation that first caused this
tree to have this height. During this union operation
two trees of height m were combined. From the
induction hypothesis it follows that each of these trees
had at least
2m - 1 elements at this time.
Therefore, the resulting tree has at least
2m elements. Since future operations
do not reduce the number of elements in a tree, the height
m + 1 tree has at least
2m elements now.