160
4 Approche combinatoire
Soit a h le nombre d’arbres 2–3 de recherche de hauteur h, ou plus exactement
le nombre de marquages canoniques de ces arbres 8 ; établissons une relation de
récurrence sur ce nombre. Il y a deux arbres avec un seul nœud interne – ce nœud
peut avoir deux ou trois enfants, qui sont ici des feuilles – et donc a 0 = 2. Plus
généralement, en considérant les deux possibilités pour la racine : elle a deux ou
trois enfants, nous voyons que la suite (a h ) satisfait la récurrence
a h+1 = a
2
h + a
3
h .
Cette suite a une croissance extrêmement rapide en h : il y a 2 arbres de hauteur 0,
12 arbres de hauteur 1, 1872 arbres de hauteur 2, 6 563 711 232 arbres de hauteur
3, et plus de 28 10 28 arbres de hauteur 4. De manière inattendue (cf. la suite
A125295 de [200]) c’est aussi le nombre de façons de résoudre le problème des
tours de Hanoï avec h + 1 disques « sans boucler », i.e., sans repasser par un état
déjà rencontré : la récurrence est identique. En fait, il s’avère qu’un arbre 2–3 de
hauteur h code bijectivement une suite de mouvements permettant une résolution
du problème à h disques ; nous donnons des indications sur ce codage et sur ce que
nous pouvons en déduire sur la complexité moyenne d’une stratégie de résolution
dans le problème 4.19.
La suite des a h a une croissance doublement exponentielle – même si ce n’est
pas une suite « doublement exponentielle » au sens que Aho et Sloane donnent
à ce mot [2]. 9 Si nous regardons de plus près la récurrence satisfaite par les a h ,
nous pouvons tout d’abord vérifier aisément, en prenant la suite (x h ) h≥0 définie par
x 0 = 2, x h+1 = x 3
h , qui minore la suite (a h ) h≥0 , que a h > 2 3 h . Posons ensuite
v h = a
1/3 h
h
; nous avons
v h+1
v h
=
1 +
1
a h
1
3 h+1
.
Par conséquent, avec v 0 = a 0 = 2,
v h = v 0
h−1
1 +
1
a
1
3
.
8 Pour des arbres de recherche, il y a une seule manière d’attribuer les rangs des clés aux nœuds
dès que le nombre de clés dans chaque nœud est connu.
9 Aho et Sloane définissent une suite doublement exponentielle comme une suite (x n ) telle que
x n+1 = x 2
n + g n avec |g n | < x n /4, et montrent alors que x
1/2 n
n
a une limite finie.
4 Approche combinatoire
Soit a h le nombre d’arbres 2–3 de recherche de hauteur h, ou plus exactement
le nombre de marquages canoniques de ces arbres 8 ; établissons une relation de
récurrence sur ce nombre. Il y a deux arbres avec un seul nœud interne – ce nœud
peut avoir deux ou trois enfants, qui sont ici des feuilles – et donc a 0 = 2. Plus
généralement, en considérant les deux possibilités pour la racine : elle a deux ou
trois enfants, nous voyons que la suite (a h ) satisfait la récurrence
a h+1 = a
2
h + a
3
h .
Cette suite a une croissance extrêmement rapide en h : il y a 2 arbres de hauteur 0,
12 arbres de hauteur 1, 1872 arbres de hauteur 2, 6 563 711 232 arbres de hauteur
3, et plus de 28 10 28 arbres de hauteur 4. De manière inattendue (cf. la suite
A125295 de [200]) c’est aussi le nombre de façons de résoudre le problème des
tours de Hanoï avec h + 1 disques « sans boucler », i.e., sans repasser par un état
déjà rencontré : la récurrence est identique. En fait, il s’avère qu’un arbre 2–3 de
hauteur h code bijectivement une suite de mouvements permettant une résolution
du problème à h disques ; nous donnons des indications sur ce codage et sur ce que
nous pouvons en déduire sur la complexité moyenne d’une stratégie de résolution
dans le problème 4.19.
La suite des a h a une croissance doublement exponentielle – même si ce n’est
pas une suite « doublement exponentielle » au sens que Aho et Sloane donnent
à ce mot [2]. 9 Si nous regardons de plus près la récurrence satisfaite par les a h ,
nous pouvons tout d’abord vérifier aisément, en prenant la suite (x h ) h≥0 définie par
x 0 = 2, x h+1 = x 3
h , qui minore la suite (a h ) h≥0 , que a h > 2 3 h . Posons ensuite
v h = a
1/3 h
h
; nous avons
v h+1
v h
=
1 +
1
a h
1
3 h+1
.
Par conséquent, avec v 0 = a 0 = 2,
v h = v 0
h−1
1 +
1
a
1
3
.
8 Pour des arbres de recherche, il y a une seule manière d’attribuer les rangs des clés aux nœuds
dès que le nombre de clés dans chaque nœud est connu.
9 Aho et Sloane définissent une suite doublement exponentielle comme une suite (x n ) telle que
x n+1 = x 2
n + g n avec |g n | < x n /4, et montrent alors que x
1/2 n
n
a une limite finie.