126
4 Approche combinatoire
Fig. 4.2 Deux arbres
binaires de taille 6 et de
hauteurs minimale 2 et
maximale 5
binaire τ n à n nœuds :
log 2 n ≤ h(τ n ) ≤ n − 1.
(4.6)
La borne supérieure correspond à un arbre filiforme, i.e., avec un seul nœud à
chaque niveau, et la borne inférieure à un arbre le plus compact possible, ayant
ses feuilles sur les deux derniers niveaux seulement, par exemple à un arbre parfait
(cf. la définition 1.26). Nous illustrons ces deux types d’arbres dans la figure 4.2.
Cherchons maintenant un encadrement de la longueur de cheminement d’un
arbre τ n . Pour cela, rangeons les nœuds de cet arbre selon l’ordre hiérarchique ;
nous avons déjà rencontré cet ordre, qui découle d’un parcours en largeur de l’arbre,
lors de la démonstration de la formule d’équerre en section 1.2.4, et il est également
défini en section A.1.3. Le nœud de rang k est au pire à profondeur k − 1, comme
dans un arbre filiforme, ce qui donne la borne supérieure. Et le nœud de rang k
est au mieux à profondeur log 2 k, comme dans un arbre parfait ou assimilé, ce qui
donne la borne inférieure. Nous avons déjà donné une variante de cette borne dans
la proposition 3.13, pour la longueur de cheminement externe minimale, que nous
rappelons ci-après : la longueur de cheminement externe d’un arbre binaire à N
feuilles est supérieure ou égale à Nlog 2 N − N + 1.
En revenant à la longueur de cheminement totale, nous avons
1≤k≤n
log 2 k ≤ lc(τ n ) =
u∈τ n
|u| ≤
1≤k≤n
(k − 1).
D’où la proposition suivante, obtenue en évaluant le comportement asymptotique de
la première somme et en calculant la seconde.
Proposition 4.3 La longueur de cheminement d’un arbre binaire de taille n vérifie
n(log 2 n − 3) ≤ lc(τ n ) ≤
n(n − 1)
2
.
Sous le modèle de Catalan, la longueur de cheminement moyenne d’un arbre binaire
de taille n est donc d’ordre asymptotique au moins n log n, et au plus n 2 . En
fait, l’ordre asymptotique exact se situe entre les deux ; c’est n
√
n. Pour le voir,