Probleme – Combien de nœuds faut-il pour être haut ?

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 10 — Arbres

Énoncé

On dit qu'un arbre binaire est équilibré en hauteur si, en chacun de ses nœuds, les hauteurs des deux fils diffèrent d'au plus $1$ .

Donner une relation de récurrence pour $N (h)$ , le nombre minimal de nœuds d'un tel arbre de hauteur $h$ .
Calculer $N (h)$ et l'exprimer avec la suite de Fibonacci.
En déduire une majoration de la hauteur en fonction du nombre de nœuds, et la vérifier.
Pourquoi ce résultat est-il celui qui justifie tout le chapitre suivant ?

Corrigé

1. La récurrence. Un arbre équilibré de hauteur $h \geq 1$ et de taille minimale a une racine, un fils de hauteur $h - 1$ — il en faut un pour atteindre la hauteur $h$ — et un second fils dont la hauteur est au moins $h - 2$ , par la contrainte d'équilibre. Pour minimiser, on prend exactement $h - 2$ , et chacun des deux fils est lui-même minimal. D'où

$N (h) = 1 + N (h - 1) + N (h - 2), N (- 1) = 0, N (0) = 1.$

La convention $h (Vide) = - 1$ du cours rend l'initialisation limpide : $N (- 1) = 0$ est l'arbre vide, et non un cas particulier. Avec la convention $h (Vide) = 0$ , il faudrait ici une exception.

2. Les valeurs, calculées, et la forme close :

$h$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
$N (h)$	$1$	$2$	$4$	$7$	$12$	$20$	$33$	$54$	$88$	$143$	$232$	$376$	$609$

On reconnaît les nombres de Fibonacci diminués de $1$ , et l'identité

$N (h) = F (h + 3) - 1$

a été vérifiée pour $h$ de $0$ à $20$ , avec $F (1) = F (2) = 1$ . Par exemple $N (10) = 232$ et $F (13) = 233$ .

Preuve. Par récurrence forte. $N (- 1) = 0 = F (2) - 1$ et $N (0) = 1 = F (3) - 1$ . Puis

$N (h) = 1 + (F (h + 2) - 1) + (F (h + 1) - 1) = F (h + 2) + F (h + 1) - 1 = F (h + 3) - 1.$

3. La majoration de la hauteur. Un arbre équilibré de hauteur $h$ et de taille $n$ vérifie $n \geq N (h) = F (h + 3) - 1$ , donc $n + 1 \geq F (h + 3)$ . Comme $F (k) \sim φ^{k} / 5$ avec $φ = (1 + 5) /2$ , on obtient en passant au logarithme

$h \leq lo g_{φ} (n + 2) + O (1) = \frac{lo g _{2} ( n + 2 )}{lo g _{2} φ} + O (1) \approx 1, 4405 lo g_{2} (n + 2) - 0, 3277.$

Cette borne a été vérifiée numériquement pour $h$ de $0$ à $40$ , c'est-à-dire jusqu'à $N (40) = 433494436$ nœuds : elle tient, avec un écart maximal de $1, 96$ .

Le chiffre à retenir est $1, 44$ . Un arbre équilibré en hauteur est au plus $44 %$ plus haut que l'arbre parfait de même taille. La comparaison, obtenue en cherchant le plus grand $h$ tel que $N (h) \leq n$ , est frappante :

$n$	hauteur d'un arbre parfait	hauteur maximale d'un équilibré
$1 0^{3}$	$9$	$13$
$1 0^{6}$	$19$	$27$
$1 0^{9}$	$29$	$41$

Contre une hauteur de $1 0^{9} - 1$ pour un peigne de même taille.

4. Pourquoi ce résultat gouverne le chapitre suivant. Le cours a établi deux choses : la hauteur est comprise entre $Θ (lo g n)$ et $n - 1$ , et toute recherche coûte $O (h)$ . Il en découlait une question sans réponse : comment garantir qu'on est du bon côté ?

Ce problème donne la réponse, et elle est du meilleur genre : une contrainte purement locale — en chaque nœud, les hauteurs des fils diffèrent d'au plus $1$ — suffit à garantir une propriété globale, $h = O (lo g n)$ . On peut donc maintenir l'équilibre en ne regardant, à chaque insertion, que le voisinage du chemin parcouru : c'est ce que feront les arbres bicolores du chapitre chap:tas.

L'arbre qui sature la borne mérite d'être connu : c'est l'arbre de Fibonacci, défini par $F_{h} = N œ ud (F_{h - 1}, e, F_{h - 2})$ . Il est le pire cas de tous les algorithmes d'arbres équilibrés, et c'est donc le premier arbre sur lequel on les teste — une application directe de la méthode du chapitre chap:discipline : ne pas tester au hasard, tester aux frontières.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.