20
1 Botanique
Fig. 1.17 Un arbre non
croissant, et l’arbre obtenu
après avoir échangé la plus
petite clé avec celle de la
racine.
Regardons ce qui se passe sur un exemple. La figure 1.17 présente un arbre
à réordonner, et l’arbre qui est obtenu après avoir traité le premier nœud en
ordre hiérarchique, i.e., la racine. Le marquage de l’arbre initial correspond à
la permutation σ 0 = (5 4 6 7 8 2 1 3) : σ 0 (1) = 5, etc. Si nous poursuivons
récursivement ce réordonnement, nous obtenons le second arbre de la figure 1.16.
Chaque marquage initial σ 0 conduit ainsi à un unique marquage croissant ; par
contre plus d’un marquage initial σ 0 va aboutir à un marquage croissant σ donné
de τ . Plus précisément, soit τ i le sous-arbre enraciné en le nœud de rang i (1 ≤
i ≤ n) : il y a |τ i | échanges possibles qui vont amener à placer la plus petite clé du
sous-arbre à sa racine, et cela doit être fait pour chaque sous-arbre. Le nombre de
permutations amenant au marquage croissant σ est donc
n
i=1 |τ i |, et ne dépend que
de la forme de l’arbre, non de σ . Donc, en considérant toutes les permutations de
{1, . . . , n}, qui conduisent aux λ(τ ) marquages croissants σ possibles pour τ , nous
avons n! = λ(τ )
n
i=1 |τ i |.
Passons aux arbres binaires : certains d’entre eux ont une forme particulièrement
compacte ; cette compacité est la raison de l’efficacité algorithmique des tas, que
nous allons maintenant définir. Pour ce faire, et dans l’optique de l’étude de leurs
propriétés algorithmiques (cf. les sections 3.3.3 et 4.3), nous allons d’abord définir
les arbres non étiquetés sous-jacents : il s’agit des arbres parfaits et des arbres saturés
(nous renvoyons à la définition 1.3 pour le niveau d’un nœud).
Définition 1.26 Un arbre parfait est un arbre binaire non vide où tous les niveaux,
sauf éventuellement le dernier, sont pleins, et où les feuilles du dernier niveau sont
le plus à gauche possible. Quand le dernier niveau est lui aussi plein, on dit que
l’arbre est saturé (figure 1.18).
En conséquence, chaque niveau d’un arbre saturé est plein. Si l’arbre est de
hauteur h, il a 2 h+1 − 1 nœuds (l’arbre réduit à une racine est par convention
de hauteur 0) ; de manière équivalente la hauteur d’un arbre saturé de taille n est
log 2 (n + 1) − 1.
1 Botanique
Fig. 1.17 Un arbre non
croissant, et l’arbre obtenu
après avoir échangé la plus
petite clé avec celle de la
racine.
Regardons ce qui se passe sur un exemple. La figure 1.17 présente un arbre
à réordonner, et l’arbre qui est obtenu après avoir traité le premier nœud en
ordre hiérarchique, i.e., la racine. Le marquage de l’arbre initial correspond à
la permutation σ 0 = (5 4 6 7 8 2 1 3) : σ 0 (1) = 5, etc. Si nous poursuivons
récursivement ce réordonnement, nous obtenons le second arbre de la figure 1.16.
Chaque marquage initial σ 0 conduit ainsi à un unique marquage croissant ; par
contre plus d’un marquage initial σ 0 va aboutir à un marquage croissant σ donné
de τ . Plus précisément, soit τ i le sous-arbre enraciné en le nœud de rang i (1 ≤
i ≤ n) : il y a |τ i | échanges possibles qui vont amener à placer la plus petite clé du
sous-arbre à sa racine, et cela doit être fait pour chaque sous-arbre. Le nombre de
permutations amenant au marquage croissant σ est donc
n
i=1 |τ i |, et ne dépend que
de la forme de l’arbre, non de σ . Donc, en considérant toutes les permutations de
{1, . . . , n}, qui conduisent aux λ(τ ) marquages croissants σ possibles pour τ , nous
avons n! = λ(τ )
n
i=1 |τ i |.
Passons aux arbres binaires : certains d’entre eux ont une forme particulièrement
compacte ; cette compacité est la raison de l’efficacité algorithmique des tas, que
nous allons maintenant définir. Pour ce faire, et dans l’optique de l’étude de leurs
propriétés algorithmiques (cf. les sections 3.3.3 et 4.3), nous allons d’abord définir
les arbres non étiquetés sous-jacents : il s’agit des arbres parfaits et des arbres saturés
(nous renvoyons à la définition 1.3 pour le niveau d’un nœud).
Définition 1.26 Un arbre parfait est un arbre binaire non vide où tous les niveaux,
sauf éventuellement le dernier, sont pleins, et où les feuilles du dernier niveau sont
le plus à gauche possible. Quand le dernier niveau est lui aussi plein, on dit que
l’arbre est saturé (figure 1.18).
En conséquence, chaque niveau d’un arbre saturé est plein. Si l’arbre est de
hauteur h, il a 2 h+1 − 1 nœuds (l’arbre réduit à une racine est par convention
de hauteur 0) ; de manière équivalente la hauteur d’un arbre saturé de taille n est
log 2 (n + 1) − 1.