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

The shape of a sequence of trees grown by the progressive ordering of the elements of an infinite random permutation is studied. Lₙ, 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 + ⋯ + 1/m), m - 1 being the capacity of a node.Furthermore, Cₙ, the number of comparisons needed to insert the $(n + 1)$st element grows, in probability, as Lₙ (m - 1)(m + 2)/2m. We also show that, almost surely, Lₙ /ln n ∈ [α ₁ - ε ,α ₂ + ε ], Cₙ /ln n ∈ [β ₁ - ε ,β ₂ + ε ] for large enough n(ε > 0). Here α ᵢ ,β ᵢ are roots of two certain equations.