4.4 Arbres équilibrés
163
Nombre d’arbres 2–3 à n clés
Nous nous intéressons ici à un problème plus complexe que ceux que nous
avons traités jusqu’à présent : le dénombrement des arbres 2–3 contenant
un nombre donné n de clés, quelle que soit leur hauteur – nous savons
seulement, par le théorème 4.19, que celle-ci est comprise entre log 3 (n + 1)
et log 2 (n + 1). Nos références ici sont l’article d’Odlyzko [199] et le livre
de Flajolet et Sedgewick [94]. Si nous supposons que les arbres considérés
sont des arbres de recherche, que les clés sont distinctes, et qu’elles sont
uniquement dans les nœuds internes, le nombre de feuilles correspond alors au
nombre d’intervalles déterminés par les clés, et est égal à n + 1 ; en d’autres
termes il revient au même de déterminer le nombre d’arbres 2–3 à n + 1
feuilles, ou à n clés. Soit donc e n le nombre d’arbres 2–3 à n feuilles, et soit
E(z) =
n≥0 e n z n sa fonction génératrice. Nous donnons des indications
sur une manière (relativement) simple d’aborder l’étude de E(z) dans le
problème 4.22, et résumons les résultats obtenus dans la proposition suivante.
Proposition 4.23 La fonction génératrice E(z) du nombre d’arbres 2–3,
énumérés suivant le nombre de leurs feuilles, satisfait l’équation fonctionnelle
E(z) = z + E(z
2
+ z
3 ).
Elle a pour rayon de convergence le nombre d’or
1+
√
5
2 , et ses premiers termes
sont donnés par
E(z) = z + z
2
+ z
3
+ z
4
+ 2 z
5
+ 2 z
6
+ 3 z
7
+ 4 z
8
+ 5 z
9
+ 8 z
10
+ O
z
11
.
Le nombre d’arbres 2–3 avec n feuilles est d’ordre exponentiel
1+
√
5
2
n
.
Le calcul de l’équivalent asymptotique exact de e n fait appel à des techniques
sophistiquées d’analyse complexe et sort du cadre de ce livre. Nous nous
contentons de donner le résultat, et renvoyons à [199] et [94, pp. 281–283]
pour plus d’informations.
Proposition 4.24 Le nombre d’arbres 2–3 avec n feuilles satisfait asymptotiquement
e n =
ω(n)
n
1 +
√
5
2
n
(1 + O(1/n)),
où ω(n) est une fonction périodique de moyenne 0,71208. . . , d’amplitude
inférieure à 0.1, et de période 0,86792. . .
163
Nombre d’arbres 2–3 à n clés
Nous nous intéressons ici à un problème plus complexe que ceux que nous
avons traités jusqu’à présent : le dénombrement des arbres 2–3 contenant
un nombre donné n de clés, quelle que soit leur hauteur – nous savons
seulement, par le théorème 4.19, que celle-ci est comprise entre log 3 (n + 1)
et log 2 (n + 1). Nos références ici sont l’article d’Odlyzko [199] et le livre
de Flajolet et Sedgewick [94]. Si nous supposons que les arbres considérés
sont des arbres de recherche, que les clés sont distinctes, et qu’elles sont
uniquement dans les nœuds internes, le nombre de feuilles correspond alors au
nombre d’intervalles déterminés par les clés, et est égal à n + 1 ; en d’autres
termes il revient au même de déterminer le nombre d’arbres 2–3 à n + 1
feuilles, ou à n clés. Soit donc e n le nombre d’arbres 2–3 à n feuilles, et soit
E(z) =
n≥0 e n z n sa fonction génératrice. Nous donnons des indications
sur une manière (relativement) simple d’aborder l’étude de E(z) dans le
problème 4.22, et résumons les résultats obtenus dans la proposition suivante.
Proposition 4.23 La fonction génératrice E(z) du nombre d’arbres 2–3,
énumérés suivant le nombre de leurs feuilles, satisfait l’équation fonctionnelle
E(z) = z + E(z
2
+ z
3 ).
Elle a pour rayon de convergence le nombre d’or
1+
√
5
2 , et ses premiers termes
sont donnés par
E(z) = z + z
2
+ z
3
+ z
4
+ 2 z
5
+ 2 z
6
+ 3 z
7
+ 4 z
8
+ 5 z
9
+ 8 z
10
+ O
z
11
.
Le nombre d’arbres 2–3 avec n feuilles est d’ordre exponentiel
1+
√
5
2
n
.
Le calcul de l’équivalent asymptotique exact de e n fait appel à des techniques
sophistiquées d’analyse complexe et sort du cadre de ce livre. Nous nous
contentons de donner le résultat, et renvoyons à [199] et [94, pp. 281–283]
pour plus d’informations.
Proposition 4.24 Le nombre d’arbres 2–3 avec n feuilles satisfait asymptotiquement
e n =
ω(n)
n
1 +
√
5
2
n
(1 + O(1/n)),
où ω(n) est une fonction périodique de moyenne 0,71208. . . , d’amplitude
inférieure à 0.1, et de période 0,86792. . .