266
6 Arbres binaires de recherche
En outre, comme τ 1 est composé des clés de τ (d) et de τ , il est indépendant
de τ (g) ; en effet, τ suit la loi Ord, donc ses deux sous-arbres τ (d) et τ (g) sont
indépendants et nous avons supposé que τ et τ étaient indépendants.
Ainsi, dans l’algorithme de fusion droite, les deux arbres τ (g) et τ 1 qui sont les
deux sous-arbres, respectivement gauche et droit, de l’arbre T résultat de la fusion
de τ et τ sont indépendants et de loi Ord.
Il reste à voir la loi du rang de la clé à la racine de l’arbre fusionné T . Appelons
r(τ ) le rang de la clé à la racine d’un abr τ . Sachant qu’il s’agit d’une fusion droite,
et comme toutes les clés de de τ sont inférieures à celles de τ , le rang de la clé
à la racine de l’arbre fusionné T est celui de la clé à la racine de τ et pour tout
k = 1, . . . , n + n ,
P (r(T ) = k) =
n
n + n P
r(T ) = k
fusion droite
=
n
n + n P
r(τ
) = k
=
n
n + n
1
n .
Le raisonnement est analogue lorsque la fusion gauche se produit.
Proposition 6.41 Soient τ un abr sous la loi Ord et x une clé de τ . Alors l’arbre
binaire de recherche obtenu par suppression randomisée de x dans τ avec pour
probabilité q(τ ) =
|τ (g) |
|τ |−1 suit la loi Ord.
Preuve Nous raisonnons par récurrence sur n avec n + 1 = |τ |.
Si n = 0, la suppression de x conduit à l’arbre vide, et la proposition est vraie.
Si n ≥ 1, distinguons deux cas suivant si x est à la racine de τ ou pas. Si x n’est
pas à la racine de τ , alors la suppression a lieu dans l’un des deux sous-arbres de
τ , qui est de taille strictement plus petite que τ et donc l’hypothèse de récurrence
s’applique : ce sous-arbre est de loi Ord. De plus, il est indépendant de l’autre sousarbre de τ .
Si x est à la racine de τ , alors l’arbre τ obtenu par suppression de x dans τ est
le résultat de la fusion des sous-arbres gauche et droit de τ . Le choix de q(τ ) assure
par le lemme 6.40 que τ est de loi Ord.
Il reste à montrer que tout z, z valeur de clé de τ , z = x, a même probabilité 1/n
d’être la marque de la racine de τ . Distinguons là aussi deux cas suivant si x est à la
racine de τ ou pas.
6 Arbres binaires de recherche
En outre, comme τ 1 est composé des clés de τ (d) et de τ , il est indépendant
de τ (g) ; en effet, τ suit la loi Ord, donc ses deux sous-arbres τ (d) et τ (g) sont
indépendants et nous avons supposé que τ et τ étaient indépendants.
Ainsi, dans l’algorithme de fusion droite, les deux arbres τ (g) et τ 1 qui sont les
deux sous-arbres, respectivement gauche et droit, de l’arbre T résultat de la fusion
de τ et τ sont indépendants et de loi Ord.
Il reste à voir la loi du rang de la clé à la racine de l’arbre fusionné T . Appelons
r(τ ) le rang de la clé à la racine d’un abr τ . Sachant qu’il s’agit d’une fusion droite,
et comme toutes les clés de de τ sont inférieures à celles de τ , le rang de la clé
à la racine de l’arbre fusionné T est celui de la clé à la racine de τ et pour tout
k = 1, . . . , n + n ,
P (r(T ) = k) =
n
n + n P
r(T ) = k
fusion droite
=
n
n + n P
r(τ
) = k
=
n
n + n
1
n .
Le raisonnement est analogue lorsque la fusion gauche se produit.
Proposition 6.41 Soient τ un abr sous la loi Ord et x une clé de τ . Alors l’arbre
binaire de recherche obtenu par suppression randomisée de x dans τ avec pour
probabilité q(τ ) =
|τ (g) |
|τ |−1 suit la loi Ord.
Preuve Nous raisonnons par récurrence sur n avec n + 1 = |τ |.
Si n = 0, la suppression de x conduit à l’arbre vide, et la proposition est vraie.
Si n ≥ 1, distinguons deux cas suivant si x est à la racine de τ ou pas. Si x n’est
pas à la racine de τ , alors la suppression a lieu dans l’un des deux sous-arbres de
τ , qui est de taille strictement plus petite que τ et donc l’hypothèse de récurrence
s’applique : ce sous-arbre est de loi Ord. De plus, il est indépendant de l’autre sousarbre de τ .
Si x est à la racine de τ , alors l’arbre τ obtenu par suppression de x dans τ est
le résultat de la fusion des sous-arbres gauche et droit de τ . Le choix de q(τ ) assure
par le lemme 6.40 que τ est de loi Ord.
Il reste à montrer que tout z, z valeur de clé de τ , z = x, a même probabilité 1/n
d’être la marque de la racine de τ . Distinguons là aussi deux cas suivant si x est à la
racine de τ ou pas.