264
6 Arbres binaires de recherche
de même loi Ord ; inversement, le lemme 6.40 montre que la fusion de deux arbres
de loi Ord fournit un arbre sous cette même loi. Les deux propositions 6.39 et 6.41
établissent quant à elles que les arbres obtenus par l’application des opérations
d’insertion et de suppression randomisées à un arbre binaire de recherche, toujours
sous la loi Ord, suivent eux aussi cette loi.
Lemme 6.38 Soient τ un abr de taille n de loi Ord contenant des clés x 1 , . . . , x n
dont le réordonnement est donné par la permutation σ :
x σ (1) < x σ (2) < · · · < x σ (n) .
Soit x une clé non présente dans τ . Soit p ∈ {1, . . . , n + 1}. Supposons que le rang
de x vaille p, autrement dit :
x ∈]x σ (p−1) , x σ (p) [.
Alors, les deux arbres τx obtenus par coupure de τ suivant x sont
indépendants et de loi Ord respectivement de taille p − 1 et n + 1 − p.
Preuve La clé x sépare les données x i , i = 1, . . . , n en deux paquets : les p − 1
données inférieures à x, disons
X
X >x = {x σ (j) , j = p, . . . , n + 1},
avec les conventions habituelles : si p = 1, le premier ensemble est vide et si
p = n + 1, le second ensemble est vide.
L’algorithme de coupure en A.2.4 construit τx , respectivement sur X
Comme τ est de loi Ord, les x i , i = 1, . . . , n sont i.i.d. et donc les arbres τ
loi uniforme sur S n . Et par conséquent (c’est là l’argument central), σ restreinte à
{1, . . . , p − 1} est uniforme sur S p−1 , respectivement σ restreinte à {p, . . . , n + 1}
est uniforme sur S n+1−p . Donc τx sont de loi Ord respectivement de taille
p − 1 et n + 1 − p.
Proposition 6.39 Soient τ un abr de loi Ord et x une clé non présente dans τ . Alors
l’arbre binaire de recherche obtenu par insertion randomisée de x dans τ avec pour
probabilité p(τ ) =
1
|τ |+1 suit la loi Ord.
Preuve Par récurrence sur n = |τ |. Si τ est vide, l’insertion d’une clé x dans τ
conduit, de manière évidente, à un arbre de loi Ord. Supposons n ≥ 1. Soit X
l’ensemble des clés de τ , et soit τ l’arbre obtenu par insertion randomisée de x
dans τ ; l’ensemble des clés de τ est alors X ∪ {x}.
6 Arbres binaires de recherche
de même loi Ord ; inversement, le lemme 6.40 montre que la fusion de deux arbres
de loi Ord fournit un arbre sous cette même loi. Les deux propositions 6.39 et 6.41
établissent quant à elles que les arbres obtenus par l’application des opérations
d’insertion et de suppression randomisées à un arbre binaire de recherche, toujours
sous la loi Ord, suivent eux aussi cette loi.
Lemme 6.38 Soient τ un abr de taille n de loi Ord contenant des clés x 1 , . . . , x n
dont le réordonnement est donné par la permutation σ :
x σ (1) < x σ (2) < · · · < x σ (n) .
Soit x une clé non présente dans τ . Soit p ∈ {1, . . . , n + 1}. Supposons que le rang
de x vaille p, autrement dit :
x ∈]x σ (p−1) , x σ (p) [.
Alors, les deux arbres τ
indépendants et de loi Ord respectivement de taille p − 1 et n + 1 − p.
Preuve La clé x sépare les données x i , i = 1, . . . , n en deux paquets : les p − 1
données inférieures à x, disons
X
X >x = {x σ (j) , j = p, . . . , n + 1},
avec les conventions habituelles : si p = 1, le premier ensemble est vide et si
p = n + 1, le second ensemble est vide.
L’algorithme de coupure en A.2.4 construit τ
Comme τ est de loi Ord, les x i , i = 1, . . . , n sont i.i.d. et donc les arbres τ
loi uniforme sur S n . Et par conséquent (c’est là l’argument central), σ restreinte à
{1, . . . , p − 1} est uniforme sur S p−1 , respectivement σ restreinte à {p, . . . , n + 1}
est uniforme sur S n+1−p . Donc τ
p − 1 et n + 1 − p.
Proposition 6.39 Soient τ un abr de loi Ord et x une clé non présente dans τ . Alors
l’arbre binaire de recherche obtenu par insertion randomisée de x dans τ avec pour
probabilité p(τ ) =
1
|τ |+1 suit la loi Ord.
Preuve Par récurrence sur n = |τ |. Si τ est vide, l’insertion d’une clé x dans τ
conduit, de manière évidente, à un arbre de loi Ord. Supposons n ≥ 1. Soit X
l’ensemble des clés de τ , et soit τ l’arbre obtenu par insertion randomisée de x
dans τ ; l’ensemble des clés de τ est alors X ∪ {x}.