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.


    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

    Consultation statistics

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