-
Danièle Gardy, University of Versailles
-
"Trees of Computer Science"
-
We will present
- Catalan trees (enumeration, path length, additive parameters)
- Simple families of trees (enumeration, additive parameters)
- Balanced trees, e.g., 2-3 trees, B-trees (enumeration for fixed height or fixed size)
The technics are those of analytic combinatoricsĀ :
starting from a functional specification of a set T of trees, we translate it into an equation of the enumerating generating function associated to T
(a bivariate function for additive parameters), solve the equation when
possible, and get the exact or asymptotic value of the number of trees of
given size (and value of the additive parameter when applicable) in the set T.