A study of trie-like structures under the density model

DOI10.1214/AOAP/1177005709MaRDI QIDQ1198580zbMATH OpenOpenAlexFDO

Authors Luc Devroye

Publication date 16 January 1993

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1214/aoap/1177005709

zbMATH Keywords

data structuresrandom treeslimit lawsrandom binary trees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Functional limit theorems; invariance principles (60F17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 1303595
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Dynamical sources in information theory: A general analysis of trie structures
• A generalization of the trie data structure
• A Uniform Approach to the Analysis of Trie Structures That Store Prefixing-Keys
• scientific article; zbMATH DE number 3896283
• scientific article; zbMATH DE number 4775
• Gaussian distribution of trie depth for strongly tame sources
• A unifying framework for trie design heuristics

Cited in

(12)

• Multiple choice tries and distributed hash tables
• Analysis of random LC tries
• The expected profile of digital search trees
• On the number of full levels in tries
• scientific article; zbMATH DE number 3896283 (Why is no real title available?)
• A note on the probabilistic analysis of patricia trees
• On the distribution for the duration of a randomized leader election algorithm
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• Size and path length of Patricia tries: Dynamical sources context
• Expected worst-case partial match in random quadtries
• The density of the ISE and local limit laws for embedded trees
• Process convergence for the complexity of radix selection on Markov sources

This page was built for publication: A study of trie-like structures under the density model

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