360
8 Arbres m-aires et quadrants
8.2.5 Profondeur d’insertion d’une clé : cas d = 2
Soit d(X, τ ) (resp. d(X n+1 , τ n )) la variable aléatoire profondeur d’insertion de
la clé X dans l’arbre τ (resp. profondeur d’insertion de la n + 1-ième clé dans
un arbre aléatoire de taille n). Comme les clés sont i.i.d., nous considérons dans
cette section d(X, τ n ). Par convention, la racine est à profondeur 0. Des méthodes
combinatoires simples permettent de traiter le cas d = 2. Devroye et Laforest [61]
ont obtenu de cette manière l’espérance et la variance de d(X, τ n ), et montré la
convergence en probabilité de d(X, τ n )/ log n quand n tend vers +∞. Ces méthodes
peuvent s’étendre à d ≥ 3, pour montrer que d(X, τ n )/ log n → 2/d ; le calcul de
E[d(X, τ n )] se trouve dans l’article de Flajolet et al. [99].
Dans cette partie, nous nous limitons au cas d = 2 et à une approche combinatoire tirée de Devroye et Laforest [61], basée sur le calcul explicite des probabilités
de partage, i.e., des lois des tailles des différents sous-arbres que nous avons
présentées en section 8.2.3. Nous présenterons ultérieurement (cf. Section 8.2.7) des
techniques différentes dues à Flajolet et Lafforgue [86], qui permettent de retrouver
la moyenne et la variance asymptotiques pour toute dimension d, et en outre de
montrer que le coût suit asymptotiquement une loi normale.
Probabilité d’insertion à profondeur Nous allons d’abord exprimer la probabilité P(d(X, τ n ) = ) de manière récursive, en fonction de la loi de la profondeur
d’insertion dans un arbre de taille plus petite, afin d’obtenir la relation (8.12) cidessous. En considérant les différents sous-arbres de τ n , nous obtenons 6 :
P(d(X, τ n ) = =
3
j =0
P
d(X, τ n ) = , X ∈ τ
(j )
n
.
Soit j ∈ {0, 1, 2, 3} fixé. En considérant les différentes tailles possibles du sousarbre τ
(j )
n , nous avons
P
d(X, τ n ) = , X ∈ τ
(j )
n
=
n−1
i=0
P
d(X, τ n ) = , X ∈ τ
(j )
n , |τ
(j )
n | = i
.
Quand la clé X est insérée à profondeur dans l’arbre global, elle est insérée à
profondeur − 1 dans le sous-arbre adéquat, donc
P
d(X, τ n ) = , X ∈ τ
(j )
n
=
n−1
i=0
P
d(X, τ
(j )
n ) = − 1, X ∈ τ
(j )
n , |τ
(j )
n | = i
.
6 Rappelons que l’écriture P(A, B) pour deux événements A et B, signifie P(A ∧ B) ou encore
P(A ∩ B).
8 Arbres m-aires et quadrants
8.2.5 Profondeur d’insertion d’une clé : cas d = 2
Soit d(X, τ ) (resp. d(X n+1 , τ n )) la variable aléatoire profondeur d’insertion de
la clé X dans l’arbre τ (resp. profondeur d’insertion de la n + 1-ième clé dans
un arbre aléatoire de taille n). Comme les clés sont i.i.d., nous considérons dans
cette section d(X, τ n ). Par convention, la racine est à profondeur 0. Des méthodes
combinatoires simples permettent de traiter le cas d = 2. Devroye et Laforest [61]
ont obtenu de cette manière l’espérance et la variance de d(X, τ n ), et montré la
convergence en probabilité de d(X, τ n )/ log n quand n tend vers +∞. Ces méthodes
peuvent s’étendre à d ≥ 3, pour montrer que d(X, τ n )/ log n → 2/d ; le calcul de
E[d(X, τ n )] se trouve dans l’article de Flajolet et al. [99].
Dans cette partie, nous nous limitons au cas d = 2 et à une approche combinatoire tirée de Devroye et Laforest [61], basée sur le calcul explicite des probabilités
de partage, i.e., des lois des tailles des différents sous-arbres que nous avons
présentées en section 8.2.3. Nous présenterons ultérieurement (cf. Section 8.2.7) des
techniques différentes dues à Flajolet et Lafforgue [86], qui permettent de retrouver
la moyenne et la variance asymptotiques pour toute dimension d, et en outre de
montrer que le coût suit asymptotiquement une loi normale.
Probabilité d’insertion à profondeur Nous allons d’abord exprimer la probabilité P(d(X, τ n ) = ) de manière récursive, en fonction de la loi de la profondeur
d’insertion dans un arbre de taille plus petite, afin d’obtenir la relation (8.12) cidessous. En considérant les différents sous-arbres de τ n , nous obtenons 6 :
P(d(X, τ n ) = =
3
j =0
P
d(X, τ n ) = , X ∈ τ
(j )
n
.
Soit j ∈ {0, 1, 2, 3} fixé. En considérant les différentes tailles possibles du sousarbre τ
(j )
n , nous avons
P
d(X, τ n ) = , X ∈ τ
(j )
n
=
n−1
i=0
P
d(X, τ n ) = , X ∈ τ
(j )
n , |τ
(j )
n | = i
.
Quand la clé X est insérée à profondeur dans l’arbre global, elle est insérée à
profondeur − 1 dans le sous-arbre adéquat, donc
P
d(X, τ n ) = , X ∈ τ
(j )
n
=
n−1
i=0
P
d(X, τ
(j )
n ) = − 1, X ∈ τ
(j )
n , |τ
(j )
n | = i
.
6 Rappelons que l’écriture P(A, B) pour deux événements A et B, signifie P(A ∧ B) ou encore
P(A ∩ B).