Wolfgang Steiner - The distribution of m-ary search trees generated by van der Corput sequences

dmtcs:318 - Discrete Mathematics & Theoretical Computer Science, January 1, 2004, Vol. 6 no. 2 - https://doi.org/10.46298/dmtcs.318
The distribution of m-ary search trees generated by van der Corput sequences

Authors: Wolfgang Steiner

    We study the structure of $m$-ary search trees generated by the van der Corput sequences. The height of the tree is calculated and a generating function approach shows that the distribution of the depths of the nodes is asymptotically normal. Additionally a local limit theorem is derived.

    https://doi.org/10.46298/dmtcs.318
    Source: HAL:hal-00023232v1
    Volume: Vol. 6 no. 2
    Published on: January 1, 2004
    Imported on: March 26, 2015
    Keywords: arbre de recherche m-aire,suite de van der Corput,théorème central limite,série génératrice,68P05, 05C85, 60C05,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsRelatedTo DOI 10.1016/0166-218x(88)90080-7
    • 10.1016/0166-218x(88)90080-7
    On the joint distribution of the insertion path length and the number of comparisons in search trees

    Share and export

    Consultation statistics

    This page has been seen 185 times.
    This article's PDF has been downloaded 171 times.