40
1 Botanique
Définition 1.48 Soit une fonction r d’un ensemble d’arbres E vers R. Un paramètre additif sur l’ensemble E est une fonction v de E vers R qui peut s’exprimer
additivement en fonction des M sous-arbres enfants de la racine :
v(τ ) = r(τ ) +
M
i=1
v(τ
i ),
où les τ i sont les sous-arbres issus des enfants de la racine, et où r(τ ) est la valeur
liée à la racine, aussi appelée péage.
En particulier, si v est un paramètre additif sur un arbre binaire τ =
•, τ (g) , τ (d)
,
v(τ ) = r(τ ) + v
τ
(g)
+ v
τ
(d)
.
(1.10)
Le péage associé à la racine, r(τ ), est en général très simple. Par exemple, le
paramètre taille, associant à un arbre son nombre de nœuds, est obtenu pour
r(τ ) = 1 ; le paramètre longueur de cheminement correspond à r(τ ) = |τ | − 1, où
|τ | est le nombre de nœuds de l’arbre τ . Un autre exemple classique de paramètre
additif est le nombre de nœuds d’arité donnée ; dans un arbre binaire, nous nous
intéresserons ainsi aux nombres de nœuds doubles, simples, ou sans descendants.
Par exemple, le nombre de nœuds doubles dans un arbre binaire est obtenu en
prenant comme valeur à la racine dans l’équation (1.10) r(τ ) = 1 si les sous-arbres
gauche et droit sont tous deux non vides, et 0 sinon.
1.3.3 Loi d’un paramètre
L’étude d’un paramètre peut se faire, soit en établissant des bornes sur ses valeurs,
soit en regardant sa distribution sous un modèle probabiliste – que nous définirons
dans le chapitre suivant. Ces deux approches n’ont pas les mêmes prérequis :
l’établissement de bornes, par exemple sur la hauteur d’un arbre, peut se faire sans
connaître la distribution de probabilité sur les arbres ; nous en verrons un exemple
dans la section 4.4.2. Par contre, établir des résultats tels que la valeur moyenne
d’un paramètre ne peut se faire que dans un modèle probabiliste sur les arbres, et la
valeur obtenue dépend de cette distribution. Nous verrons dans la suite de ce livre
que, par exemple, la hauteur moyenne d’un arbre binaire de taille n est d’ordre
√
n
dans le modèle de Catalan où tous les arbres de même taille sont équiprobables (cf.
section 5.2.3), et d’ordre log n dans le modèle des arbres bourgeonnants, qui est la
version non marquée du modèle des permutations uniformes pour les arbres binaires
de recherche (cf. section 6.2).
1 Botanique
Définition 1.48 Soit une fonction r d’un ensemble d’arbres E vers R. Un paramètre additif sur l’ensemble E est une fonction v de E vers R qui peut s’exprimer
additivement en fonction des M sous-arbres enfants de la racine :
v(τ ) = r(τ ) +
M
i=1
v(τ
i ),
où les τ i sont les sous-arbres issus des enfants de la racine, et où r(τ ) est la valeur
liée à la racine, aussi appelée péage.
En particulier, si v est un paramètre additif sur un arbre binaire τ =
•, τ (g) , τ (d)
,
v(τ ) = r(τ ) + v
τ
(g)
+ v
τ
(d)
.
(1.10)
Le péage associé à la racine, r(τ ), est en général très simple. Par exemple, le
paramètre taille, associant à un arbre son nombre de nœuds, est obtenu pour
r(τ ) = 1 ; le paramètre longueur de cheminement correspond à r(τ ) = |τ | − 1, où
|τ | est le nombre de nœuds de l’arbre τ . Un autre exemple classique de paramètre
additif est le nombre de nœuds d’arité donnée ; dans un arbre binaire, nous nous
intéresserons ainsi aux nombres de nœuds doubles, simples, ou sans descendants.
Par exemple, le nombre de nœuds doubles dans un arbre binaire est obtenu en
prenant comme valeur à la racine dans l’équation (1.10) r(τ ) = 1 si les sous-arbres
gauche et droit sont tous deux non vides, et 0 sinon.
1.3.3 Loi d’un paramètre
L’étude d’un paramètre peut se faire, soit en établissant des bornes sur ses valeurs,
soit en regardant sa distribution sous un modèle probabiliste – que nous définirons
dans le chapitre suivant. Ces deux approches n’ont pas les mêmes prérequis :
l’établissement de bornes, par exemple sur la hauteur d’un arbre, peut se faire sans
connaître la distribution de probabilité sur les arbres ; nous en verrons un exemple
dans la section 4.4.2. Par contre, établir des résultats tels que la valeur moyenne
d’un paramètre ne peut se faire que dans un modèle probabiliste sur les arbres, et la
valeur obtenue dépend de cette distribution. Nous verrons dans la suite de ce livre
que, par exemple, la hauteur moyenne d’un arbre binaire de taille n est d’ordre
√
n
dans le modèle de Catalan où tous les arbres de même taille sont équiprobables (cf.
section 5.2.3), et d’ordre log n dans le modèle des arbres bourgeonnants, qui est la
version non marquée du modèle des permutations uniformes pour les arbres binaires
de recherche (cf. section 6.2).