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

DOI10.1016/0304-3975(89)90115-1MaRDI QIDQ1124339zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3961005 (Why is no real title available?)
• scientific article; zbMATH DE number 4039927 (Why is no real title available?)
• scientific article; zbMATH DE number 4088895 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3587312 (Why is no real title available?)
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• scientific article; zbMATH DE number 3327849 (Why is no real title available?)
• <tex>Q</tex>-ary collision resolution algorithms in random-access systems with free or blocked channel access
• Digital Search Trees Revisited
• On The variance of the extremal path length in a symmetric digital trie
• Patricia tries again revisited
• Some results on V-ary asymmetric tries
• The evaluation of an alternative sum with applications to the analysis of some data structures

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
• scientific article; zbMATH DE number 4072401 (Why is no real title available?)
• A note on the probabilistic analysis of patricia trees
• A general limit theorem for recursive algorithms and combinatorial structures
• 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)