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

DOI10.1016/0304-3975(89)90115-1zbMATH Open0678.68042OpenAlexW2077517696MaRDI QIDQ1124339FDOQ1124339

Authors: Wojciech Szpankowski, Peter Kirschenhofer, Helmut Prodinger 

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

Recommendations

• scientific article; zbMATH DE number 4072401
• Patricia tries again revisited
• Profiles of PATRICIA tries
• A note on the probabilistic analysis of patricia trees
• Expected external profile of PATRICIA tries

zbMATH Keywords

algorithmsasymptotic approximationsPatricia triesbalance propertyexternal path length

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The evaluation of an alternative sum with applications to the analysis of some data structures
• Digital Search Trees Revisited
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On The variance of the extremal path length in a symmetric digital trie
• <tex>Q</tex>-ary collision resolution algorithms in random-access systems with free or blocked channel access
• Some results on V-ary asymmetric tries
• Patricia tries again revisited
• Title not available (Why is that?)

Cited In (13)

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

This page was built for publication: On the balance property of Patricia tries: External path length viewpoint

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