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: 68P05, 05C85, 60C05, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [fr] arbre de recherche m-aire, suite de van der Corput, théorème central limite, série génératrice

    Share and export

    Consultation statistics

    This page has been seen 447 times.
    This article's PDF has been downloaded 359 times.