4.6 Exercices et problèmes
179
Fig. 4.17 Un exemple
d’arbre 2–3 codant une
résolution pour une tour de
Hanoï de 3 disques ; les
feuilles sont omises
nombre minimal de mouvements, et celle qui le résout, sans repasser par la même configuration,
en un nombre maximal de mouvements. Quelles sont leurs longueurs respectives ?
5. En supposant toutes les suites de résolution sans répétitions équiprobables, calculer la longueur
moyenne d’une telle suite et donner sa valeur asymptotique.
6. Établir un lien entre le nombre de fois où un disque donné est déplacé lors de la suite de
mouvements indiquée par σ (τ ), et un paramètre de l’arbre τ .
Problème 4.20. (Nombre de clés dans un arbre 2–3 de hauteur donnée) On rappelle que la
fonction génératrice bivariée des arbres 2–3 de hauteur h, où x marque le nombre de clés et y le
nombre de nœuds internes, satisfait l’équation de récurrence
A h+1 (x, y) = xyA
2
h (x, y) + x
2 yA
3
h (x, y)
avec pour cas de base A 0 (x, y) = xy + x 2 y. Le but de ce problème est de démontrer la
proposition 4.22.
1. En posant a h = A h (1, 1) et k h =
∂A h
∂x (1, 1), établir la relation
k h + 1 = 3(k h−1 + 1) −
a h−1 + k h−1
a h−1 (a h−1 + 1)
.
2. Soit ε h =
a h−1 +k h−1
a h−1 (a h−1 +1) . Établir que
lim
h→+∞
3
−h
k h
a h
+ 1
= 1 −
i≥0
ε i
3 i+1 .
3. Montrer que
i>h
ε i
3 i ≤
i>h
1
a i
.
4. En tenant compte du fait que a h ≥ 2 3 h , en déduire la convergence de
i≥0
ε i
3 i+1 . Conclure.
5. Étendre l’approche ci-dessus à l’étude du nombre moyen de nœuds internes.
(On pourra se reporter à l’article de Reingold [220].)
Problème 4.21. (Arbres AVL) Un arbre AVL est un arbre binaire de recherche tel que, en tout
nœud interne, les hauteurs des deux sous-arbres diffèrent au plus de 1. Nous nous intéressons ici
aux formes d’arbres AVL ; par abus de langage nous parlerons aussi d’arbre AVL pour l’arbre
non marqué, le marquage des nœuds étant déterminé par le fait que l’arbre est de recherche – la
relation est la même qu’entre les arbres binaires de recherche et les arbres binaires sous le modèle
de Catalan.
1. Soit v h le nombre d’arbres AVL de hauteur h, avec v 0 = v 1 = 1. Montrer la récurrence
v h = v 2
h−1 + 2v h−1 v h−2 pour h ≥ 2. En déduire que, asymptotiquement lorsque h → +∞,
v h → κ 2 h avec κ = 1,436872848.
2. Montrer que le nombre n h de nœuds dans un arbre AVL de hauteur donnée h satisfait la
récurrence
n h = 2n h−1 (v h−1 + v h−2 ) + 2n h−2 v h−1 + v
2
h−1 + 2v h−1 v h−2 .
179
Fig. 4.17 Un exemple
d’arbre 2–3 codant une
résolution pour une tour de
Hanoï de 3 disques ; les
feuilles sont omises
nombre minimal de mouvements, et celle qui le résout, sans repasser par la même configuration,
en un nombre maximal de mouvements. Quelles sont leurs longueurs respectives ?
5. En supposant toutes les suites de résolution sans répétitions équiprobables, calculer la longueur
moyenne d’une telle suite et donner sa valeur asymptotique.
6. Établir un lien entre le nombre de fois où un disque donné est déplacé lors de la suite de
mouvements indiquée par σ (τ ), et un paramètre de l’arbre τ .
Problème 4.20. (Nombre de clés dans un arbre 2–3 de hauteur donnée) On rappelle que la
fonction génératrice bivariée des arbres 2–3 de hauteur h, où x marque le nombre de clés et y le
nombre de nœuds internes, satisfait l’équation de récurrence
A h+1 (x, y) = xyA
2
h (x, y) + x
2 yA
3
h (x, y)
avec pour cas de base A 0 (x, y) = xy + x 2 y. Le but de ce problème est de démontrer la
proposition 4.22.
1. En posant a h = A h (1, 1) et k h =
∂A h
∂x (1, 1), établir la relation
k h + 1 = 3(k h−1 + 1) −
a h−1 + k h−1
a h−1 (a h−1 + 1)
.
2. Soit ε h =
a h−1 +k h−1
a h−1 (a h−1 +1) . Établir que
lim
h→+∞
3
−h
k h
a h
+ 1
= 1 −
i≥0
ε i
3 i+1 .
3. Montrer que
i>h
ε i
3 i ≤
i>h
1
a i
.
4. En tenant compte du fait que a h ≥ 2 3 h , en déduire la convergence de
i≥0
ε i
3 i+1 . Conclure.
5. Étendre l’approche ci-dessus à l’étude du nombre moyen de nœuds internes.
(On pourra se reporter à l’article de Reingold [220].)
Problème 4.21. (Arbres AVL) Un arbre AVL est un arbre binaire de recherche tel que, en tout
nœud interne, les hauteurs des deux sous-arbres diffèrent au plus de 1. Nous nous intéressons ici
aux formes d’arbres AVL ; par abus de langage nous parlerons aussi d’arbre AVL pour l’arbre
non marqué, le marquage des nœuds étant déterminé par le fait que l’arbre est de recherche – la
relation est la même qu’entre les arbres binaires de recherche et les arbres binaires sous le modèle
de Catalan.
1. Soit v h le nombre d’arbres AVL de hauteur h, avec v 0 = v 1 = 1. Montrer la récurrence
v h = v 2
h−1 + 2v h−1 v h−2 pour h ≥ 2. En déduire que, asymptotiquement lorsque h → +∞,
v h → κ 2 h avec κ = 1,436872848.
2. Montrer que le nombre n h de nœuds dans un arbre AVL de hauteur donnée h satisfait la
récurrence
n h = 2n h−1 (v h−1 + v h−2 ) + 2n h−2 v h−1 + v
2
h−1 + 2v h−1 v h−2 .