On the height of digital trees and related problems

DOI10.1007/BF01759045zbMath0711.68035MaRDI QIDQ922689

Wojciech Szpankowski

Publication date: 1991

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

order statisticsalignmentsuffix treedigital treesBernoulli modelMarkovian modelheight of trees

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Data structures (68P05)

Related Items (13)

Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach ⋮ Faster average case low memory semi-external construction of the Burrows-Wheeler transform ⋮ Asymptotic properties of keys and functional dependencies in random databases ⋮ An Analysis of the Height of Tries with Random Weights on the Edges ⋮ Generic properties of subgroups of free groups and finite presentations ⋮ Uncommon suffix tries ⋮ On the Stack-Size of General Tries ⋮ Analysis of random LC tries ⋮ Random databases with approximate record matching ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ Sequential and indexed two-dimensional combinatorial template matching allowing rotations ⋮ Computing the shortest reset words of synchronizing automata ⋮ Laws of large numbers and tail inequalities for random tries and PATRICIA trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic analysis of the height of tries and of the complexity of triesort
• On the performance evaluation of extendible hashing and trie searching
• Asymptotical growth of a class of random trees
• A note on the analysis of extendible hashing
• On the average height of trees in digital search and dynamic hashing
• Probability approximations via the Poisson clumping heuristic
• On The variance of the extremal path length in a symmetric digital trie
• Tree algorithms for packet broadcast channels
• Paths in a random digital tree: limiting distributions
• Probabilistic analysis of optimum partitioning
• Counts of long aligned word matches among random letter sequences
• Some results on V-ary asymmetric tries
• Self-alignments in words and their applications
• A class of dependent random variables and their maxima

This page was built for publication: On the height of digital trees and related problems