Séminaire Lotharingien de Combinatoire, B18g (1987).
[Formerly: Publ. I.R.M.A. Strasbourg, 1988, 358/S-18, p. 77-86.]

Francois Bergeron, Gilbert Labelle and Pierre Leroux

Functional Equations for Data Structures

Abstract. We show how tree-like structures (B-trees, AVL trees, binary trees, etc. ...) can be characterized by functional equations in the context of the theory of species of structures which has been introduced as a conceptual framework for enumerative combinatorics. The generating functions associated to these abstract data structures are directly derived from the corresponding functional equations.

The paper has been finally published under the same title in STACS 88 (Bordeaux, 1988), pp. 73-80, Lecture Notes in Comput. Sci., 294, Springer, Berlin, 1988.