Abstract#R##N##R##N#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.
['Luc Devroye']
On the Height of Random m-ary Search Trees