On the joint distribution of the insertion path length and the number of comparisons in search trees (Q1121028): Difference between revisions

A special type of an m-ary search tree successively created by insertion of n distinct numbers (keys) is considered. The sequence of the keys is supposed to be random. To insert the \((n+1)th\) key into the search tree one has to exercise \(C_ n\) comparisons and the key is placed into a note on \(L_ n\) level. The paper presents a proof, based on the Laplace transform, of the assertion claiming that the random vector \(L_ n\), \(C_ n\) is asymptotically Gaussian with the mean and the covariance matrix dependent only on m and the first and second order moments of the local (i.e. within one node) search.