Abstract
An increasing tree is a labelled rooted tree in which labels along any branch from the root go in increasing order. Under various guises, such trees have surfaced as tree representations of permutations, as data structures in computer science, and as probabilistic models in diverse applications.
We present a unified generating function approach to the enumeration of parameters on such trees. The counting generating functions for several basic parameters are shown to be related to a simple ordinary differential equation, d/dzY(z)=φ(Y(z)), which is non linear and autonomous.
Singularity analysis applied to the intervening generating functions then permits to analyze asymptotically a number of parameters of the trees, like: root degree, number of leaves, path length, and level of nodes. In this way it is found that various models share common features: path length is O(n log n), the distribution of node levels and number of leaves are asymptotically normal, etc.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Balińska, K. T., Quintas, L. V., and Szymansky, J. Random recursive forests. Preprint, August 1991.
Bender, E. A. Central and local limit theorems applied to asymptotic enumeration. Journal of Combinatorial Theory 15 (1973), 91–111.
Bergeron, F., Labelle, G., and Leroux, P. Computation of the expected number of leaves in a tree having a given automorphism, and related topics. preliminary version, 1991.
Burge, W. H. An analysis of a tree sorting method and some properties of a set of trees. In First USA-JAPAN Computer Conference Proceedings (October 1972), AFIPS and IPSJ, pp. 372–378.
Chen, W., and Ni, W. Heap ordered trees. Personal communication, October 1991. Based on Wen-Chun Ni's Master Thesis, National Taiwan University.
Comtet, L.Advanced Combinatorics. Reidel, Dordrecht, 1974.
Devroye, L. Applications of the theory of records in the study of random trees. Acta Informatica 26 (1988), 123–130.
Evgrafov, M. A.Analytic Functions. Dover, New York, 1966.
Flajolet, P. Random tree models in the analysis of algorithms. In PERFORMANCE'87 (1988), P.-J. Courtois and G. Latouche, Eds., Elsevier Science Publishers (North Holland), pp. 171–187. (Invited lecture).
Flajolet, P., Gonnet, G., Puech, C., and Robson, J. M. Analytic variations on quadtrees. Algorithmica (1992). 24 pages, to appear.
Flajolet, P., and Odlyzko, A. M. Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics 3, 2 (1990), 216–240.
Flajolet, P., and Soria, M. Gaussian limiting distributions for the number of components in combinatorial structures. Journal of Combinatorial Theory, Series A 53 (1990), 165–182.
Flajolet, P., and Soria, M. General combinatorial schemas: Gaussian limit distributions and exponential tails. Discrete Mathematics (1991). To appear in the Special Issue on Combinatorics and Algorithms, A. S. Fraenkel Editor. Available as Research Report 632, LRI, Université Paris-Sud, January 1991. 21 pages.
Ford, W. B.Studies on divergent series and summability and the asymptotic developments of functions defined by Maclaurin series, 3rd ed. Chelsea Publishing Company, New York, 1960.
Françon, J. Arbres binaires de recherche: Propriétés combinatoires et applications. RAIRO Informatique Théorique 10, 12 (Dec. 1976), 35–50.
Gastwirth, J. L. A probability model of a pyramid scheme. American Statistician 31 (1977), 79–82.
Gastwirth, J. L., and Bhattacharya, P. K. Two probability models of pyramid or chain letter schemes demonstrating that their promotional claims are unreliable. Operations Research 32, 3 (May–June 1984), 527–536.
Gonnet, G. H., and Baeza-Yates, R. Handbook of Algorithms and Data Structures: in Pascal and C, second ed. Addison-Wesley, 1991.
Goulden, I. P., and Jackson, D. M.Combinatorial Enumeration. John Wiley, New York, 1983.
Graham, R., Knuth, D., and Patashnik, O. Concrete Mathematics. Addison Wesley, 1989.
Hennequin, P. Combinatorial analysis of quicksort algorithm. RAIRO Theoretical Informatics and Applications 23, 3 (1989), 317–333.
Joyal, A. Une théorie combinatoire des séries formelles. Advances in Mathematics 42, 1 (1981), 1–82.
Knuth, D. E. The Art of Computer Programming, vol. 1: Fundamental Algorithms. Addison-Wesley, 1968. Second edition, 1973.
Knuth, D. E. The Art of Computer Programming, vol. 3: Sorting and Searching. Addison-Wesley, 1973.
Knuth, D. E., and Pittel, B. A recurrence related to trees. Proceedings of the American Mathematical Society 105, 2 (Feb. 1989), 335–349.
Leroux, P., and Viennot, G. X. Combinatorial resolution of systems of differential equations I: Ordinary differential equations. In Combinatoire Énumérative (1986), G. Labelle and P. Leroux, Eds., no. 1234 in Lecture Notes in Mathematics, Springer-Verlag, pp. 210–245.
Leroux, P., and Viennot, X. G. Combinatorial resolution of systems of differential equations. IV. separation of variables. Discrete Mathematics 72 (1988), 237–250.
Louchard, G. Exact and asymptotic distributions in digital and binary search trees. RAIRO Theoretical Informatics and Applications 21, 4 (1987), 479–495.
Mahmoud, H.Evolution of Random Search Trees. John Wiley, New York, 1991. In press.
Mahmoud, H. M. Distances in random plane-oriented recursive trees, 1991. Preprint. To appear in the Journal of Applied and Computational Mathematics, special issue on asymptotic analysis in discrete mathematics.
Mahmoud, H. M., Smythe, R. T., and Szymański, J. On the structure of random plane-oriented recursive trees and their branches, 1991. Preprint.
Meir, A., and Moon, J. W. On the altitude of nodes in random trees. Canadian Journal of Mathematics 30 (1978), 997–1015.
Meir, A., and Moon, J. W. Recursive trees with no nodes of out-degree one. Congressus Numerantium 66 (1988), 49–62.
Najock, D., and Heyde, C. C. On the number of terminal vertices in certain random trees with an application to stemma constructions in philology. Journal of Applied Probability 19 (1982), 675–680.
Stanley, R. P. Enumerative Combinatorics, vol. I. Wadsworth & Brooks/Cole, 1986.
Szymański, J. On a non-uniform random recursive tree. In Random Graphs '85, M. Karoński and Z. Palka, Eds., vol. 33 of Annals of Discrete Mathematics. North-Holland, 1987, pp. 297–306.
Titchmarsh, E. C. The Theory of Functions, second ed. Oxford University Press, 1939.
Vitter, J. S., and Flajolet, P. Analysis of algorithms and data structures. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed., vol. A: Algorithms and Complexity. North Holland, 1990, ch. 9, pp. 431–524.
Vuillemin, J. A unifying look at data structures. Communications of the ACM 23, 4 (Apr. 1980), 229–239.
Wilf, H. S. Generatingfunctionology. Academic Press, 1990.
Wilson, R. Functions with dominant singularities of the generalized algebraic-logarithmic type (II): On the order of the Hadamard product. Proceedings of the London Mathematical Society, Series 2 43, 2190 (1937), 417–438.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bergeron, F., Flajolet, P., Salvy, B. (1992). Varieties of increasing trees. In: Raoult, J.C. (eds) CAAP '92. CAAP 1992. Lecture Notes in Computer Science, vol 581. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55251-0_2
Download citation
DOI: https://doi.org/10.1007/3-540-55251-0_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55251-2
Online ISBN: 978-3-540-46799-1
eBook Packages: Springer Book Archive