On the balance property of Patricia tries: External path length viewpoint

DOI10.1016/0304-3975(89)90115-1zbMath0678.68042OpenAlexW2077517696MaRDI QIDQ1124339

Wojciech Szpankowski, Peter Kirschenhofer, Prodinger, Helmut

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90115-1

zbMATH Keywords

algorithmsasymptotic approximationsPatricia triesbalance propertyexternal path length

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

A note on the probabilistic analysis of patricia trees, An analytic approach to the asymptotic variance of trie statistics and related structures, A general limit theorem for recursive algorithms and combinatorial structures, On the variance of a class of inductive valuations of data structures for digital search, Improved behaviour of tries by adaptive branching, A note on binomial recurrences arising in the analysis of algorithms, A high-speed dynamic full-text search method by using memory management, Probabilistic modeling of data structures on words. A reply to Professor Andersson's letter, Size and path length of Patricia tries: Dynamical sources context, Analysis of random LC tries, The Wiener Index of Random Digital Trees

Cites Work

• The evaluation of an alternative sum with applications to the analysis of some data structures
• On The variance of the extremal path length in a symmetric digital trie
• Patricia tries again revisited
• <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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item