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

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the joint distribution of the insertion path length and the number of comparisons in search trees
scientific article

    Statements

    On the joint distribution of the insertion path length and the number of comparisons in search trees (English)
    0 references
    0 references
    0 references
    1988
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    number of comparisons
    0 references
    asymptotic properties
    0 references
    m-ary search tree
    0 references