284
7 Arbres digitaux
récursives permettent ensuite de passer, via un dictionnaire, 2 à des équations
fonctionnelles sur les séries génératrices correspondantes.
– La taille S(ω) d’un trie construit sur un ensemble ω ∈ B est le nombre de nœuds
internes (à ne pas confondre avec le nombre |ω| de feuilles). La contribution de
la racine à la taille est 1 si l’ensemble ω contient au moins deux clés distinctes.
Ensuite il faut ajouter les tailles des sous-tries gauche et droit correspondant aux
ensembles ω \ 0 et ω \ 1. L’équation suivante définit récursivement la taille S(ω)
et utilise le fait que la taille est un paramètre additif :
S(ω) =
0
s i |ω| ≤ 1,
1 + S(ω \ 0) + S(ω \ 1) sinon.
(7.2)
– La longueur de cheminement externe (ω) ≡ lce(ω) se décompose récursivement
de manière analogue à la taille. Il s’agit là encore d’un paramètre additif. Ici
un nœud interne contribuera à la longueur de cheminement externe pour une
quantité égale au nombre de clés dans le sous-trie dont il est racine (ce nœud est
« traversé » par tous les chemins qui partent de la racine pour aller aux feuilles
du sous-trie). Nous obtenons donc
(ω) =
0
s i |ω| ≤ 1,
|ω| + \ 0) + \ 1) sinon.
(7.3)
– La hauteur h s’exprime elle aussi sous une forme récursive
h(ω) =
0
s i |ω| ≤ 1,
1 + max (h(ω \ 0), h(ω \ 1)) sinon.
(7.4)
La hauteur fait intervenir le maximum et n’est pas un paramètre additif. Elle ne
sera pas traitée aussi directement que la taille et la longueur de cheminement
externe. Pour k ≥ 0, nous notons χ k (ω) l’indicatrice de l’événement « le trie
construit sur l’ensemble ω est de hauteur h(ω) inférieure ou égale à k »
χ k (ω) = 1 {h(ω)≤k} .
(7.5)
Un trie de hauteur inférieure ou égale à 0 contient nécessairement 0 ou 1 clé.
Pour k ≥ 1, un trie est de hauteur inférieure ou égale à k si et seulement si les
deux sous-tries sont de hauteurs inférieures ou égales à k − 1. Ceci ce traduit par
2 Ce dictionnaire n’est pas celui de la méthode symbolique puisqu’il correspond à la décomposition
récursive par préfixes du trie et non à des opérations ensemblistes ou combinatoires.
7 Arbres digitaux
récursives permettent ensuite de passer, via un dictionnaire, 2 à des équations
fonctionnelles sur les séries génératrices correspondantes.
– La taille S(ω) d’un trie construit sur un ensemble ω ∈ B est le nombre de nœuds
internes (à ne pas confondre avec le nombre |ω| de feuilles). La contribution de
la racine à la taille est 1 si l’ensemble ω contient au moins deux clés distinctes.
Ensuite il faut ajouter les tailles des sous-tries gauche et droit correspondant aux
ensembles ω \ 0 et ω \ 1. L’équation suivante définit récursivement la taille S(ω)
et utilise le fait que la taille est un paramètre additif :
S(ω) =
0
s i |ω| ≤ 1,
1 + S(ω \ 0) + S(ω \ 1) sinon.
(7.2)
– La longueur de cheminement externe (ω) ≡ lce(ω) se décompose récursivement
de manière analogue à la taille. Il s’agit là encore d’un paramètre additif. Ici
un nœud interne contribuera à la longueur de cheminement externe pour une
quantité égale au nombre de clés dans le sous-trie dont il est racine (ce nœud est
« traversé » par tous les chemins qui partent de la racine pour aller aux feuilles
du sous-trie). Nous obtenons donc
(ω) =
0
s i |ω| ≤ 1,
|ω| + \ 0) + \ 1) sinon.
(7.3)
– La hauteur h s’exprime elle aussi sous une forme récursive
h(ω) =
0
s i |ω| ≤ 1,
1 + max (h(ω \ 0), h(ω \ 1)) sinon.
(7.4)
La hauteur fait intervenir le maximum et n’est pas un paramètre additif. Elle ne
sera pas traitée aussi directement que la taille et la longueur de cheminement
externe. Pour k ≥ 0, nous notons χ k (ω) l’indicatrice de l’événement « le trie
construit sur l’ensemble ω est de hauteur h(ω) inférieure ou égale à k »
χ k (ω) = 1 {h(ω)≤k} .
(7.5)
Un trie de hauteur inférieure ou égale à 0 contient nécessairement 0 ou 1 clé.
Pour k ≥ 1, un trie est de hauteur inférieure ou égale à k si et seulement si les
deux sous-tries sont de hauteurs inférieures ou égales à k − 1. Ceci ce traduit par
2 Ce dictionnaire n’est pas celui de la méthode symbolique puisqu’il correspond à la décomposition
récursive par préfixes du trie et non à des opérations ensemblistes ou combinatoires.