406
A Rappels algorithmiques
Fig. A.4 Un arbre binaire de
recherche
Nous présentons ci-dessous l’algorithme de recherche d’une clé, suivi
d’algorithmes de mise à jour : d’abord les algorithmes les plus courants d’insertion
d’une nouvelle clé, dit « insertion aux feuilles », et de la suppression d’une clé, avec
recherche de la clé à supprimer, et suppression de la clé à la racine d’un arbre. Nous
donnons ensuite deux algorithmes de mise à jour plus rarement utilisés : l’insertion
à la racine, grâce à l’algorithme de coupure, et la suppression d’une clé par fusion
de deux sous-arbres ; ces deux variantes permettent d’obtenir des algorithmes
randomisés de mise à jour sur les arbres binaires de recherche (figure A.4).
Lorsqu’il existe une version récursive et une version itérative d’un algorithme,
nous donnons la version récursive. La version itérative a naturellement la même
complexité, comptée en nombre de comparaisons de clés.
A.2.1 Recherche
Fonction chercher(élément X, Arbre A)
// Précondition : A est un arbre binaire de recherche.
// Postcondition : Retourne l’arbre vide si X ∈ A, sinon l’arbre ayant pour
racine le premier nœud de A rencontré contenant X.
// Utilise : chercher
si A == None alors
retourner None
si A.clé == X alors
retourner A
si A.clé < X alors
retourner chercher(X, A.droit)
sinon
retourner chercher(X, A.gauche)
A Rappels algorithmiques
Fig. A.4 Un arbre binaire de
recherche
Nous présentons ci-dessous l’algorithme de recherche d’une clé, suivi
d’algorithmes de mise à jour : d’abord les algorithmes les plus courants d’insertion
d’une nouvelle clé, dit « insertion aux feuilles », et de la suppression d’une clé, avec
recherche de la clé à supprimer, et suppression de la clé à la racine d’un arbre. Nous
donnons ensuite deux algorithmes de mise à jour plus rarement utilisés : l’insertion
à la racine, grâce à l’algorithme de coupure, et la suppression d’une clé par fusion
de deux sous-arbres ; ces deux variantes permettent d’obtenir des algorithmes
randomisés de mise à jour sur les arbres binaires de recherche (figure A.4).
Lorsqu’il existe une version récursive et une version itérative d’un algorithme,
nous donnons la version récursive. La version itérative a naturellement la même
complexité, comptée en nombre de comparaisons de clés.
A.2.1 Recherche
Fonction chercher(élément X, Arbre A)
// Précondition : A est un arbre binaire de recherche.
// Postcondition : Retourne l’arbre vide si X ∈ A, sinon l’arbre ayant pour
racine le premier nœud de A rencontré contenant X.
// Utilise : chercher
si A == None alors
retourner None
si A.clé == X alors
retourner A
si A.clé < X alors
retourner chercher(X, A.droit)
sinon
retourner chercher(X, A.gauche)