416
A Rappels algorithmiques
Suppression randomisée Comme dans le cas standard, l’algorithme de suppression randomisée commence par chercher la clé à supprimer ; la différence apparaît
quand elle est trouvée et qu’il s’agit de supprimer la racine d’un (sous-)arbre. Le
choix se pose alors d’exécuter l’algorithme standard de suppression à la racine, ou
de fusionner les deux sous-arbres. Si la fusion est choisie, ce sera la fusion gauche
(resp. droite) avec une probabilité q(A) : il suffit d’adapter la fonction tirerAléa
pour qu’elle renvoie gauche avec la probabilité q(A), et droite avec la probabilité
complémentaire.
La suppression randomisée utilise donc l’algorithme de fusion de la façon
suivante :
– Si un des sous-arbres gauche ou droit est vide, renvoyer l’autre sous-arbre.
– Sinon, soient G = (x, G g , G d ) et D = (y, D g , D d ) les sous-arbres gauche et
droit. Renvoyer l’arbre obtenu récursivement par (x, G g , fusionner(G d , D))
avec une probabilité q(A), et renvoyer l’arbre (y, fusionner(G, D g ), D d ) avec
la probabilité complémentaire.
Sur l’exemple de la figure A.17, la suppression de la clé 15 à la racine de l’arbre
conduit à effectuer une des deux opérations de fusion, gauche ou droite, avec une
probabilité que nous avons supposée proportionnelle à la taille du sous-arbre dans
lequel s’effectue la fusion.
Fig. A.17 Suppression randomisée de la clé 15 à la racine de l’arbre A : nous avons pris une
probabilité q(A) =
A (g)
|A|−1 , et nous obtenons l’arbre de gauche avec une probabilité
3
7 , et celui de
droite avec la probabilité complémentaire
4
7
A Rappels algorithmiques
Suppression randomisée Comme dans le cas standard, l’algorithme de suppression randomisée commence par chercher la clé à supprimer ; la différence apparaît
quand elle est trouvée et qu’il s’agit de supprimer la racine d’un (sous-)arbre. Le
choix se pose alors d’exécuter l’algorithme standard de suppression à la racine, ou
de fusionner les deux sous-arbres. Si la fusion est choisie, ce sera la fusion gauche
(resp. droite) avec une probabilité q(A) : il suffit d’adapter la fonction tirerAléa
pour qu’elle renvoie gauche avec la probabilité q(A), et droite avec la probabilité
complémentaire.
La suppression randomisée utilise donc l’algorithme de fusion de la façon
suivante :
– Si un des sous-arbres gauche ou droit est vide, renvoyer l’autre sous-arbre.
– Sinon, soient G = (x, G g , G d ) et D = (y, D g , D d ) les sous-arbres gauche et
droit. Renvoyer l’arbre obtenu récursivement par (x, G g , fusionner(G d , D))
avec une probabilité q(A), et renvoyer l’arbre (y, fusionner(G, D g ), D d ) avec
la probabilité complémentaire.
Sur l’exemple de la figure A.17, la suppression de la clé 15 à la racine de l’arbre
conduit à effectuer une des deux opérations de fusion, gauche ou droite, avec une
probabilité que nous avons supposée proportionnelle à la taille du sous-arbre dans
lequel s’effectue la fusion.
Fig. A.17 Suppression randomisée de la clé 15 à la racine de l’arbre A : nous avons pris une
probabilité q(A) =
A (g)
|A|−1 , et nous obtenons l’arbre de gauche avec une probabilité
3
7 , et celui de
droite avec la probabilité complémentaire
4
7