6.5 Arbres binaires de recherche randomisés
263
6.5.2 Loi des arbres binaires de recherche randomisés
Nous supposons dans cette section que les clés insérées sont toutes distinctes. Nous
revenons tout d’abord sur une propriété essentielle d’un arbre binaire de recherche
aléatoire sous le modèle des permutations uniformes ; cf. la proposition 6.1 « diviser
pour régner ». Sous le modèle Ord et pour des arbres de taille n ≥ 1, le rang de
la clé à la racine vaut j , pour j ∈ {1, . . . , n}, avec probabilité 1/n, et les sousarbres gauche et droit sont eux-mêmes des arbres binaires de recherche aléatoires
indépendants et de loi Ord. Nous utilisons aussi la propriété suivante, qui en est
la réciproque et que nous donnons lorsque les clés d’un arbre τ sont les entiers
1, . . . , |τ | : nous pouvons toujours nous ramener à ce cas par marquage canonique
lorsqu’il n’y a pas de clés égales, ce qui est bien le cas dans le modèle des
permutations uniformes.
Proposition 6.36 Soit un arbre binaire de recherche aléatoire τ de taille n, marqué
par les entiers {1, . . . , n}. Supposons que la loi de τ soit telle que
– pour tout j ∈ {1, . . . , n}, la probabilité que la marque de la racine soit égale à j
vaut
1
n ;
– sachant la marque à la racine, les sous-arbres gauche et droit de τ sont
indépendants et suivent la loi Ord.
Alors la loi de τ est la loi Ord.
Nous renvoyons à l’exercice 6.8 pour des indications sur la manière d’obtenir cette
proposition.
Il est ainsi possible d’exprimer de trois façons différentes que τ est un abr de
taille n sous la loi Ord. Appelons x 1 , . . . , x n les clés dans τ .
1. Les clés x 1 , . . . , x n sont i.i.d.
2. Le réordonnement σ de x 1 , . . . , x n est de loi uniforme sur S n .
3. Comme dans la proposition 6.36 : Soit j ∈ {1, . . . , n}. La racine contient la clé x j
avec probabilité
1
n et sachant x j , les sous-arbres gauche et droit sont indépendants
et de loi Ord.
Les trois caractérisations sont équivalentes et entraînent la propriété « diviser
pour régner » de la proposition 6.1.
Nous pouvons maintenant démontrer le résultat que nous avons annoncé à la fin
de la section 6.5.1, à savoir que, pour un choix judicieux des probabilités p(τ ) et
q(τ ), nous retrouvons la loi Ord sur les arbres binaires de recherche randomisés.
Théorème 6.37 Pour des probabilités p(τ ) =
1
|τ |+1 et q(τ ) =
|τ (g) |
|τ |−1 , les formes
d’arbres binaires de recherche randomisés sont de même loi que les formes d’arbres
binaires de recherche sous la loi Ord, c’est-à-dire les arbres bourgeonnants.
Preuve Ce théorème est la conséquence directe d’une série de résultats intermédiaires : le lemme 6.38 montre que l’opération de coupure, appliquée à un arbre binaire
de recherche de loi Ord, fournit deux arbres binaires de recherche indépendants et
263
6.5.2 Loi des arbres binaires de recherche randomisés
Nous supposons dans cette section que les clés insérées sont toutes distinctes. Nous
revenons tout d’abord sur une propriété essentielle d’un arbre binaire de recherche
aléatoire sous le modèle des permutations uniformes ; cf. la proposition 6.1 « diviser
pour régner ». Sous le modèle Ord et pour des arbres de taille n ≥ 1, le rang de
la clé à la racine vaut j , pour j ∈ {1, . . . , n}, avec probabilité 1/n, et les sousarbres gauche et droit sont eux-mêmes des arbres binaires de recherche aléatoires
indépendants et de loi Ord. Nous utilisons aussi la propriété suivante, qui en est
la réciproque et que nous donnons lorsque les clés d’un arbre τ sont les entiers
1, . . . , |τ | : nous pouvons toujours nous ramener à ce cas par marquage canonique
lorsqu’il n’y a pas de clés égales, ce qui est bien le cas dans le modèle des
permutations uniformes.
Proposition 6.36 Soit un arbre binaire de recherche aléatoire τ de taille n, marqué
par les entiers {1, . . . , n}. Supposons que la loi de τ soit telle que
– pour tout j ∈ {1, . . . , n}, la probabilité que la marque de la racine soit égale à j
vaut
1
n ;
– sachant la marque à la racine, les sous-arbres gauche et droit de τ sont
indépendants et suivent la loi Ord.
Alors la loi de τ est la loi Ord.
Nous renvoyons à l’exercice 6.8 pour des indications sur la manière d’obtenir cette
proposition.
Il est ainsi possible d’exprimer de trois façons différentes que τ est un abr de
taille n sous la loi Ord. Appelons x 1 , . . . , x n les clés dans τ .
1. Les clés x 1 , . . . , x n sont i.i.d.
2. Le réordonnement σ de x 1 , . . . , x n est de loi uniforme sur S n .
3. Comme dans la proposition 6.36 : Soit j ∈ {1, . . . , n}. La racine contient la clé x j
avec probabilité
1
n et sachant x j , les sous-arbres gauche et droit sont indépendants
et de loi Ord.
Les trois caractérisations sont équivalentes et entraînent la propriété « diviser
pour régner » de la proposition 6.1.
Nous pouvons maintenant démontrer le résultat que nous avons annoncé à la fin
de la section 6.5.1, à savoir que, pour un choix judicieux des probabilités p(τ ) et
q(τ ), nous retrouvons la loi Ord sur les arbres binaires de recherche randomisés.
Théorème 6.37 Pour des probabilités p(τ ) =
1
|τ |+1 et q(τ ) =
|τ (g) |
|τ |−1 , les formes
d’arbres binaires de recherche randomisés sont de même loi que les formes d’arbres
binaires de recherche sous la loi Ord, c’est-à-dire les arbres bourgeonnants.
Preuve Ce théorème est la conséquence directe d’une série de résultats intermédiaires : le lemme 6.38 montre que l’opération de coupure, appliquée à un arbre binaire
de recherche de loi Ord, fournit deux arbres binaires de recherche indépendants et