The distribution of m-ary search trees generated by van der Corput sequences

Abstract

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.

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]