| Abstract: | A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height Hn of these trees by applying the theory of branching random walks. in particular, it is shown that Hn/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees. |
