average number of leaves = L = n/b
Longest paths occur if the number of children at every stage = m/2
= l, say
Average number of nodes that are parents of leaves =
Average number of nodes that are second level parents
= l
=
If h is the level of the leaves, we have
1 | |||
or | h log_{l}L | ||
i.e., | h log_{m/2}n/b |
If n = 106 records (1 million records), b = 10, and m = 100, we
have
h 3.9