A Rappels algorithmiques
415
Fonction supprimerFusion(élément X, Arbre A)
// Précondition : A est un arbre binaire de recherche.
// Postcondition : Retourne l’arbre initial s’il ne contenait pas X ; sinon,
retourne l’arbre obtenu en supprimant la première occurrence de X
rencontrée.
// Utilise : fusionner, supprimerFusion
si A == None alors
retourner None
si A.clé == X alors
retourner fusionner(A.gauche, A.droit)
sinon
si A.clé > X alors
A.gauche = supprimerFusion(X, A.gauche)
sinon
A.droit = supprimerFusion(X, A.droit)
retourner A
A.2.6 Arbres binaires de recherche randomisés
Le terme randomisé qui traduit le mot anglais « randomized », bien que couramment employé, n’est peut-être pas le plus adéquat : il s’agit, pour ce type d’arbre,
de choisir aléatoirement à chaque mise à jour de l’arbre entre deux algorithmes
d’insertion d’une nouvelle clé, l’une aux feuilles et l’autre sur un chemin allant de
la racine vers une feuille, ou bien entre deux procédures de suppression d’une clé,
effectuant une fusion droite ou gauche des deux sous-arbres du nœud contenant la
clé à supprimer. Le choix entre deux variantes pour les algorithmes d’insertion ou de
suppression se fait en tenant compte des tailles de chaque sous-arbre, qu’il faut donc
garder en mémoire : en chaque nœud de l’arbre est stockée la taille du sous-arbre
dont il est racine.
Insertion randomisée L’insertion randomisée utilise l’insertion à la racine :
L’insertion d’une clé X dans un arbre binaire de recherche A se fait à la racine avec
une probabilité p(A), et dans le sous-arbre pertinent (droit ou gauche, suivant les valeurs
respectives de X et de la racine de l’arbre) avec la probabilité complémentaire 1 − p(A).
Lorsque l’insertion dans un sous-arbre est choisie, elle se fait récursivement de façon
randomisée.
En conséquence, l’insertion d’une clé se fait à un endroit aléatoire du chemin
qui va de la racine à la feuille où la clé serait insérée par l’algorithme classique
d’insertion aux feuilles. Lorsque p(A) = 0 (respectivement p(A) = 1) pour tout
arbre A, nous retrouvons l’insertion aux feuilles (respectivement à la racine).
415
Fonction supprimerFusion(élément X, Arbre A)
// Précondition : A est un arbre binaire de recherche.
// Postcondition : Retourne l’arbre initial s’il ne contenait pas X ; sinon,
retourne l’arbre obtenu en supprimant la première occurrence de X
rencontrée.
// Utilise : fusionner, supprimerFusion
si A == None alors
retourner None
si A.clé == X alors
retourner fusionner(A.gauche, A.droit)
sinon
si A.clé > X alors
A.gauche = supprimerFusion(X, A.gauche)
sinon
A.droit = supprimerFusion(X, A.droit)
retourner A
A.2.6 Arbres binaires de recherche randomisés
Le terme randomisé qui traduit le mot anglais « randomized », bien que couramment employé, n’est peut-être pas le plus adéquat : il s’agit, pour ce type d’arbre,
de choisir aléatoirement à chaque mise à jour de l’arbre entre deux algorithmes
d’insertion d’une nouvelle clé, l’une aux feuilles et l’autre sur un chemin allant de
la racine vers une feuille, ou bien entre deux procédures de suppression d’une clé,
effectuant une fusion droite ou gauche des deux sous-arbres du nœud contenant la
clé à supprimer. Le choix entre deux variantes pour les algorithmes d’insertion ou de
suppression se fait en tenant compte des tailles de chaque sous-arbre, qu’il faut donc
garder en mémoire : en chaque nœud de l’arbre est stockée la taille du sous-arbre
dont il est racine.
Insertion randomisée L’insertion randomisée utilise l’insertion à la racine :
L’insertion d’une clé X dans un arbre binaire de recherche A se fait à la racine avec
une probabilité p(A), et dans le sous-arbre pertinent (droit ou gauche, suivant les valeurs
respectives de X et de la racine de l’arbre) avec la probabilité complémentaire 1 − p(A).
Lorsque l’insertion dans un sous-arbre est choisie, elle se fait récursivement de façon
randomisée.
En conséquence, l’insertion d’une clé se fait à un endroit aléatoire du chemin
qui va de la racine à la feuille où la clé serait insérée par l’algorithme classique
d’insertion aux feuilles. Lorsque p(A) = 0 (respectivement p(A) = 1) pour tout
arbre A, nous retrouvons l’insertion aux feuilles (respectivement à la racine).