Lire un arbre

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

Énoncé

Soit l'arbre


let a = Noeud (Noeud (Noeud (Vide, 1, Vide), 3,
                      Noeud (Noeud (Vide, 4, Vide), 6, Vide)),
               8,
               Noeud (Noeud (Vide, 7, Vide), 9, Vide))

Donner sa taille, sa hauteur, le nombre de ses feuilles et de ses nœuds internes, la profondeur de chaque étiquette, et le nombre de nœuds par niveau. Vérifier l'encadrement du cours.

Corrigé

Les comptes, tous vérifiés par le calcul :

taille $n$	$7$
hauteur $h$	$3$
feuilles	$3$ \ \ (les étiquettes $1$ , $4$ , $7$ )
nœuds internes	$4$ \ \ (les étiquettes $8$ , $3$ , $6$ , $9$ )
nœuds à deux fils non vides	$2$ \ \ (les étiquettes $8$ et $3$ )

Les profondeurs : $8$ à la profondeur $0$ ; $3$ et $9$ à $1$ ; $1$ , $6$ et $7$ à $2$ ; $4$ à $3$ . La hauteur est la plus grande d'entre elles, soit $3$ .

Les niveaux, et la comparaison avec le maximum $2^{k}$ :

niveau $k$	$0$	$1$	$2$	$3$
nœuds	$1$	$2$	$3$	$1$
au plus $2^{k}$	$1$	$2$	$4$	$8$

Les deux premiers niveaux sont pleins, les deux derniers non : l'arbre n'est pas complet.

L'encadrement du cours, $h + 1 \leq n \leq 2^{h + 1} - 1$ , donne ici $4 \leq 7 \leq 15$ . Il est vérifié, et lâche des deux côtés : cet arbre n'est ni un peigne ( $n = 4$ ) ni un arbre parfait ( $n = 15$ ). Il est exactement au milieu.

Trois remarques de lecture qui servent tout le chapitre.

Un. $feuilles + internes = 3 + 4 = 7 = n$ . La partition est complète par définition : un nœud a ses deux fils vides, ou pas.

Deux. $feuilles = 3$ et $n œ uds a ˋ deux fils = 2$ : on retrouve $f (a) = d (a) + 1$ , l'identité démontrée par induction au chapitre chap:induction. Elle ne dépend ni de la forme ni de la taille de l'arbre — c'est ce qui en fait un invariant utile pour déboguer un constructeur d'arbres.

Trois. La somme des profondeurs vaut $0 + 1 + 1 + 2 + 2 + 2 + 3 = 11$ , soit une profondeur moyenne de $11/7 \approx 1, 57$ . C'est cette moyenne, et non la hauteur, qui gouverne le coût d'une recherche sur une clé tirée au hasard — une distinction dont on reparlera au chapitre chap:tas.

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.