42
2 Aléa sur les arbres
Fig. 2.1 Deux arbres binaires complets avec 200 nœuds internes (et donc 201 nœuds externes)
tirés aléatoirement uniformément
d’arbres binaires de taille n, dit aussi « nombre de Catalan » (voir section 4.1 pour
le calcul de la valeur de C n ), d’où le terme de « modèle de Catalan » couramment
employé.
La figure 2.1 donne deux exemples d’arbres binaires complets avec 200 nœuds
internes (tirés aléatoirement uniformément).
Le choix uniforme parmi un ensemble d’arbres s’applique évidemment à d’autres
types d’arbres que les arbres binaires, ou à des sous-ensembles d’une classe d’arbres
définis par une autre notion que la taille : par exemple, c’est la hauteur qui peut être
fixée et un arbre sera choisi uniformément parmi les arbres de hauteur donnée ; par
analogie nous parlerons encore de « modèle de Catalan ». Ce modèle sera étudié
essentiellement au chapitre 4, où il sera appliqué à diverses classes d’arbres ; pour
certaines de ces classes, nous ne pousserons pas l’analyse au delà du dénombrement,
qui est la base permettant ensuite d’étudier les valeurs des divers paramètres que
nous avons définis en section 1.3, et dont nous verrons l’utilisation pour l’analyse
d’algorithmes dans le chapitre 3. Nous étudierons donc dans le chapitre 4
– les arbres binaires, comme nous l’avons déjà mentionné ;
– les familles simples d’arbres ;