Some results on V-ary asymmetric tries

DOI10.1016/0196-6774(88)90039-9zbMath0637.68072OpenAlexW2067215545MaRDI QIDQ3777471

Wojciech Szpankowski

Publication date: 1988

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cstech/501

zbMATH Keywords

factorial momentssyntactic monoidinfix codeasymmetric triesefficiency of algorithms.radix search triesrandom family of triesreflective codesThue code

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Geometric probability and stochastic geometry (60D05) Searching and sorting (68P10) Formal languages and automata (68Q45)

Related Items

Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, A note on the probabilistic analysis of patricia trees, Further results on digital search trees, The evaluation of an alternative sum with applications to the analysis of some data structures, On the balance property of Patricia tries: External path length viewpoint, Smoothed heights of tries and patricia tries, On the height of digital trees and related problems, On tries, contention trees and their analysis, A characterization of digital search trees from the successful search viewpoint, Mellin transforms and asymptotics: Harmonic sums, Mellin transforms and asymptotics: Finite differences and Rice's integrals, A note on binomial recurrences arising in the analysis of algorithms, On the Stack-Size of General Tries, Analysis of random LC tries, On The variance of the extremal path length in a symmetric digital trie, Yet another application of a binomial recurrence. Order statistics, Multiple choice tries and distributed hash tables, Expected worst-case partial match in random quadtries, On the average depth of asymmetric LC-tries, Some results on tries with adaptive branching., Laws of large numbers and tail inequalities for random tries and PATRICIA trees