On the Most Probable Shape of a Search Tree Grown from a Random Permutation

Abstract

The shape of a sequence of trees grown by the progressive ordering of the elements of an infinite random permutation is studied. $L_n $, the length of the path to the node containing the $(n + 1)$st element, is shown to grow, in probability, as $\ln n/(1/2 + \cdots + 1/m), m - 1$ being the capacity of a node.Furthermore, $C_n $, the number of comparisons needed to insert the $(n + 1)$st element grows, in probability, as $L_n (m - 1)(m + 2)/2m$. We also show that, almost surely, $L_n /\ln n \in [\alpha _1 - \varepsilon ,\alpha _2 + \varepsilon ]$, $C_n /\ln n \in [\beta _1 - \varepsilon ,\beta _2 + \varepsilon ]$ for large enough $n(\varepsilon > 0)$. Here $\alpha _i ,\beta _i $ are roots of two certain equations.