A functional limit theorem for the profile of search trees (Q2476407): Difference between revisions

The level profile of a tree, as examined in this paper, is the sequence of numbers each counting the number of nodes with the same distance from the root. This parameter is a very informative shape parameter, useful for many purposes. The authors derive a functional limit law of the form \[ \frac{X_{n,\lfloor \alpha\log n\rfloor}} {E(X_{n,\lfloor \alpha\log n\rfloor})} \to X(\alpha), \] for the profile \(X_{n,k}\) of a class of trees called the generalized \(m\)-ary search trees. Many deep tools are developed for achieving this, which are of independent interest \textit{per se}.