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

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

Cited in

(13)

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

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)