×

The distribution of \(m\)-ary search trees generated by van der Corput sequences. (English) Zbl 1066.68028

Summary: 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.

MSC:

68P05 Data structures
05C85 Graph algorithms (graph-theoretic aspects)
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: EuDML EMIS