Discrete Mathematics & Theoretical Computer Science, Vol 6, No 2 (2004)

Font Size:  Small  Medium  Large

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

Wolfgang Steiner

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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page