×

zbMATH — the first resource for mathematics

Generalized digital trees and their difference-differential equations. (English) Zbl 0758.60015
From the authors’ 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 tree and the digital search tree. The exponential generating function for the expected size of the tree satisfies a difference-differential equation of order \(b\), \[ {d^ b \over dz^ b} f(z)=e^ z+2e^{z/2}f(z/2). \] The solution involves going to ordinary (rather than exponential) generating functions, analyzing singularities by means of Mellin transforms and contour integration.

MSC:
60E10 Characteristic functions; other transforms
68R05 Combinatorics in computer science
60C05 Combinatorial probability
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aldous, Probability Theory Related Fields 79 pp 509– (1988)
[2] The Theory of Partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley, Reading, MA, 1976.
[3] Askey, Am. Math. Monthly 87 pp 346– (1980)
[4] Handbuch der Laplace Transformation, Vol. 1–3. Birkhäuser Verlag, Basel, Switzerland, 1955. · doi:10.1007/978-3-0348-4147-4
[5] Fagin, A.C.M. Trans. Database Syst. 4 pp 315– (1979)
[6] Flajolet, Discrete Math. 3 pp 216– (1990)
[7] Flajolet, SIAM J. Comput. 15 pp 629– (1986)
[8] Flajolet, SIAM J. Comput. 15 pp 748– (1986)
[9] and , Basic Hypergeometric Series, Encyclopedia of Mathematics and its Applications, Vol. 35, Cambridge University Press, Cambridge, England, 1990.
[10] Ramanujan: Twelve Lectures on Subjects Suggested by his Life and Work, third ed., Chelsea Publishing Company, New York, 1978. Reprinted and corrected from the first ed., Cambridge, 1940.
[11] and , Page usage in quadtree indexes. Report 1434, Institut National de Recherche en Informatique et an Automatique, May 1991, 19 pages. Accepted for publication, BIT.
[12] and , Trie partitioning process: Limiting distributions, CAAP’86, -Zanetacchi, Ed., of Lecture Notes in Computer Science, Vol. 214, 1986, pp. 196–210. Proceedings of the 11th Colloquium on Trees in Algebra and Programming, Nice France, March 1986.
[13] Kirschenhofer, Mathematika 38 pp 14– (1991)
[14] The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973.
[15] Konheim, Discrete Math. 4 pp 57– (1973)
[16] Larson, BIT 18 pp 184– (1978)
[17] Louchard, RAIRO Theoretical Inform. Applications 21 pp 479– (1987)
[18] Evolution of Random Search Trees, Wiley, New York, 1992. · Zbl 0762.68033
[19] Mahmoud, J. Algorithms 10 pp 52– (1989)
[20] Odlyzko, Adv. Math. 44 pp 180– (1982)
[21] Algorithms, second ed., Addison-Wesley, Reading, MA, 1988.
[22] The Use of Integral Transforms, McGraw-Hill, New York, 1972. · Zbl 0237.44001
[23] and , Analysis of algorithms and data structures, in Handbook of Theoretical Computer Science, Ed., Vol. A: Algorithms and Complexity. North Holland, Amsterdam, The Netherlands, 1990, Chap. 9, pp. 431–524. · Zbl 0900.68251
[24] and , A Course of Modern Analysis, fourth ed., Cambridge University Press, Cambridge, England, 1927. Reprinted 1973.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.