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 structureslimit lawsrandom binary treesrandom trees

Mathematics Subject Classification ID

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

Review text

Binary trees are constructed from sequences of independent random variables with a common density on the unit interval. Asymptotic properties are studied for the height of a leaf and for the maximum height of the leaves.

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

(13)

• 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
• Process convergence for the complexity of radix selection on Markov sources
• Expected worst-case partial match in random quadtries
• Size and path length of Patricia tries: Dynamical sources context
• Analysis of random LC tries
• On the number of full levels in tries
• Multiple choice tries and distributed hash tables
• scientific article; zbMATH DE number 3896283 (Why is no real title available?)
• A note on the probabilistic analysis of patricia trees
• The expected profile of digital search trees
• Patricia's bad distributions
• The density of the ISE and local limit laws for embedded trees

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)