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 sequencesArticle

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]

    Share and export

    Consultation statistics

    This page has been seen 266 times.
    This article's PDF has been downloaded 216 times.