A note on the probabilistic analysis of patricia trees

DOI10.1002/rsa.3240030209zbMath0768.05083OpenAlexW2065493100MaRDI QIDQ3990222

Luc P. Devroye

Publication date: 28 June 1992

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240030209

zbMATH Keywords

strong convergenceprobabilistic analysisminimum distancemaximal distanceheight of a treePATRICIA trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Related Items

Profiles of PATRICIA tries, Analysis of random LC tries, Asymmetric Rényi Problem, On the average depth of asymmetric LC-tries, On the Horton-Strahler number for random tries, Laws of large numbers and tail inequalities for random tries and PATRICIA trees

Cites Work

• Unnamed Item
• A probabilistic analysis of the height of tries and of the complexity of triesort
• On the performance evaluation of extendible hashing and trie searching
• Asymptotical growth of a class of random trees
• A diffusion limit for a class of randomly-growing binary trees
• On the balance property of Patricia tries: External path length viewpoint
• A note on the average depth of trees
• A study of trie-like structures under the density model
• On The variance of the extremal path length in a symmetric digital trie
• How many random questions are necessary to identify \(n\) distinct objects?
• Negative association of random variables, with applications
• Weighted sums of certain dependent random variables
• Paths in a random digital tree: limiting distributions
• Digital Search Trees Revisited
• Some results on V-ary asymmetric tries
• Analysis of Extendible Hashing
• Probability Inequalities for Sums of Bounded Random Variables
• Association of Random Variables, with Applications
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations