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.


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

Consultation statistics

This page has been seen 852 times.
This article's PDF has been downloaded 439 times.