Generalized Digital Trees and Their Difference—Differential Equations
Philippe Flajolet, Bruce M. Richmond · Random Structures and Algorithms · 1992
Abstract Consider a tree partitioning process in which n elements are split into b at the root of a tree ( b a design parameter), the rest going recursively into two subtrees with a binomial probability distribution. This extends some familiar tree data structures of computer science like the digital trie and the digital search tree. The exponential generating function for the expected size of the tree satisfies a difference–differential equation of order b , magnified image The solution involves going to ordinary (rather than exponential) generating functions, analyzing singularities by means of Mellin transforms and contour integration. The method is of some general interest since a large number of related problems on digital structures can be treated in this way via singularity analysis of ordinary generating functions.