×

Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire. (French) Zbl 0565.05037

We present a geometric method in order to enumerate binary trees with n nodes, investigating the class of binary trees with labeled leaves. A very simple device allows to generate all those trees by inserting the leaves iteratively, following the order given by the labels. It is then easy to verify that the number \(B'_ n\) of binary trees with \((n+1)\) labeled leaves satisfies the relation \(B'_ n=2\cdot (2n-1)\) \(B'_{n- 1}\). As there are \((n+1)!\) different possible labelings for the leaves, the number of binary trees satisfies: \(B_ n=2\cdot (2n-1)B_{n- 1}/(n+1)\), which gives the classical formula and \(B_ n\) is the Catalan number. From this construction, we obtain also an efficient procedure for the random generation of a binary tree. This technique runs in linear time and is thus better than those of G. D. Knott [Commun. ACM 20, 113-115 (1977; Zbl 0345.68025)] and D. Rotem [Inf. Process. Lett. 4, 58-61 (1975; Zbl 0323.05006)] which are briefly recalled.

MSC:

05C30 Enumeration in graph theory
05A15 Exact enumeration problems, generating functions
05C05 Trees
PDFBibTeX XMLCite
Full Text: EuDML

Online Encyclopedia of Integer Sequences:

Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).

References:

[1] A. V. AHO, J. E. HOPCROFT et J. D. ULLMAN, The Design and Analysis of Algorithms, Addison-Wesley, Reading, Mass, 1974. · Zbl 0326.68005
[2] L. COMTET, Analyse combinatoire, vol. 1, 2, Presses Universitaires de France, Paris, 1970. Zbl0221.05002 MR262087 · Zbl 0221.05002
[3] P. FLAJOLET, Analyse d’algorithmes de manipulation d’arbres et de fichiers, Thèse, Université de Paris-Sud, Paris, 1979.
[4] J. FRANÇON, Combinatoire des structures de données, Thèse, Faculté des Sciences de Strasbourg, 1979.
[5] J. FRANÇON, G. VIENNOT et J. VUILLEMIN, Description and Analysis of an Efficient Priority Queue Representation, Proc. of 19th I.E.E.E. Symp. on Found. of Comp. Sc., 1979. MR539825
[6] E. HOROWITZ et S. SAHNI, Fundamentals of Computer Algorithms, Computer Science Press, Potomac, Maryland, 1978. Zbl0442.68022 MR603626 · Zbl 0442.68022
[7] G. D. KNOTT, A Numbering System for Binary Trees, Comm. of A.C.M., vol. 20, n^\circ 2, 1977, p. 113-115. Zbl0345.68025 · Zbl 0345.68025 · doi:10.1145/359423.359434
[8] C. L. LIU, Generation of k-ary trees in Actes du 5e coll. de Lille sur les Arbres en Algèbre et en Programmation, Lille, 1980, p. 45-53; également Rapport n^\circ 27, I.N.R.I.A., Rocquencourt, 1980. Zbl0461.05020 MR620174 · Zbl 0461.05020
[9] A. PROSKUROWSKI, On the Generation of Binary Trees, J. A.C.M., vol. 27, n^\circ 1, 1980, p. 1-2. MR554275 · Zbl 0449.05018
[10] J. L. RÉMY, Construction, évaluation et amélioration systématiques de structures de données, R.A.I.R.O. Informatique théorique, vol. 14, n^\circ 1, 1980, p. 83-118. Zbl0434.68050 · Zbl 0434.68050
[11] J. L. RÉMY, Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire, Actes des 3es Journées de la RCP Complexité, Nice 1980et Rapport 80-P-053, C.R.I.N. 1980.
[12] D. ROTEM, On a Correspondence between Binary Trees and a Certain Type of Permutation, Information Processing Letters, vol. 4, n^\circ 1, 1975, p. 58-61. Zbl0323.05006 MR388841 · Zbl 0323.05006 · doi:10.1016/0020-0190(75)90002-2
[13] D. ROTEM et Y. L. VAROL, Generation of Binary Trees from Ballot Sequences, J. A.C.M., vol. 25, n^\circ 3, 1978, p. 396-404. Zbl0379.68029 MR495167 · Zbl 0379.68029 · doi:10.1145/322077.322082
[14] M. SOLOMON et R. A. FINKEL, A Note on Enumerating Binary Trees, J. A.C.M., vol. 27, n^\circ 1, 1980, p. 3-5. MR554276
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.