162
4 Approche combinatoire
Nous pouvons retrouver simplement le nombre d’arbres de hauteur h :
a h = A h (1, 1).
Remarque 4.21 L’équivalent asymptotique de a h que nous avons donné dans la
proposition 4.20 peut aussi s’obtenir à partir d’un résultat de Flajolet et Odlyzko [89]
sur les coefficients de polynômes obtenus par itération : si une suite (y h (z)) h≥0
vérifie une relation de récurrence y h+1 (z) = P (y h (z), z), où P (y, z) est un
polynôme de degré d en y, alors sous certaines conditions il existe une fonction α(z)
telle que y h (z) ∼ g(z) α(z) d h quand h → +∞ (c’est la formule (1.11) et le lemme
2.5 de [89]). Il suffit ensuite de prendre z = 1 pour retrouver la proposition 4.20.
Le nombre cumulé de clés dans tous les arbres de hauteur h est
∂A h
∂x (1, 1), ce
qui donne immédiatement une expression pour la moyenne du nombre N(τ ) de clés
dans un arbre 2–3 τ de hauteur h :
E[N(τ )] =
∂A h
∂x (1, 1)
A h (1, 1)
.
Nous obtenons de même la moyenne de la taille |τ | de l’arbre par
E[|τ |] =
∂A h
∂y (1, 1)
A h (1, 1)
.
L’étude asymptotique de ces deux espérances lorsque h croît est présentée dans
l’article de Reingold [220]. Elle fait appel à des techniques relativement simples
d’analyse réelle (encadrements et bornes sur des séries ; des indications de preuve
sont données dans le problème 4.20 de la Section 4.6). Elle conduit à la proposition
suivante.
Proposition 4.22 Soit τ un arbre 2–3 de hauteur h choisi uniformément parmi tous
les arbres de cette hauteur ; alors le nombre N(τ ) de clés présentes et la taille |τ |
vérifient, lorsque h → +∞ :
E[N(τ )] ∼ 0,72162 . . . 3
h
;
E[|τ |] ∼ 0,48061 . . . 3
h .
De plus, le nombre moyen de clés par nœud tend asymptotiquement vers 1,50146
lorsque h → +∞.
4 Approche combinatoire
Nous pouvons retrouver simplement le nombre d’arbres de hauteur h :
a h = A h (1, 1).
Remarque 4.21 L’équivalent asymptotique de a h que nous avons donné dans la
proposition 4.20 peut aussi s’obtenir à partir d’un résultat de Flajolet et Odlyzko [89]
sur les coefficients de polynômes obtenus par itération : si une suite (y h (z)) h≥0
vérifie une relation de récurrence y h+1 (z) = P (y h (z), z), où P (y, z) est un
polynôme de degré d en y, alors sous certaines conditions il existe une fonction α(z)
telle que y h (z) ∼ g(z) α(z) d h quand h → +∞ (c’est la formule (1.11) et le lemme
2.5 de [89]). Il suffit ensuite de prendre z = 1 pour retrouver la proposition 4.20.
Le nombre cumulé de clés dans tous les arbres de hauteur h est
∂A h
∂x (1, 1), ce
qui donne immédiatement une expression pour la moyenne du nombre N(τ ) de clés
dans un arbre 2–3 τ de hauteur h :
E[N(τ )] =
∂A h
∂x (1, 1)
A h (1, 1)
.
Nous obtenons de même la moyenne de la taille |τ | de l’arbre par
E[|τ |] =
∂A h
∂y (1, 1)
A h (1, 1)
.
L’étude asymptotique de ces deux espérances lorsque h croît est présentée dans
l’article de Reingold [220]. Elle fait appel à des techniques relativement simples
d’analyse réelle (encadrements et bornes sur des séries ; des indications de preuve
sont données dans le problème 4.20 de la Section 4.6). Elle conduit à la proposition
suivante.
Proposition 4.22 Soit τ un arbre 2–3 de hauteur h choisi uniformément parmi tous
les arbres de cette hauteur ; alors le nombre N(τ ) de clés présentes et la taille |τ |
vérifient, lorsque h → +∞ :
E[N(τ )] ∼ 0,72162 . . . 3
h
;
E[|τ |] ∼ 0,48061 . . . 3
h .
De plus, le nombre moyen de clés par nœud tend asymptotiquement vers 1,50146
lorsque h → +∞.