Asymptotical growth of a class of random trees
From MaRDI portal
Publication:1057565
DOI10.1214/aop/1176993000zbMath0563.60010OpenAlexW2091851562WikidataQ56688556 ScholiaQ56688556MaRDI QIDQ1057565
Publication date: 1985
Published in: The Annals of Probability (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1214/aop/1176993000
Analysis of algorithms and problem complexity (68Q25) Strong limit theorems (60F15) Combinatorial probability (60C05) Entropy and other invariants (28D20)
Related Items (36)
Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach ⋮ Longest Path Distance in Random Circuits ⋮ On the distribution for the duration of a randomized leader election algorithm ⋮ A diffusion limit for a class of randomly-growing binary trees ⋮ Distances in random digital search trees ⋮ A note on the probabilistic analysis of patricia trees ⋮ Smoothed heights of tries and patricia tries ⋮ On the variety of shapes in digital trees ⋮ An Analysis of the Height of Tries with Random Weights on the Edges ⋮ Profiles of PATRICIA tries ⋮ Joint string complexity for Markov sources: small data matters ⋮ On the shortest distance between orbits and the longest common substring problem ⋮ On the height of digital trees and related problems ⋮ Text indexing with errors ⋮ Probabilistic modeling of data structures on words. A reply to Professor Andersson's letter ⋮ Uncommon suffix tries ⋮ The expected profile of digital search trees ⋮ Analysis of random LC tries ⋮ Uniform distribution modulo one and binary search trees ⋮ A probabilistic analysis of some tree algorithms ⋮ On the silhouette of binary search trees ⋮ An almost sure result for path lengths in binary search trees ⋮ Asymmetric Rényi Problem ⋮ Multiple choice tries and distributed hash tables ⋮ How many random questions are necessary to identify \(n\) distinct objects? ⋮ Optimal data compression algorithm ⋮ Universal Data Compression Algorithm Based on Approximate String Matching ⋮ Renewal theory in the analysis of tries and strings ⋮ Expected worst-case partial match in random quadtries ⋮ On the average depth of asymmetric LC-tries ⋮ A new method for approximate indexing and dictionary lookup with one error ⋮ Digital search trees and chaos game representation ⋮ Search problems in groups and branching processes ⋮ On the Horton-Strahler number for random tries ⋮ Some results on tries with adaptive branching. ⋮ Laws of large numbers and tail inequalities for random tries and PATRICIA trees
This page was built for publication: Asymptotical growth of a class of random trees
