%0 Journal Article
%T On the Average Profile of Symmetric Digital Search Trees
%A Charles Knessl
%A Wojciech Szpankowski
%J Online Journal of Analytic Combinatorics
%D 2009
%I University of Auckland
%X A digital search tree (DST) ¨C one of the most fundamental data structures on words ¨C is a digital tree in which keys (strings, words) are stored directly in (internal) nodes. The profile of a digital search tree is a parameter that counts the number of nodes at the same distance from the root. It is a function of the number of nodes and the distance from the root. Several tree parameters, such as height, size, depth, shortest path, and fill-up level, can be uniformly analyzed through the profile. In this note we analyze asymptotically the average profile for a symmetric digital search tree in which strings are generated by an unbiased memoryless source. We show that the average profile undergoes several phase transitions: initially it resembles a full tree until it starts growing algebraically with the number of nodes, and then it decays first algebraically, then exponentially, and finally quadratic exponentially. We derive these results by a combinational of analytic techniques, such as the saddle point method.
%U http://analytic-combinatorics.org/index.php/ojac/article/view/58