Steiner, Wolfgang The distribution of \(m\)-ary search trees generated by van der Corput sequences. (English) Zbl 1066.68028 Discrete Math. Theor. Comput. Sci. 6, No. 2, 409-423 (2004). 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 Keywords:\(m\)-ary search trees; van der Corput sequence; tree height; central limit theorem; generating function PDFBibTeX XMLCite \textit{W. Steiner}, Discrete Math. Theor. Comput. Sci. 6, No. 2, 409--423 (2004; Zbl 1066.68028) Full Text: EuDML EMIS