146
4 Approche combinatoire
Proposition 4.10 Soit f une expression arithmétique construite sur l’ensemble de
symboles S = {(x, 0), (exp, 1), (+, 2), (∗, 2)}. Sous le modèle de Catalan, la taille
moyenne d’une expression obtenue par dérivation d’une expression de taille n vaut
asymptotiquement
E[δ(f )] =
3 +
√
2
28
n
3/2 (1 + o(1)) = 0,15765 . . . n
3/2 (1 + o(1)).
4.3 Tas
Les tas ont été définis en section 1.2.4 comme des arbres parfaits croissants.
Ils peuvent avoir des clés répétées ; cependant, pour les dénombrer puis analyser
leur coût algorithmique, nous supposons que les n clés d’un tas de taille n sont
toutes distinctes. Nous avons vu (cf. Proposition 1.16) que nous pouvons alors
nous ramener par marquage canonique au cas où ce sont les entiers {1, 2, . . . , n}
(figure 4.5).
La première étape vers un dénombrement des tas de taille donnée n passe par
l’étude des tailles des différents sous-arbres d’un arbre parfait de taille n ; dans un
deuxième temps nous utilisons le dénombrement des arbres croissants par la formule
d’équerre de la section 1.2.4, pour obtenir une formule exacte donnant le nombre de
tas de taille n. Tout ceci fait l’objet de la section 4.3.1, puis nous passons à l’étude
asymptotique de ce nombre en section 4.3.2, avant de nous tourner brièvement vers
les coûts des opérations sur les tas en section 4.3.3.
4.3.1 Nombre de tas de taille donnée
Dans l’étude qui suit, certains nœuds d’un arbre parfait, dits spéciaux [156, pp. 152–
153], jouent un rôle particulier : il s’agit de ceux qui sont sur le chemin de la racine
Fig. 4.5 Un exemple de tas
construit sur les clés
{1, . . . , 9}
4 Approche combinatoire
Proposition 4.10 Soit f une expression arithmétique construite sur l’ensemble de
symboles S = {(x, 0), (exp, 1), (+, 2), (∗, 2)}. Sous le modèle de Catalan, la taille
moyenne d’une expression obtenue par dérivation d’une expression de taille n vaut
asymptotiquement
E[δ(f )] =
3 +
√
2
28
n
3/2 (1 + o(1)) = 0,15765 . . . n
3/2 (1 + o(1)).
4.3 Tas
Les tas ont été définis en section 1.2.4 comme des arbres parfaits croissants.
Ils peuvent avoir des clés répétées ; cependant, pour les dénombrer puis analyser
leur coût algorithmique, nous supposons que les n clés d’un tas de taille n sont
toutes distinctes. Nous avons vu (cf. Proposition 1.16) que nous pouvons alors
nous ramener par marquage canonique au cas où ce sont les entiers {1, 2, . . . , n}
(figure 4.5).
La première étape vers un dénombrement des tas de taille donnée n passe par
l’étude des tailles des différents sous-arbres d’un arbre parfait de taille n ; dans un
deuxième temps nous utilisons le dénombrement des arbres croissants par la formule
d’équerre de la section 1.2.4, pour obtenir une formule exacte donnant le nombre de
tas de taille n. Tout ceci fait l’objet de la section 4.3.1, puis nous passons à l’étude
asymptotique de ce nombre en section 4.3.2, avant de nous tourner brièvement vers
les coûts des opérations sur les tas en section 4.3.3.
4.3.1 Nombre de tas de taille donnée
Dans l’étude qui suit, certains nœuds d’un arbre parfait, dits spéciaux [156, pp. 152–
153], jouent un rôle particulier : il s’agit de ceux qui sont sur le chemin de la racine
Fig. 4.5 Un exemple de tas
construit sur les clés
{1, . . . , 9}