4.4 Arbres équilibrés
167
et comme c ≥ (m + 1) (2m+1) , le produit infini
1 +
1
c
+ · · · +
1
c
m
1
(2m+1)
est convergent (cf. section B.5.2) et la suite (v h ) converge vers une limite finie, que
nous notons κ m :
κ m = v 0
1 +
1
c
+ · · · +
1
c
m
1
(2m+1)
.
Nous en déduisons comme pour les arbres 2–3 que, pour h suffisamment grand,
v h = κ m
1 + O
1
(2m + 1) h (m + 1) (2m+1) h
et finalement que
c h = ν
(2m+1) h
h
= κ
(2m+1) h
m
1 + O
1
(m + 1) (2m+1) h
.
Comme pour la constante κ de la proposition 4.20, il est possible d’obtenir une
très bonne approximation de κ m pour toute valeur numérique de m en prenant
juste quelques termes du produit infini, dont la convergence est très rapide. Nous
terminons en revenant à b h , que nous écrivons sous la forme
b h = c
2m+1
h−1
1 + O
1
c h−1
,
et nous obtenons la proposition suivante.
Proposition 4.27 Le nombre d’arbres-B optimistes de paramètre m, de hauteur h,
vaut asymptotiquement
b h = κ
(2m+1) h
m
1 + O
1
(m + 1) (2m+1) h
,
où κ m est une constante, dépendant uniquement du paramètre m.
La figure 4.15 donne les premières valeurs de la constante κ m ; nous pouvons
constater qu’elle est légèrement supérieure à m + 1.
L’étude du comportement dynamique des arbres-B de recherche n’est pas du
ressort de ce chapitre, qui s’intéresse uniquement aux arbres sous le modèle de
Catalan. Nous renvoyons cette étude, qui utilise une description des nœuds de l’arbre
(en fait, seulement des feuilles) par urne de Pólya et les techniques d’analyse de ces
urnes, au chapitre 9.