6.1 Analyses de la longueur de cheminement et du profil
223
Or
F (x, 1) =
n,k≥0
P(lci(τ n ) = k)x
n
=
n≥0
⎛
⎝
k≥0
P(lci(τ n ) = k)
⎞
⎠ x
n
=
n≥0
x
n
=
1
1 − x
,
ce qui montre que B est solution de l’équation différentielle
B
(x) =
2x
(1 − x) 3 +
2B(x)
1 − x
.
(6.3)
Cette équation se résout sans problème, en ajoutant les conditions initiales lci(τ 0 ) =
0 et lci(τ 1 ) = 0 :
B(x) =
−2
(1 − x) 2 (x + log (1 − x)) .
(6.4)
Pour obtenir E(lci(τ n )), il suffit alors d’extraire le coefficient de x n dans B(x). Nous
pouvons par exemple écrire B(x) comme le produit de deux séries :
B(x) =
2
(1 − x) 2
x 2
2
+
x 3
3
+ · · · +
x n
n
+ . . .
= 2x
2
⎛
⎝
j ≥0
(j + 1) x
j
⎞
⎠
⎛
⎝
k≥0
1
k + 2
x
k
⎞
⎠
de sorte que le coefficient de x n+2 vaut 2
n
k=0
n − k + 1
k + 2
. Finalement,
E(lci(τ n+2 )) = 2
n
k=0
n − k + 1
k + 2
= 2(n + 1)H n − 4n = 2(n + 1)(H n+1 − 1) − 2n,
ce qui redonne bien le résultat du théorème 6.2. Remarquons que le résultat
asymptotique peut être obtenu directement à partir de l’expression de B(x) donnée
par l’équation (6.4), par analyse de singularité.
La même méthode fournit pour la variance le théorème suivant (voir Sedgewick
et Flajolet [232, page 142]).
Théorème 6.3 La variance de la longueur de cheminement d’un arbre binaire de
recherche de taille n, sous la loi Ord, vaut asymptotiquement lorsque n → +∞
Var (lci(τ n )) =
7 −
2π 2
3
n
2
+ O(n log n).
223
Or
F (x, 1) =
n,k≥0
P(lci(τ n ) = k)x
n
=
n≥0
⎛
⎝
k≥0
P(lci(τ n ) = k)
⎞
⎠ x
n
=
n≥0
x
n
=
1
1 − x
,
ce qui montre que B est solution de l’équation différentielle
B
(x) =
2x
(1 − x) 3 +
2B(x)
1 − x
.
(6.3)
Cette équation se résout sans problème, en ajoutant les conditions initiales lci(τ 0 ) =
0 et lci(τ 1 ) = 0 :
B(x) =
−2
(1 − x) 2 (x + log (1 − x)) .
(6.4)
Pour obtenir E(lci(τ n )), il suffit alors d’extraire le coefficient de x n dans B(x). Nous
pouvons par exemple écrire B(x) comme le produit de deux séries :
B(x) =
2
(1 − x) 2
x 2
2
+
x 3
3
+ · · · +
x n
n
+ . . .
= 2x
2
⎛
⎝
j ≥0
(j + 1) x
j
⎞
⎠
⎛
⎝
k≥0
1
k + 2
x
k
⎞
⎠
de sorte que le coefficient de x n+2 vaut 2
n
k=0
n − k + 1
k + 2
. Finalement,
E(lci(τ n+2 )) = 2
n
k=0
n − k + 1
k + 2
= 2(n + 1)H n − 4n = 2(n + 1)(H n+1 − 1) − 2n,
ce qui redonne bien le résultat du théorème 6.2. Remarquons que le résultat
asymptotique peut être obtenu directement à partir de l’expression de B(x) donnée
par l’équation (6.4), par analyse de singularité.
La même méthode fournit pour la variance le théorème suivant (voir Sedgewick
et Flajolet [232, page 142]).
Théorème 6.3 La variance de la longueur de cheminement d’un arbre binaire de
recherche de taille n, sous la loi Ord, vaut asymptotiquement lorsque n → +∞
Var (lci(τ n )) =
7 −
2π 2
3
n
2
+ O(n log n).