The profile of a trie, the most popular data structures on words, is a parameter that represents the number of nodes (either internal or external) with the same distance to the root. Several, if not all, trie parameters such as height, size, depth, shortest path, and fill-up level can be uniformly analyzed through the (external and internal) profiles. The analysis of profiles is surprisingly arduous but once it is carried out it reveals unusually intriguing and interesting behavior. We present a detailed study of the distribution of the profiles in a trie built over strings generated by a memoryless source (extension to Markov sources is possible). Our results are derived by methods of analytic algorithmics such as generating functions, Mellin transform, Poissonization and de-Poissonization, the saddle-point method, singularity analysis and uniform asymptotic analysis.
['Gahyun Park', 'Hsien-Kuei Hwang', 'Pierre Nicodème', 'Wojciech Szpankowski']
Profile of tries