6.5 Arbres binaires de recherche randomisés
265
La probabilité que x soit racine de τ est
1
n+1 (cf. la définition 6.33 de l’insertion
randomisée). La marque de la racine de τ est une valeur a ∈ X lorsque
– a était déjà racine de τ , événement qui se produit avec probabilité
1
n ,
– et l’insertion de x ne se fait pas à la racine, ce qui se produit avec probabilité
n
n+1 .
La probabilité que a soit racine de τ est donc
1
n
n
n+1 =
1
n+1 , ce qui signifie que la
loi de la marque de la racine est uniforme sur X ∪ {x}.
Regardons ensuite les sous-arbres de τ . Si x est insérée à la racine, alors
τ = (x, τx )
où τx sont les deux arbres obtenus par coupure de τ suivant x ; par le
lemme 6.38 ils sont indépendants et suivent la loi Ord. Sinon, l’insertion de x se
fait dans l’un des sous-arbres de τ , qui suit la loi Ord par la proposition 6.1. De
plus |τ (g) | < |τ | et |τ (d) | < |τ | car τ n’est pas vide. L’hypothèse de récurrence
s’applique donc et l’arbre obtenu par insertion randomisée de x dans τ (g) ou dans
τ (d) suit la loi Ord et est indépendant de l’autre sous-arbre de τ .
Nous avons vérifié les hypothèses de la proposition 6.36, et pouvons conclure
que τ suit la loi Ord.
Lemme 6.40 Soient τ et τ deux arbres binaires de recherche indépendants et de
même loi Ord, respectivement de taille n et n , marqués de telle sorte que toute
clé de τ soit inférieure à toute clé de τ . Alors l’arbre binaire de recherche obtenu
par fusion de τ et τ selon la probabilité de fusion droite égale à
n
n +n (dont
l’algorithme est décrit dans A.2.5) suit la loi Ord.
Preuve Par récurrence sur la somme n + n des tailles n = |τ | et n = |τ |.
Appelons T l’arbre résultat de la fusion de τ et τ . Si n = 0, l’arbre résultat de
la fusion est simplement τ , et suit par hypothèse la loi Ord. De même si n = 0.
Supposons qu’aucun des deux arbres τ et τ n’est vide.
Avec probabilité
n
n +n , c’est la fusion droite qui se produit, c’est-à-dire qu’est
effectuée la fusion de τ (d) et de τ . Or, la taille de τ (d) est strictement inférieure
à celle de τ puisque τ est non vide. Donc la somme des deux tailles |τ (d) | + |τ |
est strictement inférieure à n + n et l’hypothèse de récurrence s’applique : l’arbre
résultant de la fusion de τ (d) et de τ , appelons-le τ 1 , suit la loi Ord.
265
La probabilité que x soit racine de τ est
1
n+1 (cf. la définition 6.33 de l’insertion
randomisée). La marque de la racine de τ est une valeur a ∈ X lorsque
– a était déjà racine de τ , événement qui se produit avec probabilité
1
n ,
– et l’insertion de x ne se fait pas à la racine, ce qui se produit avec probabilité
n
n+1 .
La probabilité que a soit racine de τ est donc
1
n
n
n+1 =
1
n+1 , ce qui signifie que la
loi de la marque de la racine est uniforme sur X ∪ {x}.
Regardons ensuite les sous-arbres de τ . Si x est insérée à la racine, alors
τ = (x, τ
où τ
lemme 6.38 ils sont indépendants et suivent la loi Ord. Sinon, l’insertion de x se
fait dans l’un des sous-arbres de τ , qui suit la loi Ord par la proposition 6.1. De
plus |τ (g) | < |τ | et |τ (d) | < |τ | car τ n’est pas vide. L’hypothèse de récurrence
s’applique donc et l’arbre obtenu par insertion randomisée de x dans τ (g) ou dans
τ (d) suit la loi Ord et est indépendant de l’autre sous-arbre de τ .
Nous avons vérifié les hypothèses de la proposition 6.36, et pouvons conclure
que τ suit la loi Ord.
Lemme 6.40 Soient τ et τ deux arbres binaires de recherche indépendants et de
même loi Ord, respectivement de taille n et n , marqués de telle sorte que toute
clé de τ soit inférieure à toute clé de τ . Alors l’arbre binaire de recherche obtenu
par fusion de τ et τ selon la probabilité de fusion droite égale à
n
n +n (dont
l’algorithme est décrit dans A.2.5) suit la loi Ord.
Preuve Par récurrence sur la somme n + n des tailles n = |τ | et n = |τ |.
Appelons T l’arbre résultat de la fusion de τ et τ . Si n = 0, l’arbre résultat de
la fusion est simplement τ , et suit par hypothèse la loi Ord. De même si n = 0.
Supposons qu’aucun des deux arbres τ et τ n’est vide.
Avec probabilité
n
n +n , c’est la fusion droite qui se produit, c’est-à-dire qu’est
effectuée la fusion de τ (d) et de τ . Or, la taille de τ (d) est strictement inférieure
à celle de τ puisque τ est non vide. Donc la somme des deux tailles |τ (d) | + |τ |
est strictement inférieure à n + n et l’hypothèse de récurrence s’applique : l’arbre
résultant de la fusion de τ (d) et de τ , appelons-le τ 1 , suit la loi Ord.