4.4 Arbres équilibrés
161
Comme la série
≥0
1
3 log
1 +
1
a
est de même nature que
1
3
1
a
et comme a > 2 3 , le produit infini
1 +
1
a
1
3
est convergent (cf.
section B.5.2) et la suite (v h ) converge vers
κ := v 0
1 +
1
a
1
3
.
Une excellente approximation de la valeur numérique de κ s’obtient aisément en
calculant les premières valeurs des a : la convergence est extrêmement rapide ; les
quatre premiers termes suffisent à avoir une valeur à 10 −9 près, et nous trouvons
que κ = 2,30992632 . . . En outre, en utilisant a > 2 3 et le fait qu’au voisinage de
0, log(1 + x) < x, il vient
κ
v h
=
1 +
1
a
1
3 = 1 + O
1
3 h 2 3 h
,
et donc v h = κ
1 + O
1
3 h 2 3 h
, ce qui montre que a h = v 3 h
h
=
κ 3 h
1 + O
1
2 3 h
. D’où la proposition suivante.
Proposition 4.20 Le nombre a h d’arbres 2–3 de hauteur h satisfait la relation de
récurrence a h+1 = a 2
h + a 3
h avec a 0 = 2. Asymptotiquement il vaut
a h = κ
3 h
1 + O
1
2 3 h
avec κ = 2,30992632 . . .
Tournons-nous maintenant vers l’étude des paramètres Taille et Nombre de clés
(la taille est ici le nombre total de nœuds, internes et feuilles). Rappelons que
nous sommes sous un modèle de Catalan : tous les arbres de hauteur h fixée sont
équiprobables. Nous considérons donc la fonction génératrice du nombre a n,q,h
d’arbres 2–3 à n clés, q nœuds, et de hauteur h fixée, où x marque les clés et y
les nœuds :
A h (x, y) :=
n,q
a n,q,h x
n y
q .
La condition initiale est A 0 (x, y) = (x + x 2 ) y et, en considérant comme
précédemment le nombre d’enfants de la racine, nous établissons facilement la
relation de récurrence
A h+1 (x, y) = xy A
2
h (x, y) + x
2 y A
3
h (x, y)
(h ≥ 0).
161
Comme la série
≥0
1
3 log
1 +
1
a
est de même nature que
1
3
1
a
et comme a > 2 3 , le produit infini
1 +
1
a
1
3
est convergent (cf.
section B.5.2) et la suite (v h ) converge vers
κ := v 0
1 +
1
a
1
3
.
Une excellente approximation de la valeur numérique de κ s’obtient aisément en
calculant les premières valeurs des a : la convergence est extrêmement rapide ; les
quatre premiers termes suffisent à avoir une valeur à 10 −9 près, et nous trouvons
que κ = 2,30992632 . . . En outre, en utilisant a > 2 3 et le fait qu’au voisinage de
0, log(1 + x) < x, il vient
κ
v h
=
1 +
1
a
1
3 = 1 + O
1
3 h 2 3 h
,
et donc v h = κ
1 + O
1
3 h 2 3 h
, ce qui montre que a h = v 3 h
h
=
κ 3 h
1 + O
1
2 3 h
. D’où la proposition suivante.
Proposition 4.20 Le nombre a h d’arbres 2–3 de hauteur h satisfait la relation de
récurrence a h+1 = a 2
h + a 3
h avec a 0 = 2. Asymptotiquement il vaut
a h = κ
3 h
1 + O
1
2 3 h
avec κ = 2,30992632 . . .
Tournons-nous maintenant vers l’étude des paramètres Taille et Nombre de clés
(la taille est ici le nombre total de nœuds, internes et feuilles). Rappelons que
nous sommes sous un modèle de Catalan : tous les arbres de hauteur h fixée sont
équiprobables. Nous considérons donc la fonction génératrice du nombre a n,q,h
d’arbres 2–3 à n clés, q nœuds, et de hauteur h fixée, où x marque les clés et y
les nœuds :
A h (x, y) :=
n,q
a n,q,h x
n y
q .
La condition initiale est A 0 (x, y) = (x + x 2 ) y et, en considérant comme
précédemment le nombre d’enfants de la racine, nous établissons facilement la
relation de récurrence
A h+1 (x, y) = xy A
2
h (x, y) + x
2 y A
3
h (x, y)
(h ≥ 0).