260
6 Arbres binaires de recherche
car s n+1 − s n suit une loi de Bernoulli de paramètre
1
n+1 . Finalement,
Q z (s n+1 − s n = 0) =
n
n + 1
n + 1
n + 2z
1
γ n (2z − 1)
E 1
2
(2z)
s n
=
n
n + 2z
,
ce qui montre que l’arbre pousse de la même façon sous P z et sous Q z . Donc,
pour tout n ∈ N
P z = E n (z) P 1
2
sur F n .
6.5 Arbres binaires de recherche randomisés
Nous avons supposé dans les sections précédentes que les arbres binaires de
recherche étaient construits par insertions successives aux feuilles, de clés tirées
indépendamment et avec la même loi, c’est-à-dire i.i.d. Il s’agit d’une hypothèse
forte, qui n’est plus vérifiée dès lors que les clés insérées ne sont plus indépendantes
entre elles mais corrélées (par exemple des clés peuvent être égales), ou lorsque
des clés peuvent être supprimées. Un moyen efficace de retrouver cette loi, et les
bonnes performances qui en découlent en terme de hauteur moyenne ou de longueur
de cheminement moyenne, est donné par la randomisation des arbres binaires de
recherche, initialement mise au point par Aragon et Seidel [8, 9]. Les arbres qu’ils
construisent, auxquels ils donnent le nom de treaps, contiennent des clés auxquelles
sont associées des priorités ; l’arbre est un arbre binaire de recherche suivant les
clés, et un tas suivant les priorités. Lorsque les priorités sont des variables aléatoires
tirées suivant une loi ad-hoc (dépendant de poids associés aux clés), le temps moyen
d’une opération de recherche ou de mise à jour est bien logarithmique.
La randomisation a été reprise et simplifiée par Martinez et Roura [179], qui se
sont débarrassés des priorités et poids. Nous présentons ci-dessous cette dernière
version, qui permet donc de construire des arbres binaires de recherche suivant la
loi Ord quelles que soient les corrélations des clés et les opérations autorisées.
6.5.1 Randomisation d’un arbre binaire de recherche
Supposons dans un premier temps que la seule opération de mise à jour permise sur
l’arbre soit l’insertion d’une nouvelle clé, mais sous des hypothèses probabilistes
qui n’assurent plus d’être sous la loi Ord. Par exemple, il peut ne pas y avoir
indépendance des clés, mais au contraire localité : la loi de la n-ième clé est
concentrée autour de la valeur de la (n − 1)-ième clé insérée. Dans un tel cas
l’arbre binaire de recherche obtenu par insertion aux feuilles de n clés semble
intuitivement avoir peu de chances d’avoir une hauteur d’ordre log n. Pour conserver
6 Arbres binaires de recherche
car s n+1 − s n suit une loi de Bernoulli de paramètre
1
n+1 . Finalement,
Q z (s n+1 − s n = 0) =
n
n + 1
n + 1
n + 2z
1
γ n (2z − 1)
E 1
2
(2z)
s n
=
n
n + 2z
,
ce qui montre que l’arbre pousse de la même façon sous P z et sous Q z . Donc,
pour tout n ∈ N
P z = E n (z) P 1
2
sur F n .
6.5 Arbres binaires de recherche randomisés
Nous avons supposé dans les sections précédentes que les arbres binaires de
recherche étaient construits par insertions successives aux feuilles, de clés tirées
indépendamment et avec la même loi, c’est-à-dire i.i.d. Il s’agit d’une hypothèse
forte, qui n’est plus vérifiée dès lors que les clés insérées ne sont plus indépendantes
entre elles mais corrélées (par exemple des clés peuvent être égales), ou lorsque
des clés peuvent être supprimées. Un moyen efficace de retrouver cette loi, et les
bonnes performances qui en découlent en terme de hauteur moyenne ou de longueur
de cheminement moyenne, est donné par la randomisation des arbres binaires de
recherche, initialement mise au point par Aragon et Seidel [8, 9]. Les arbres qu’ils
construisent, auxquels ils donnent le nom de treaps, contiennent des clés auxquelles
sont associées des priorités ; l’arbre est un arbre binaire de recherche suivant les
clés, et un tas suivant les priorités. Lorsque les priorités sont des variables aléatoires
tirées suivant une loi ad-hoc (dépendant de poids associés aux clés), le temps moyen
d’une opération de recherche ou de mise à jour est bien logarithmique.
La randomisation a été reprise et simplifiée par Martinez et Roura [179], qui se
sont débarrassés des priorités et poids. Nous présentons ci-dessous cette dernière
version, qui permet donc de construire des arbres binaires de recherche suivant la
loi Ord quelles que soient les corrélations des clés et les opérations autorisées.
6.5.1 Randomisation d’un arbre binaire de recherche
Supposons dans un premier temps que la seule opération de mise à jour permise sur
l’arbre soit l’insertion d’une nouvelle clé, mais sous des hypothèses probabilistes
qui n’assurent plus d’être sous la loi Ord. Par exemple, il peut ne pas y avoir
indépendance des clés, mais au contraire localité : la loi de la n-ième clé est
concentrée autour de la valeur de la (n − 1)-ième clé insérée. Dans un tel cas
l’arbre binaire de recherche obtenu par insertion aux feuilles de n clés semble
intuitivement avoir peu de chances d’avoir une hauteur d’ordre log n. Pour conserver