An Analysis of the Height of Tries with Random Weights on the Edges

DOI10.1017/S0963548307008796zbMath1144.68054MaRDI QIDQ3512599

Nicolas Broutin, Luc P. Devroye

Publication date: 21 July 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05)

Related Items

Weighted height of random trees

Cites Work

• A probabilistic analysis of the height of tries and of the complexity of triesort
• Large deviations for the weighted height of an extended class of trees
• Left and right pathlengths in random binary trees
• The left-right-imbalance of binary search trees
• On the height of digital trees and related problems
• On the performance evaluation of extendible hashing and trie searching
• Asymptotical growth of a class of random trees
• On the average height of trees in digital search and dynamic hashing
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• Universal asymptotics for random tries and PATRICIA trees
• A Note on the Height of Suffix Trees
• More Combinatorial Properties of Certain Trees
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item