4.3 Tas
147
Fig. 4.6 Un arbre parfait de hauteur 3 et de taille 9, et ses nœuds spéciaux en vert
Fig. 4.7 Numérotation des nœuds d’un arbre parfait en ordre hiérarchique ; les nœuds spéciaux
sont indiqués en vert
à la « dernière » feuille, i.e., à la feuille la plus à droite du dernier niveau. 5 Dans
un arbre saturé (cf. la définition 1.26), les nœuds spéciaux sont ceux du bord droit
de l’arbre. Dans l’exemple d’un arbre parfait de taille 9 donné en figure 4.6, ils sont
indiqués en bleu.
Soit donc un arbre parfait de taille n, et considérons la numérotation des nœuds de
l’arbre en ordre hiérarchique (cf. la section A.1.3 pour la définition), en commençant
à 1, et en écrivant chaque numéro en binaire.
Nous donnons dans la figure 4.7 un exemple pour une taille n = 24, dont
l’écriture binaire 6 est (24) 2 = 11000. Remarquons que la numérotation d’un nœud
est préfixe de celles de ses descendants et que, si on enlève le préfixe 1 aux rangs
des nœuds, on retrouve le numérotage canonique de la section 1.1.1.
Dans toute cette section, nous posons L = =log 2 n
Posons (n) 2 =
0≤k≤L 2 k b k avec, pour tout k, b k ∈ {0, 1} : les bits b k de
l’écriture binaire de n se calculent par exemple de proche en proche, par b L = 1,
puis pour k < L,
b k = [
n −
k<<≤L 2 b
2 k
].
5 Il s’agit effectivement du dernier nœud pour l’ordre hiérarchique défini en section A.1.3.
6 (n) 2 désigne la représentation binaire de l’entier n.
147
Fig. 4.6 Un arbre parfait de hauteur 3 et de taille 9, et ses nœuds spéciaux en vert
Fig. 4.7 Numérotation des nœuds d’un arbre parfait en ordre hiérarchique ; les nœuds spéciaux
sont indiqués en vert
à la « dernière » feuille, i.e., à la feuille la plus à droite du dernier niveau. 5 Dans
un arbre saturé (cf. la définition 1.26), les nœuds spéciaux sont ceux du bord droit
de l’arbre. Dans l’exemple d’un arbre parfait de taille 9 donné en figure 4.6, ils sont
indiqués en bleu.
Soit donc un arbre parfait de taille n, et considérons la numérotation des nœuds de
l’arbre en ordre hiérarchique (cf. la section A.1.3 pour la définition), en commençant
à 1, et en écrivant chaque numéro en binaire.
Nous donnons dans la figure 4.7 un exemple pour une taille n = 24, dont
l’écriture binaire 6 est (24) 2 = 11000. Remarquons que la numérotation d’un nœud
est préfixe de celles de ses descendants et que, si on enlève le préfixe 1 aux rangs
des nœuds, on retrouve le numérotage canonique de la section 1.1.1.
Dans toute cette section, nous posons L = =log 2 n
Posons (n) 2 =
0≤k≤L 2 k b k avec, pour tout k, b k ∈ {0, 1} : les bits b k de
l’écriture binaire de n se calculent par exemple de proche en proche, par b L = 1,
puis pour k < L,
b k = [
n −
k<<≤L 2 b
2 k
].
5 Il s’agit effectivement du dernier nœud pour l’ordre hiérarchique défini en section A.1.3.
6 (n) 2 désigne la représentation binaire de l’entier n.