A functional limit theorem for the profile of search trees (Q2476407)

From MaRDI portal
Revision as of 07:17, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
A functional limit theorem for the profile of search trees
scientific article

    Statements

    A functional limit theorem for the profile of search trees (English)
    0 references
    0 references
    0 references
    0 references
    19 March 2008
    0 references
    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}.
    0 references
    binary search tree
    0 references
    level profile
    0 references
    functional limit theorem
    0 references
    concentration method
    0 references
    Zolotarev metric
    0 references
    Hilbert space
    0 references
    differential equation
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references