4.2 Familles simples d’arbres
143
Si nous prenons comme famille simple d’arbres la famille des arbres binaires non
vides, leur fonction génératrice est F (z) = C(z) − 1 et un calcul simple montre que
V (z) =
R(z)
√
1 − 4z
,
ce qui permet de retrouver la proposition 4.6.
Si maintenant la famille simple considérée est celle des arbres planaires, leur
fonction génératrice est P (z) = z C(z) et
V (z) =
1
2
R(z)
1 +
1
√
1 − 4z
.
Lorsque le paramètre additif considéré est la longueur de cheminement, le péage à
la racine est lc(τ ) = |τ | − 1 et la fonction associée est
LC(z) = z F
(z) − F (z).
D’où le corollaire suivant, qui donne la longueur de cheminement moyenne des
arbres planaires.
Corollaire 4.9 Soit τ n un arbre planaire choisi selon la loi uniforme parmi les
arbres de taille n. Sa longueur de cheminement moyenne vaut E[lc(τ n )] =
1
2 n
√
π n + O(n).
4.2.5 Un exemple : complexité de la différentiation
Nous montrons ici comment les idées que nous venons d’exposer permettent
d’obtenir la complexité moyenne d’un algorithme de différentiation symbolique
(cet exemple vient de Flajolet et Steyaert [95]). Nous avons rencontré un exemple
d’expressions arithmétiques en section 4.2.1 ; nous le reprenons et calculons la
complexité moyenne de la dérivation d’une expression de taille donnée n, construite
à partir des symboles x, exp, + et ∗ (dans cette section ∗ désigne le produit)
(figure 4.4).
L’algorithme de différentiation prend en entrée une expression f , représentée par
un arbre, et calcule l’expression dérivée df , elle aussi représentée par un arbre. La
mesure de la complexité de cet algorithme dépend de la taille de l’arbre dérivé, et le
paramètre que nous étudions est cette taille δ(f ) = |df |. Ce paramètre est additif,
143
Si nous prenons comme famille simple d’arbres la famille des arbres binaires non
vides, leur fonction génératrice est F (z) = C(z) − 1 et un calcul simple montre que
V (z) =
R(z)
√
1 − 4z
,
ce qui permet de retrouver la proposition 4.6.
Si maintenant la famille simple considérée est celle des arbres planaires, leur
fonction génératrice est P (z) = z C(z) et
V (z) =
1
2
R(z)
1 +
1
√
1 − 4z
.
Lorsque le paramètre additif considéré est la longueur de cheminement, le péage à
la racine est lc(τ ) = |τ | − 1 et la fonction associée est
LC(z) = z F
(z) − F (z).
D’où le corollaire suivant, qui donne la longueur de cheminement moyenne des
arbres planaires.
Corollaire 4.9 Soit τ n un arbre planaire choisi selon la loi uniforme parmi les
arbres de taille n. Sa longueur de cheminement moyenne vaut E[lc(τ n )] =
1
2 n
√
π n + O(n).
4.2.5 Un exemple : complexité de la différentiation
Nous montrons ici comment les idées que nous venons d’exposer permettent
d’obtenir la complexité moyenne d’un algorithme de différentiation symbolique
(cet exemple vient de Flajolet et Steyaert [95]). Nous avons rencontré un exemple
d’expressions arithmétiques en section 4.2.1 ; nous le reprenons et calculons la
complexité moyenne de la dérivation d’une expression de taille donnée n, construite
à partir des symboles x, exp, + et ∗ (dans cette section ∗ désigne le produit)
(figure 4.4).
L’algorithme de différentiation prend en entrée une expression f , représentée par
un arbre, et calcule l’expression dérivée df , elle aussi représentée par un arbre. La
mesure de la complexité de cet algorithme dépend de la taille de l’arbre dérivé, et le
paramètre que nous étudions est cette taille δ(f ) = |df |. Ce paramètre est additif,