A study of trie-like structures under the density model

DOI10.1214/aoap/1177005709zbMath0758.68051OpenAlexW2051008728MaRDI QIDQ1198580

Luc P. 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 treesrandom binary trees

Mathematics Subject Classification ID

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

Related Items

On the number of full levels in tries, On the distribution for the duration of a randomized leader election algorithm, A note on the probabilistic analysis of patricia trees, Process convergence for the complexity of radix selection on Markov sources, The expected profile of digital search trees, Size and path length of Patricia tries: Dynamical sources context, Analysis of random LC tries, Multiple choice tries and distributed hash tables, Expected worst-case partial match in random quadtries, Laws of large numbers and tail inequalities for random tries and PATRICIA trees