24
1 Botanique
Dans le cas de clés égales, l’arbre complété fait apparaître un sous-arbre du type
où la feuille noire ne correspond pas à une possibilité d’insertion.
Nous allons maintenant présenter deux visions complémentaires d’un arbre
binaire de recherche, la première très liée aux algorithmes implémentant la construction d’un arbre par insertions successives de clés aux feuilles, la seconde exploitant
plutôt la définition récursive 1.31. Les deux constructions qui suivent, partant de la
même suite de clés, conduisent au même arbre.
Construction algorithmique dynamique
Soit n ≥ 1 et soient n clés x 1 , . . . , x n , c’est-à-dire n éléments distincts d’un
ensemble totalement ordonné . L’arbre binaire de recherche construit à partir de la
suite finie x 1 , . . . , x n est un arbre binaire de taille n, dans lequel chaque nœud est
muni d’une clé de la façon suivante : la première clé x 1 est mise à la racine. Puis
la deuxième clé x 2 est assignée au fils gauche si elle est inférieure ou égale à x 1 , et
au fils droit si elle est plus grande que x 1 . La clé suivante, x 3 , est ensuite comparée
à la racine ; si elle est inférieure ou égale à x 1 , elle est assignée au fils gauche si
celui-ci est inoccupé, et elle est comparée au fils gauche si celui-ci est occupé, allant
à sa gauche ou à sa droite selon qu’elle est inférieure ou égale ou bien supérieure au
fils gauche. De même, si la clé x 3 est supérieure à la clé racine, elle va dans le sousarbre droit. Nous continuons récursivement de cette façon jusqu’à avoir inséré toutes
les clés dans l’arbre. Après n insertions, 11 nous avons un arbre binaire de taille n,
dont chacun des n nœuds contient une clé, et qui satisfait la définition 1.30. Comme
mentionné plus haut, il est possible d’ajouter à l’arbre binaire n + 1 feuilles, qui
correspondent aux possibilités d’insertion, et nous obtenons alors un arbre binaire
complet. Un exemple de construction d’un arbre binaire de recherche de taille 5 est
montré figure 1.23.
11 L’algorithme de construction présenté ici est connu sous le nom d’« insertion aux feuilles » ;
il existe d’autres algorithmes d’insertion, notamment l’insertion à la racine présentée en section A.2.4.
1 Botanique
Dans le cas de clés égales, l’arbre complété fait apparaître un sous-arbre du type
où la feuille noire ne correspond pas à une possibilité d’insertion.
Nous allons maintenant présenter deux visions complémentaires d’un arbre
binaire de recherche, la première très liée aux algorithmes implémentant la construction d’un arbre par insertions successives de clés aux feuilles, la seconde exploitant
plutôt la définition récursive 1.31. Les deux constructions qui suivent, partant de la
même suite de clés, conduisent au même arbre.
Construction algorithmique dynamique
Soit n ≥ 1 et soient n clés x 1 , . . . , x n , c’est-à-dire n éléments distincts d’un
ensemble totalement ordonné . L’arbre binaire de recherche construit à partir de la
suite finie x 1 , . . . , x n est un arbre binaire de taille n, dans lequel chaque nœud est
muni d’une clé de la façon suivante : la première clé x 1 est mise à la racine. Puis
la deuxième clé x 2 est assignée au fils gauche si elle est inférieure ou égale à x 1 , et
au fils droit si elle est plus grande que x 1 . La clé suivante, x 3 , est ensuite comparée
à la racine ; si elle est inférieure ou égale à x 1 , elle est assignée au fils gauche si
celui-ci est inoccupé, et elle est comparée au fils gauche si celui-ci est occupé, allant
à sa gauche ou à sa droite selon qu’elle est inférieure ou égale ou bien supérieure au
fils gauche. De même, si la clé x 3 est supérieure à la clé racine, elle va dans le sousarbre droit. Nous continuons récursivement de cette façon jusqu’à avoir inséré toutes
les clés dans l’arbre. Après n insertions, 11 nous avons un arbre binaire de taille n,
dont chacun des n nœuds contient une clé, et qui satisfait la définition 1.30. Comme
mentionné plus haut, il est possible d’ajouter à l’arbre binaire n + 1 feuilles, qui
correspondent aux possibilités d’insertion, et nous obtenons alors un arbre binaire
complet. Un exemple de construction d’un arbre binaire de recherche de taille 5 est
montré figure 1.23.
11 L’algorithme de construction présenté ici est connu sous le nom d’« insertion aux feuilles » ;
il existe d’autres algorithmes d’insertion, notamment l’insertion à la racine présentée en section A.2.4.