4.1 Les arbres binaires
127
intéressons-nous à la somme des longueurs de cheminement, cumulées sur tous les
arbres de taille n :
l n :=
τ :|τ |=n
lc(τ ),
que nous allons étudier en établissant d’abord une équation de récurrence reliant la
longueur de cheminement d’un arbre τ = (◦, τ (g) , τ (d) ) à celles de ses sous-arbres
gauche τ (g) et droit τ (d) :
lc(τ ) = |τ
(g)
| + |τ
(d)
| + lc(τ
(g) ) + lc(τ
(d) ).
(4.7)
En effet, soit x un nœud non racine d’un arbre τ , supposé donc être de taille au
moins 2. Supposons que x appartienne à τ (g) , le sous-arbre gauche de τ , et notons
N(x, τ ) et N(x, τ (g) ) sa profondeur (ou niveau) respectivement dans τ et dans τ (g) :
N(x, τ ) = 1 + N(x, τ (g) ). En sommant sur tous les nœuds de τ (g) , nous voyons
que
x∈τ (g)
N(x, τ ) = |τ
(g)
| +
x∈τ (g)
N(x, τ
(g) ).
Bien évidemment, une formule similaire est valide pour le sous-arbre droit τ (d) ;
l’équation (4.7) s’obtient ensuite en ajoutant les contributions des sous-arbres
gauche et droit. Reportée dans la définition de l n , elle donne tout d’abord
l n =
τ =(◦,τ (g) ,τ (d) ),|τ |=n
|τ
(g)
| + |τ
(d)
| + lc(τ
(g) ) + lc(τ
(d) )
que nous récrivons, τ (g) et τ (d) jouant des rôles similaires, en
l n = 2
τ =(◦,τ (g) ,τ (d) ),|τ |=n
|τ
(g)
| + 2
τ =(◦,τ (g) ,τ (d) ),|τ |=n
lc(τ
(g) ).
Décomposons maintenant chacune des deux sommes sur τ suivant la taille du sousarbre gauche τ (g) . Chaque sous-arbre τ (g) de taille k apparaît autant de fois qu’il
y a de sous-arbres droits τ (d) de taille pertinente, i.e., de taille n − 1 − k, et nous
connaissons le nombre de ces sous-arbres droits : c’est C n−1−k . Nous obtenons
donc, en sommant cette fois non plus sur τ , mais sur τ (g) , dont la taille k varie de 0
à n − 1 :
l n = 2
n−1
k=0
|τ (g) |=k
C n−k−1 |τ
(g)
| + 2
n−1
k=0
|τ (g) |=k
C n−k−1 lc(τ
(g) )
= 2
n−1
k=0
C n−k−1
|τ (g) |=k
|τ
(g)
| + 2
n−1
k=0
C n−k−1
|τ (g) |=k
lc(τ
(g) ),
127
intéressons-nous à la somme des longueurs de cheminement, cumulées sur tous les
arbres de taille n :
l n :=
τ :|τ |=n
lc(τ ),
que nous allons étudier en établissant d’abord une équation de récurrence reliant la
longueur de cheminement d’un arbre τ = (◦, τ (g) , τ (d) ) à celles de ses sous-arbres
gauche τ (g) et droit τ (d) :
lc(τ ) = |τ
(g)
| + |τ
(d)
| + lc(τ
(g) ) + lc(τ
(d) ).
(4.7)
En effet, soit x un nœud non racine d’un arbre τ , supposé donc être de taille au
moins 2. Supposons que x appartienne à τ (g) , le sous-arbre gauche de τ , et notons
N(x, τ ) et N(x, τ (g) ) sa profondeur (ou niveau) respectivement dans τ et dans τ (g) :
N(x, τ ) = 1 + N(x, τ (g) ). En sommant sur tous les nœuds de τ (g) , nous voyons
que
x∈τ (g)
N(x, τ ) = |τ
(g)
| +
x∈τ (g)
N(x, τ
(g) ).
Bien évidemment, une formule similaire est valide pour le sous-arbre droit τ (d) ;
l’équation (4.7) s’obtient ensuite en ajoutant les contributions des sous-arbres
gauche et droit. Reportée dans la définition de l n , elle donne tout d’abord
l n =
τ =(◦,τ (g) ,τ (d) ),|τ |=n
|τ
(g)
| + |τ
(d)
| + lc(τ
(g) ) + lc(τ
(d) )
que nous récrivons, τ (g) et τ (d) jouant des rôles similaires, en
l n = 2
τ =(◦,τ (g) ,τ (d) ),|τ |=n
|τ
(g)
| + 2
τ =(◦,τ (g) ,τ (d) ),|τ |=n
lc(τ
(g) ).
Décomposons maintenant chacune des deux sommes sur τ suivant la taille du sousarbre gauche τ (g) . Chaque sous-arbre τ (g) de taille k apparaît autant de fois qu’il
y a de sous-arbres droits τ (d) de taille pertinente, i.e., de taille n − 1 − k, et nous
connaissons le nombre de ces sous-arbres droits : c’est C n−1−k . Nous obtenons
donc, en sommant cette fois non plus sur τ , mais sur τ (g) , dont la taille k varie de 0
à n − 1 :
l n = 2
n−1
k=0
|τ (g) |=k
C n−k−1 |τ
(g)
| + 2
n−1
k=0
|τ (g) |=k
C n−k−1 lc(τ
(g) )
= 2
n−1
k=0
C n−k−1
|τ (g) |=k
|τ
(g)
| + 2
n−1
k=0
C n−k−1
|τ (g) |=k
lc(τ
(g) ),