Premium
Generalized Digital Trees and Their Difference—Differential Equations
Author(s) -
Flajolet Philippe,
Richmond Bruce
Publication year - 1992
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.3240030309
Subject(s) - mathematics , trie , generating function , tree (set theory) , exponential function , ordinary differential equation , differential equation , function (biology) , discrete mathematics , algorithm , computer science , mathematical analysis , data structure , evolutionary biology , biology , programming language
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 ,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.