On The variance of the extremal path length in a symmetric digital trie

DOI10.1016/0166-218X(89)90050-4zbMath0685.68059MaRDI QIDQ1262137

Peter Kirschenhofer, Wojciech Szpankowski, Prodinger, Helmut

Publication date: 1989

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

binary treesearch tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

A note on the probabilistic analysis of patricia trees, On the balance property of Patricia tries: External path length viewpoint, An analytic approach to the asymptotic variance of trie statistics and related structures, Process convergence for the complexity of radix selection on Markov sources, On the height of digital trees and related problems, A general limit theorem for recursive algorithms and combinatorial structures, On tries, contention trees and their analysis, A characterization of digital search trees from the successful search viewpoint, Mellin transforms and asymptotics: Harmonic sums, Mellin transforms and asymptotics: Finite differences and Rice's integrals, On the variance of a class of inductive valuations of data structures for digital search, A note on binomial recurrences arising in the analysis of algorithms, Probabilistic modeling of data structures on words. A reply to Professor Andersson's letter, The total path length of split trees, D?E?K=(1000)8, Analysis of random LC tries, Dependence between path-length and size in random digital trees, Analytic analysis of algorithms, The number of winners in a discrete geometrically distributed sample, Upper tail analysis of bucket sort and random tries, Upper tail analysis of bucket sort and random tries, On the variance of the internal path length of generalized digital trees -- the Mellin convolution approach, The Wiener Index of Random Digital Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The evaluation of an alternative sum with applications to the analysis of some data structures
• <tex>Q</tex>-ary collision resolution algorithms in random-access systems with free or blocked channel access
• Digital Search Trees Revisited
• Some results on V-ary asymmetric tries
• On some applications of formulae of Ramanujan in the analysis of algorithms