Sérialiser à la main, et compter les jetons

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 12 — Tableaux associatifs, hachage et sérialisation

Énoncé

Soit l'arbre de racine $5$ , dont le fils gauche est $3$ — lui-même de fils gauche $1$ et sans fils droit — et dont le fils droit est $8$ , une feuille.

Donner sa sérialisation préfixe avec vides marqués.
Combien de jetons pour un arbre à $n$ nœuds ? Le démontrer.
Le mot # est-il indispensable dans les deux positions ?

Corrigé

1. On applique la définition : un nœud donne son étiquette, puis son fils gauche, puis son fils droit ; un sous-arbre vide donne #.


5 3 1 # # # 8 # #

Détail de la lecture : 5, puis le sous-arbre gauche 3 1 # # # — c'est-à-dire $3$ , son fils gauche 1 # #, et son fils droit # —, puis le sous-arbre droit 8 # #. Mesuré par aller-retour : la désérialisation de cette chaîne redonne l'arbre de départ.

2. Un arbre à $n$ nœuds a exactement $2n + 1$ jetons : $n$ étiquettes et $n + 1$ marqueurs #. Ici : $n = 4$ , et l'on compte bien $9$ jetons.

Démonstration, par induction structurelle. Pour $Vide$ : $n = 0$ et un seul jeton, $2 \cdot 0 + 1 = 1$ . Pour $N œ ud (g, e, d)$ de tailles $n_{g}$ et $n_{d}$ : par hypothèse d'induction les deux sous-arbres donnent $2 n_{g} + 1$ et $2 n_{d} + 1$ jetons, auxquels s'ajoute l'étiquette, soit

$1 + (2 n_{g} + 1) + (2 n_{d} + 1) = 2 (1 + n_{g} + n_{d}) + 1 = 2 n + 1.$

Vérifié par programme sur $2000$ arbres tirés au hasard.

Une autre lecture du même comptage : un arbre binaire à $n$ nœuds a exactement $n + 1$ « places vides » — c'est le nombre de sous-arbres vides —, résultat déjà vrai au chapitre chap:arbres et qu'on retrouve ici comme un sous-produit du format.

3. Oui, les deux sont indispensables, et pour deux raisons différentes.

Le # du fils droit de $3$ distingue « $1$ est le fils gauche de $3$ » de « $1$ est son fils droit ». Mesuré : sans marqueurs, l'arbre $8$ avec $3$ à gauche et l'arbre $8$ avec $3$ à droite donnent tous deux la même écriture 8 3. Avec marqueurs : 8 3 # # # contre 8 # 3 # #.
Les # des feuilles marquent la fin de la descente ; sans eux, rien ne dirait quand un sous-arbre se termine, et la lecture ne pourrait pas savoir à qui rattacher le jeton suivant.

Le # n'est pas un remplissage : c'est le seul endroit du format où la forme de l'arbre est écrite. Les étiquettes, elles, ne portent que le contenu.

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.