1.2 Arbres marqués
19
Fig. 1.16 Un arbre croissant
de taille 8 et son arbre des
rangs
Ainsi, l’arbre planaire non marqué obtenu en effaçant les marques dans l’arbre
croissant de la figure 1.16 est de taille 8 ; il a 5 sous-arbres de taille 1, un sousarbre de taille 2, un sous-arbre de taille 3, et enfin le sous-arbre de taille 8 égal à
l’arbre lui-même ; il y a donc
8!
1 5 ·2·3·8
= 840 marquages croissants possibles pour cet
arbre utilisant l’ensemble de marques toutes distinctes {1, 2, . . . , 8}.
Preuve Comme les marques sont toutes différentes, nous pouvons travailler avec
le marquage canonique : les marques sont alors les entiers de 1 à n où n = |τ |.
Attribuons un rang aux nœuds selon l’ordre hiérarchique. Cet ordre correspond à
un parcours de l’arbre par niveaux : d’abord la racine, puis ses enfants, ensuite les
enfants de ses enfants, etc ; les nœuds d’un niveau donné sont pris de gauche à droite
(rappelons qu’ici l’arbre est planaire) ; cf. section A.1.3. Par exemple, le parcours en
ordre hiérarchique de l’arbre du bas de la figure 1.16 (arbre des rangs obtenu après
marquage canonique) donne les marques des nœuds suivant l’ordre 1, 4, 2, 7, 3, 6,
5, 8.
Soit σ 0 l’une des n! permutations de {1, . . . , n}, i.e., un des n! marquages des
nœuds de l’arbre τ par les clés 1, . . . , n : le nœud de rang i a pour marque σ 0 (i).
À partir de ce marquage, il est possible de construire un marquage croissant sur τ ,
comme suit. Parcourons les n sous-arbres de τ dans l’ordre hiérarchique de leurs
racines : cet ordre assure qu’on traitera la marque d’un nœud après avoir traité celles
de ses ancêtres. Nous commençons par échanger la marque 1 avec la marque à la
racine (lorsque 1 est déjà à la racine, l’échange ne modifie pas le marquage), puis
recommençons pour chaque sous-arbre, en échangeant la marque à la racine du
sous-arbre avec la plus petite marque dudit sous-arbre.
19
Fig. 1.16 Un arbre croissant
de taille 8 et son arbre des
rangs
Ainsi, l’arbre planaire non marqué obtenu en effaçant les marques dans l’arbre
croissant de la figure 1.16 est de taille 8 ; il a 5 sous-arbres de taille 1, un sousarbre de taille 2, un sous-arbre de taille 3, et enfin le sous-arbre de taille 8 égal à
l’arbre lui-même ; il y a donc
8!
1 5 ·2·3·8
= 840 marquages croissants possibles pour cet
arbre utilisant l’ensemble de marques toutes distinctes {1, 2, . . . , 8}.
Preuve Comme les marques sont toutes différentes, nous pouvons travailler avec
le marquage canonique : les marques sont alors les entiers de 1 à n où n = |τ |.
Attribuons un rang aux nœuds selon l’ordre hiérarchique. Cet ordre correspond à
un parcours de l’arbre par niveaux : d’abord la racine, puis ses enfants, ensuite les
enfants de ses enfants, etc ; les nœuds d’un niveau donné sont pris de gauche à droite
(rappelons qu’ici l’arbre est planaire) ; cf. section A.1.3. Par exemple, le parcours en
ordre hiérarchique de l’arbre du bas de la figure 1.16 (arbre des rangs obtenu après
marquage canonique) donne les marques des nœuds suivant l’ordre 1, 4, 2, 7, 3, 6,
5, 8.
Soit σ 0 l’une des n! permutations de {1, . . . , n}, i.e., un des n! marquages des
nœuds de l’arbre τ par les clés 1, . . . , n : le nœud de rang i a pour marque σ 0 (i).
À partir de ce marquage, il est possible de construire un marquage croissant sur τ ,
comme suit. Parcourons les n sous-arbres de τ dans l’ordre hiérarchique de leurs
racines : cet ordre assure qu’on traitera la marque d’un nœud après avoir traité celles
de ses ancêtres. Nous commençons par échanger la marque 1 avec la marque à la
racine (lorsque 1 est déjà à la racine, l’échange ne modifie pas le marquage), puis
recommençons pour chaque sous-arbre, en échangeant la marque à la racine du
sous-arbre avec la plus petite marque dudit sous-arbre.