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]