Digital Search Trees Again Revisited: The Internal Path Length Perspective

DOI10.1137/S0097539790189368zbMath0819.68067MaRDI QIDQ4302286

Wojciech Szpankowski, Peter Kirschenhofer, Prodinger, Helmut

Publication date: 14 August 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

Bernoulli modelsymmetric digital search tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80)

Related Items

Distances in random digital search trees, Analytical depoissonization and its applications, Approximate counting with \(m\) counters: A detailed analysis, A general limit theorem for recursive algorithms and combinatorial structures, Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees, The total path length of split trees, On the variance of the internal path length of generalized digital trees -- the Mellin convolution approach, The Wiener Index of Random Digital Trees