Renewal theory in analysis of tries and strings

Abstract

We give a survey of a number of simple applications of renewal theory to problems on random strings and tries: insertion depth, size, insertion mode and imbalance of tries; variations for b-tries and Patricia tries; Khodak and Tunstall codes.

32 pages

References in corpus (6)

• Rounding of continuous random variables and oscillatory asymptotics
• A probabilistic analysis of some tree algorithms
• Long and short paths in uniform random recursive dags
• Dynamic tree algorithms
• Renewals for exponentially increasing lifetimes, with an application to digital search trees
• Novel Characteristics of Split Trees by use of Renewal Theory