50
2 Aléa sur les arbres
Proposition 2.8 Soient n variables aléatoires x 1 , . . . , x n i.i.d. de loi commune F
continue sur l’intervalle [0, 1]. Soit τ
(F )
n
l’arbre binaire de recherche associé aux n
premières clés x 1 , . . . , x n par la construction détaillée en section 1.2.5. Alors,
(i) La suite (τ
(F )
n , n ≥ 1) est une chaîne de Markov d’arbres marqués.
(ii) La forme de l’abr τ
(F )
n
ne dépend pas de la loi F et sans perte de généralité
nous pouvons supposer que F est la loi uniforme sur [0, 1] pour l’étude de
tous les paramètres qui ne dépendent que de la forme de cet arbre.
(iii) La loi de la forme de l’abr τ
(F )
n
est la même que celle de l’abr construit en
insérant successivement n entiers d’une permutation de loi uniforme sur S n .
Preuve
(i) L’arbre aléatoire τ
(F )
n est à valeurs dans l’ensemble des arbres binaires complets
marqués, puisque chaque nœud interne contient une clé qui est un réel de
l’intervalle [0, 1]. Le caractère markovien vient du fait que τ
(F )
n
ne dépend du
passé que par la valeur de τ
(F )
n−1 (cf. l’annexe C.5).
(ii) Sous le modèle des permutations uniformes, la forme de l’abr τ
(F )
n
construit
avec les n premières clés ne dépend que de l’ordre relatif des clés. Autrement
dit, elle ne dépend que du réordonnement, de loi uniforme sur S n , ce qui prouve
(iii).
Ce qui précède permet ainsi, partant de n’importe quelle loi continue sur l’intervalle
[0, 1], de se ramener à la loi Ord définie ci-après (dont le nom est justifié par la
proposition 2.4).
Définition 2.9 Nous appelons Ord la loi sur les arbres binaires de recherche sous
le modèle des permutations uniformes défini dans la proposition 2.4, c’est-à-dire
lorsque les clés ajoutées dans l’arbre par insertion aux feuilles sont des variables
aléatoires i.i.d. de même loi uniforme sur l’intervalle [0, 1].
Remarque 2.10 Tout ce qui suit concerne des arbres binaires de recherche aléatoires
sous le modèle des permutations uniformes, c’est-à-dire sous la loi Ord. Nous
abrégerons souvent cela en « arbre binaire de recherche aléatoire », voire en « arbre
binaire de recherche » ou encore « abr », l’aléa étant alors implicite, mais bien
présent !
Comment pousse un arbre binaire de recherche aléatoire ?
La figure 2.6 reprend l’abr de la figure 1.24 en insérant une nouvelle donnée. Les
possibilités d’insertion sont figurées par des .
Précisons comment se fait l’insertion de la n + 1-ième clé x n+1 dans l’arbre à n
nœuds internes τ n . Pour calculer la probabilité que la n + 1-ième clé x n+1 tombe
dans l’intervalle ]x σ n (j ) , x σ n (j +1) [, soit encore la probabilité que x n+1 tombe sur la
2 Aléa sur les arbres
Proposition 2.8 Soient n variables aléatoires x 1 , . . . , x n i.i.d. de loi commune F
continue sur l’intervalle [0, 1]. Soit τ
(F )
n
l’arbre binaire de recherche associé aux n
premières clés x 1 , . . . , x n par la construction détaillée en section 1.2.5. Alors,
(i) La suite (τ
(F )
n , n ≥ 1) est une chaîne de Markov d’arbres marqués.
(ii) La forme de l’abr τ
(F )
n
ne dépend pas de la loi F et sans perte de généralité
nous pouvons supposer que F est la loi uniforme sur [0, 1] pour l’étude de
tous les paramètres qui ne dépendent que de la forme de cet arbre.
(iii) La loi de la forme de l’abr τ
(F )
n
est la même que celle de l’abr construit en
insérant successivement n entiers d’une permutation de loi uniforme sur S n .
Preuve
(i) L’arbre aléatoire τ
(F )
n est à valeurs dans l’ensemble des arbres binaires complets
marqués, puisque chaque nœud interne contient une clé qui est un réel de
l’intervalle [0, 1]. Le caractère markovien vient du fait que τ
(F )
n
ne dépend du
passé que par la valeur de τ
(F )
n−1 (cf. l’annexe C.5).
(ii) Sous le modèle des permutations uniformes, la forme de l’abr τ
(F )
n
construit
avec les n premières clés ne dépend que de l’ordre relatif des clés. Autrement
dit, elle ne dépend que du réordonnement, de loi uniforme sur S n , ce qui prouve
(iii).
Ce qui précède permet ainsi, partant de n’importe quelle loi continue sur l’intervalle
[0, 1], de se ramener à la loi Ord définie ci-après (dont le nom est justifié par la
proposition 2.4).
Définition 2.9 Nous appelons Ord la loi sur les arbres binaires de recherche sous
le modèle des permutations uniformes défini dans la proposition 2.4, c’est-à-dire
lorsque les clés ajoutées dans l’arbre par insertion aux feuilles sont des variables
aléatoires i.i.d. de même loi uniforme sur l’intervalle [0, 1].
Remarque 2.10 Tout ce qui suit concerne des arbres binaires de recherche aléatoires
sous le modèle des permutations uniformes, c’est-à-dire sous la loi Ord. Nous
abrégerons souvent cela en « arbre binaire de recherche aléatoire », voire en « arbre
binaire de recherche » ou encore « abr », l’aléa étant alors implicite, mais bien
présent !
Comment pousse un arbre binaire de recherche aléatoire ?
La figure 2.6 reprend l’abr de la figure 1.24 en insérant une nouvelle donnée. Les
possibilités d’insertion sont figurées par des .
Précisons comment se fait l’insertion de la n + 1-ième clé x n+1 dans l’arbre à n
nœuds internes τ n . Pour calculer la probabilité que la n + 1-ième clé x n+1 tombe
dans l’intervalle ]x σ n (j ) , x σ n (j +1) [, soit encore la probabilité que x n+1 tombe sur la