262
6 Arbres binaires de recherche
Fig. 6.13 Un arbre binaire
de recherche dont la racine
est un nœud double, avec les
différents sous-arbres
intervenant dans la définition
de la suppression randomisée
grande clé du sous-arbre gauche de τ (dans le cas où x marque un nœud double,
puisque dans le cas d’une feuille ou d’un nœud simple, il suffit de supprimer le
nœud en question). Il existe un autre algorithme de suppression, qui est en quelque
sorte l’inverse de l’algorithme de coupure : il « fusionne » les sous-arbres gauche et
droit de τ pour créer un nouvel arbre binaire de recherche ; cf. les détails dans la
section A.2.6. D’où la définition ci-dessous, illustrée par l’arbre de la figure 6.13 :
Définition 6.34 La suppression randomisée d’une clé x dans un arbre binaire de
recherche consiste
– si x est dans une feuille, à supprimer cette feuille ;
– si x est dans un nœud simple, à supprimer ce nœud et rattacher son unique sousarbre à son parent (si x était à la racine, ce sous-arbre devient l’arbre tout entier) ;
– sinon, à procéder comme suit lorsque x marque un nœud double, en se plaçant
à la racine du sous-arbre τ dont la racine est marquée par x. Soient τ (g) =
(y, τ (gg) , τ (gd) ) et τ (d) = (z, τ (dg) , τ (dd) ) les sous-arbres (non vides) gauche
et droit de τ . Alors, avec une probabilité q(τ ) ∈ [0, 1], le résultat de la
suppression de x est l’arbre binaire de recherche ayant pour racine un nœud
marqué par y, de sous-arbre gauche τ (gg) et de sous-arbre droit obtenu en
fusionnant récursivement τ (gd) et τ (d) ; avec la probabilité complémentaire
1 − q(τ ) c’est l’arbre binaire de recherche dont la racine est marquée par z, le
sous-arbre gauche est obtenu par fusion récursive de τ (g) et τ (dg) , et le sous-arbre
droit est τ (dd) .
Nous pouvons maintenant donner une définition naturelle d’un arbre binaire de
recherche randomisé.
Définition 6.35 Un arbre binaire de recherche randomisé est un arbre binaire
de recherche construit à partir de l’arbre vide, par une suite d’insertions et de
suppressions randomisées telles que données dans les définitions 6.33 et 6.34.
La définition 6.35 est valable pour toutes valeurs p(τ ) et q(τ ) ; nous allons voir
dans le théorème 6.37 ci-dessous que le choix
p(τ ) =
1
|τ | + 1
;
q(τ ) =
|τ (g) |
|τ | − 1
donne des arbres binaires de recherche suivant la loi Ord quelles que soient la
distribution sur les clés et les opérations de mise à jour : insertions et suppressions.
6 Arbres binaires de recherche
Fig. 6.13 Un arbre binaire
de recherche dont la racine
est un nœud double, avec les
différents sous-arbres
intervenant dans la définition
de la suppression randomisée
grande clé du sous-arbre gauche de τ (dans le cas où x marque un nœud double,
puisque dans le cas d’une feuille ou d’un nœud simple, il suffit de supprimer le
nœud en question). Il existe un autre algorithme de suppression, qui est en quelque
sorte l’inverse de l’algorithme de coupure : il « fusionne » les sous-arbres gauche et
droit de τ pour créer un nouvel arbre binaire de recherche ; cf. les détails dans la
section A.2.6. D’où la définition ci-dessous, illustrée par l’arbre de la figure 6.13 :
Définition 6.34 La suppression randomisée d’une clé x dans un arbre binaire de
recherche consiste
– si x est dans une feuille, à supprimer cette feuille ;
– si x est dans un nœud simple, à supprimer ce nœud et rattacher son unique sousarbre à son parent (si x était à la racine, ce sous-arbre devient l’arbre tout entier) ;
– sinon, à procéder comme suit lorsque x marque un nœud double, en se plaçant
à la racine du sous-arbre τ dont la racine est marquée par x. Soient τ (g) =
(y, τ (gg) , τ (gd) ) et τ (d) = (z, τ (dg) , τ (dd) ) les sous-arbres (non vides) gauche
et droit de τ . Alors, avec une probabilité q(τ ) ∈ [0, 1], le résultat de la
suppression de x est l’arbre binaire de recherche ayant pour racine un nœud
marqué par y, de sous-arbre gauche τ (gg) et de sous-arbre droit obtenu en
fusionnant récursivement τ (gd) et τ (d) ; avec la probabilité complémentaire
1 − q(τ ) c’est l’arbre binaire de recherche dont la racine est marquée par z, le
sous-arbre gauche est obtenu par fusion récursive de τ (g) et τ (dg) , et le sous-arbre
droit est τ (dd) .
Nous pouvons maintenant donner une définition naturelle d’un arbre binaire de
recherche randomisé.
Définition 6.35 Un arbre binaire de recherche randomisé est un arbre binaire
de recherche construit à partir de l’arbre vide, par une suite d’insertions et de
suppressions randomisées telles que données dans les définitions 6.33 et 6.34.
La définition 6.35 est valable pour toutes valeurs p(τ ) et q(τ ) ; nous allons voir
dans le théorème 6.37 ci-dessous que le choix
p(τ ) =
1
|τ | + 1
;
q(τ ) =
|τ (g) |
|τ | − 1
donne des arbres binaires de recherche suivant la loi Ord quelles que soient la
distribution sur les clés et les opérations de mise à jour : insertions et suppressions.