Premium
On the number of full levels in tries
Author(s) -
Knessl Charles,
Szpankowski Wojciech
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20023
Subject(s) - trie , mathematics , binary tree , combinatorics , symbol (formal) , binary logarithm , binary number , mellin transform , tree (set theory) , value (mathematics) , discrete mathematics , point (geometry) , distribution (mathematics) , expected value , arithmetic , computer science , statistics , data structure , mathematical analysis , laplace transform , geometry , programming language
We study the asymptotic distribution of the fill‐up level in a binary trie built over n independent strings generated by a biased memoryless source. The fill‐up level is the number of full levels in a tree. A level is full if it contains the maximum allowable number of nodes (e.g., in a binary tree level k can have up to 2 k nodes). The fill‐up level finds many interesting applications, e.g., in the internet IP lookup problem and in the analysis of level compressed tries (LC tries). In this paper, we present a complete asymptotic characterization of the fill‐up distribution. In particular, we prove that this distribution concentrates on one or two points around the most probably value k = ⌊log 1/ q n − log log log n + 1 + log log( p / q )⌋, where p > q = 1 − p is the probability of generating the more likely symbol (while q = 1 − p is the probability of the less likely symbol). We derive our results by analytic methods such as generating functions, Mellin transform, the saddle point method, and analytic depoissonization. We also present some numerical verification of our results. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004