{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:18:20Z","timestamp":1760368700935},"reference-count":24,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5397,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1992,1]]},"abstract":"Abstract<\/jats:title>Consider a tree partitioning process in which n<\/jats:italic> elements are split into b<\/jats:italic> at the root of a tree (b<\/jats:italic> 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\u2013differential equation of order b<\/jats:italic>,<\/jats:p>magnified image<\/jats:alt-text><\/jats:graphic><\/jats:chem-struct><\/jats:chem-struct-wrap><\/jats:p>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<\/jats:italic> generating functions.<\/jats:p>","DOI":"10.1002\/rsa.3240030309","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T18:23:00Z","timestamp":1180203780000},"page":"305-320","source":"Crossref","is-referenced-by-count":36,"title":["Generalized Digital Trees and Their Difference\u2014Differential Equations"],"prefix":"10.1002","volume":"3","author":[{"given":"Philippe","family":"Flajolet","sequence":"first","affiliation":[]},{"given":"Bruce","family":"Richmond","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00318784"},{"key":"e_1_2_1_3_2","volume-title":"The Theory of Partitions, Encyclopedia of Mathematics and its Applications","author":"Andrews G. E.","year":"1976"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.2307\/2321202"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-4147-4"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320092"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0403019"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215046"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215054"},{"key":"e_1_2_1_10_2","volume-title":"Basic Hypergeometric Series, Encyclopedia of Mathematics and its Applications","author":"Gasper G.","year":"1990"},{"key":"e_1_2_1_11_2","volume-title":"Ramanujan: Twelve Lectures on Subjects Suggested by his Life and Work","author":"Hardy G. H.","year":"1978"},{"key":"e_1_2_1_12_2","unstructured":"M.HoshiandP.Flajolet Page usage in quadtree indexes. Report 1434 Institut National de Recherche en Informatique et an Automatique May1991 19 pages. Accepted for publication BIT."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0022669"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300006409"},{"key":"e_1_2_1_15_2","volume-title":"The Art of Computer Programming, Vol. 3: Sorting and Searching","author":"Knuth D. E.","year":"1973"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90114-3"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01931695"},{"issue":"4","key":"e_1_2_1_18_2","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1051\/ita\/1987210404791","article-title":"Exact and asymptotic distributions in digital and binary search trees","volume":"21","author":"Louchard G.","year":"1987","journal-title":"RAIRO Theoretical Inform. Applications"},{"key":"e_1_2_1_19_2","volume-title":"Evolution of Random Search Trees","author":"Mahmoud H.","year":"1992"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90023-0"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(82)90005-6"},{"key":"e_1_2_1_22_2","unstructured":"R.Sedgewick Algorithms second ed. Addison\u2010Wesley Reading MA 1988."},{"key":"e_1_2_1_23_2","volume-title":"The Use of Integral Transforms","author":"Sneddon I. N.","year":"1972"},{"key":"e_1_2_1_24_2","first-page":"431","volume-title":"Handbook of Theoretical Computer Science","author":"Vitter J. S.","year":"1990"},{"key":"e_1_2_1_25_2","volume-title":"A Course of Modern Analysis","author":"Whittaker E. T.","year":"1927"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240030309","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240030309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T16:03:10Z","timestamp":1698163390000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240030309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,1]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,1]]}},"alternative-id":["10.1002\/rsa.3240030309"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240030309","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,1]]}}}