38
1 Botanique
Fig. 1.37 Un arbre τ de
taille (nombre total de nœuds)
|τ | = 12, de hauteur
h(τ ) = 3, de niveau de
saturation s(τ ) = 1, de profil
(0, 2, 4, 2). La deuxième
génération est en rouge
sont respectivement la somme des profondeurs des nœuds internes, ou externes ;
la longueur de cheminement (totale) est la somme de ces deux paramètres :
lc(τ ) = lci(τ ) + lce(τ ).
Dans le cas particulier d’un arbre binaire complet, ses longueurs de cheminement interne et externe sont liées par
lce(τ ) = lci(τ ) + 2 Card (τ \ ∂τ ) .
(1.9)
Cette relation se montre facilement, par récurrence sur le nombre n de nœuds
internes. Le cas de base est obtenu pour n = 1 : il y a un seul arbre complet
ayant un nœud interne et deux feuilles ; ses longueurs de cheminement interne
et externe sont respectivement 0 et 2 et la relation (1.9) est bien vérifiée ; ensuite
le passage d’un arbre complet à n nœuds internes à un arbre complet à n + 1
nœuds internes se fait en remplaçant une feuille par un nœud interne et les deux
feuilles associées, et il est aisé de vérifier qu’une telle transformation conserve la
relation (1.9).
– La hauteur de τ est le niveau maximum d’une feuille de l’arbre τ , i.e., la
profondeur d’une feuille de la dernière génération :
h(τ ) = max
u∈∂τ
|u|.
– Le niveau de saturation de τ est le niveau minimum d’une feuille de τ :
s(τ ) = min
u∈∂τ
|u|.
– Le profil est la suite finie (p i , 0 ≤ i ≤ h(τ )) des nombres de feuilles à chaque
niveau de l’arbre : p i = Card{u ∈ ∂τ : |u| = i}.
– Il peut arriver que nous considérions des arbres paginés, i.e., des arbres dans
lesquels tout sous-arbre de taille au plus b (b est un entier ≥ 1 et représente la