Digital Search Trees Again Revisited: The Internal Path Length Perspective

DOI10.1137/S0097539790189368MaRDI QIDQ4302286zbMATH OpenFDO

Authors Peter Kirschenhofer, Helmut Prodinger, Wojciech Szpankowski

Publication date 14 August 1994

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

Full work available at URL https://doi.org/10.1137/S0097539790189368

zbMATH Keywords

Bernoulli modelsymmetric digital search tree

Mathematics Subject Classification ID

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

Recommendations

• Further results on digital search trees
• Asymptotic variance of random symmetric digital search trees
• On the variance of the internal path length of generalized digital trees -- the Mellin convolution approach
• On The variance of the extremal path length in a symmetric digital trie
• The variance of the profile in digital search trees

Cited in

(20)

• Further results on digital search trees
• Analytical depoissonization and its applications
• A general limit theorem for recursive algorithms and combinatorial structures
• On the variance of the internal path length of generalized digital trees -- the Mellin convolution approach
• The variance of the height of digital search trees
• Continuous-time digital search tree and a border aggregation model
• The k-th total path length and the total Steiner k-distance for digital search trees
• Probabilistic analysis of the asymmetric digital search trees
• scientific article; zbMATH DE number 3961005 (Why is no real title available?)
• scientific article; zbMATH DE number 4039927 (Why is no real title available?)
• External Internal Nodes in Digital Search Trees via Mellin Transforms
• Approximate counting with m counters: A detailed analysis
• scientific article; zbMATH DE number 7051180 (Why is no real title available?)
• The Wiener index of random digital trees
• Digital search trees with m trees: level polynomials and insertion costs
• The variance of the profile in digital search trees
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• On the variance of a class of inductive valuations of data structures for digital search
• The total path length of split trees
• Distances in random digital search trees

This page was built for publication: Digital Search Trees Again Revisited: The Internal Path Length Perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4302286)