148
4 Approche combinatoire
Les nœuds spéciaux (ce sont les ancêtres de la dernière feuille de l’arbre selon
l’ordre hiérarchique) ont pour rangs les valeurs
[
n
2 k ] =
L
2
b
où k varie de 0 à L ; ils sont donc numérotés par des préfixes de la représentation
binaire de n. Dans la figure 4.7, les nœuds spéciaux sont indiqués en vert ; ils ont
pour rangs 7 1, 11, 110, 1100 et 11000 qui correspond à la dernière feuille.
A chaque niveau, le nœud spécial qui s’y trouve partitionne l’ensemble des
nœuds, en nœuds « de gauche » (avant le nœud spécial) et nœuds « de droite ».
Nous appelons naturellement sous-arbres spéciaux les sous-arbres enracinés en
les nœuds spéciaux. Remarquons que ce sont les seuls, parmi les sous-arbres d’un
arbre parfait, qui puissent ne pas être saturés. La taille du sous-arbre spécial enraciné
au niveau p est
s p = 2
L−p
+
0≤k
k b k .
En particulier, s 0 = n et s L = 1 ; cf. Knuth [156, p. 153]. Nous rassemblons tous
ces résultats dans la proposition suivante.
Proposition 4.11 Soit n = 2 L + j avec L = [log 2 n] et j ∈ {0, . . . , 2 L − 1}. Dans
un arbre parfait de taille n :
(i) Au niveau p (0 ≤ p ≤ L) le nœud spécial a pour rang r p = ([
n
2 L−p ]) 2 =
p
k=0 2 k b L−p+k ; les nœuds de gauche ont pour rang une valeur de
l’intervalle [2 p . . r p − 1], et les nœuds de droite une valeur de l’intervalle
[r p + 1 . . 2 p+1 − 1] (au dernier niveau, cet intervalle est vide).
(ii) Les tailles des sous-arbres spéciaux sont toutes différentes ; la taille du sousarbre spécial ayant sa racine au niveau p est
s p = 2
L−p
+
0≤k
k b k = n + 2
L−p
1 − [
n
2 L−p ]
.
(iii) Les sous-arbres non spéciaux sont saturés et leur taille vaut 2 k − 1 pour 0 ≤
k < L. Le nombre ν k de sous-arbres saturés de taille 2 k − 1 est
ν k = =
n
2 k−1 − −
n
2 k − 1 = =
n − 2 k−1
2 k
7 Ici « rang » signifie rang dans la numérotation en ordre hiérarchique, en commençant à 1, et en
binaire.
4 Approche combinatoire
Les nœuds spéciaux (ce sont les ancêtres de la dernière feuille de l’arbre selon
l’ordre hiérarchique) ont pour rangs les valeurs
[
n
2 k ] =
L
2
b
où k varie de 0 à L ; ils sont donc numérotés par des préfixes de la représentation
binaire de n. Dans la figure 4.7, les nœuds spéciaux sont indiqués en vert ; ils ont
pour rangs 7 1, 11, 110, 1100 et 11000 qui correspond à la dernière feuille.
A chaque niveau, le nœud spécial qui s’y trouve partitionne l’ensemble des
nœuds, en nœuds « de gauche » (avant le nœud spécial) et nœuds « de droite ».
Nous appelons naturellement sous-arbres spéciaux les sous-arbres enracinés en
les nœuds spéciaux. Remarquons que ce sont les seuls, parmi les sous-arbres d’un
arbre parfait, qui puissent ne pas être saturés. La taille du sous-arbre spécial enraciné
au niveau p est
s p = 2
L−p
+
0≤k
k b k .
En particulier, s 0 = n et s L = 1 ; cf. Knuth [156, p. 153]. Nous rassemblons tous
ces résultats dans la proposition suivante.
Proposition 4.11 Soit n = 2 L + j avec L = [log 2 n] et j ∈ {0, . . . , 2 L − 1}. Dans
un arbre parfait de taille n :
(i) Au niveau p (0 ≤ p ≤ L) le nœud spécial a pour rang r p = ([
n
2 L−p ]) 2 =
p
k=0 2 k b L−p+k ; les nœuds de gauche ont pour rang une valeur de
l’intervalle [2 p . . r p − 1], et les nœuds de droite une valeur de l’intervalle
[r p + 1 . . 2 p+1 − 1] (au dernier niveau, cet intervalle est vide).
(ii) Les tailles des sous-arbres spéciaux sont toutes différentes ; la taille du sousarbre spécial ayant sa racine au niveau p est
s p = 2
L−p
+
0≤k
k b k = n + 2
L−p
1 − [
n
2 L−p ]
.
(iii) Les sous-arbres non spéciaux sont saturés et leur taille vaut 2 k − 1 pour 0 ≤
k < L. Le nombre ν k de sous-arbres saturés de taille 2 k − 1 est
ν k = =
n
2 k−1 − −
n
2 k − 1 = =
n − 2 k−1
2 k
7 Ici « rang » signifie rang dans la numérotation en ordre hiérarchique, en commençant à 1, et en
binaire.