New results on the size of tries

DOI10.1109/18.42197zbMath0684.68038OpenAlexW1993618625MaRDI QIDQ4734759

Mireille Régnier, Philippe Jacquet

Publication date: 1989

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/18.42197

zbMATH Keywords

communications protocolstrieshashing schemes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items (18)

Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach ⋮ Central limit theorems for additive functionals and fringe trees in tries ⋮ Limit theorems for recursive algorithms ⋮ On the distribution for the duration of a randomized leader election algorithm ⋮ Analytical depoissonization and its applications ⋮ Profiles of PATRICIA tries ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees ⋮ On the variance of a class of inductive valuations of data structures for digital search ⋮ A probabilistic analysis of some tree algorithms ⋮ Dependence between path-length and size in random digital trees ⋮ Multiple choice tries and distributed hash tables ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees ⋮ Upper tail analysis of bucket sort and random tries ⋮ Renewal theory in the analysis of tries and strings ⋮ Maximum likelihood analysis of algorithms and data structures ⋮ The Wiener Index of Random Digital Trees ⋮ Trie size in a dynamic list structure

This page was built for publication: New results on the size of tries