The expected profile of digital search trees

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:118

Article

Drmota, Michael¹  Szpankowski, Wojciech² 

[1] TU Wien, Inst Diskrete Math & Geometrie, A-1040 Vienna, Austria

[2] Purdue Univ, Dept Comp Sci, W Lafayette, IN 47907 USA

关键词: Digital search trees;    Tree profiles;    Analytic combinatorics;    Analysis of algorithms;    Recurrences;    Generating functions;    Poissonization;    Mellin transform;    Saddle point method;   

DOI  :  10.1016/j.jcta.2011.04.001

来源: Elsevier

【 摘 要 】

A digital search tree (DST) is a fundamental data structure on words that finds various applications from the popular Lempel-Ziv'78 data compression scheme to distributed hash tables. The profile of a DST measures the number of nodes at the same distance from the root; it depends on the number of stored strings and the distance from the root. Most parameters of DST (e.g., depth, height, fillup) can be expressed in terms of the profile. We study here asymptotics of the average profile in a DST built from sequences generated independently by a memoryless source. After representing the average profile by a recurrence, we solve it using a wide range of analytic tools. This analysis is surprisingly demanding but once it is carried out it reveals an unusually intriguing and interesting behavior. The average profile undergoes phase transitions when moving from the root to the longest path: at first it resembles a full tree until it abruptly starts growing polynomially and oscillating in this range. These results are derived by methods of analytic combinatorics such as generating functions, Mellin transform, poissonization and depoissonization, the saddle point method, singularity analysis and uniform asymptotic analysis. (C) 2011 Elsevier Inc. All rights reserved.

【 授权许可】

Free