Probleme – Écrire un arbre sur une ligne, et le relire

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

Énoncé

On veut ranger un arbre dans un fichier, puis le reconstruire à l'identique.

Pourquoi le parcours préfixe seul ne suffit-il pas ?
Définir une sérialisation préfixe avec marqueurs, et écrire les deux fonctions.
Prouver que la relecture est l'inverse exact de l'écriture.
Combien de jetons l'écriture produit-elle ? Quel en est le coût ?

Corrigé

1. Le préfixe seul est ambigu, et l'exercice 10.9 en donne le contre-exemple : les deux arbres à deux nœuds où $7$ est fils gauche ou fils droit de $9$ ont le même préfixe $9, 7$ . Il manque exactement l'information « ce fils-ci est vide ».

2. La sérialisation avec marqueurs. On écrit un jeton pour chaque appel récursif, y compris sur les arbres vides.


(* Renvoie la liste des jetons du parcours prefixe de a, ou chaque arbre
   vide produit le jeton ".". Complexite : Theta(n). *)
let rec serialise = function
  | Vide -> ["."]
  | Noeud (g, e, d) -> string_of_int e :: (serialise g @ serialise d)

(* Reconstruit l'arbre a partir de ses jetons.
   Precondition : la liste provient de `serialise`.
   Leve une exception si les jetons manquent ou sont en trop. *)
let deserialise jetons =
  let rec aux = function
    | [] -> failwith "jetons manquants"
    | "." :: r -> (Vide, r)
    | x :: r ->
        let (g, r1) = aux r in                (* le sous-arbre GAUCHE d'abord *)
        let (d, r2) = aux r1 in               (* puis le DROIT, sur ce qui reste *)
        (Noeud (g, int_of_string x, d), r2)
  in
  let (a, reste) = aux jetons in
  if reste <> [] then failwith "jetons en trop" else a

Mesure : sur l'arbre de l'exercice 10.1, on obtient les quinze jetons


8 3 1 . . 6 4 . . . 9 7 . . .

et deserialise (serialise a) = a est vérifié.

La clé de deserialise, et c'est ce qui rend le problème intéressant : la fonction auxiliaire rend un couple — l'arbre lu, et ce qui reste à lire. Sans ce second membre, l'appel sur le sous-arbre droit ne saurait pas où commencer. C'est le même procédé que l'accumulateur, à l'envers : au lieu de porter ce qui est construit, on porte ce qui reste.

3. La preuve que $deserialise \circ serialise = id$ . On démontre l'énoncé renforcé, sans lequel l'induction ne passe pas :

$(Q) pour tout arbre a et toute liste ℓ, aux (serialise (a) @ ℓ) = (a, ℓ) .$

<details class="group my-6 border border-gray-300 rounded-2xl bg-black/[0.03] overflow-hidden transition-all duration-300"><summary style="color:#1e3a8a" class="flex items-center justify-between p-4 cursor-pointer text-xs font-bold select-none"><div class="flex items-center"><i class="fa-solid fa-graduation-cap mr-2"></i>Démonstration</div><span class="transition-transform group-open:rotate-180"><i class="fa-solid fa-chevron-down"></i></span></summary><div style="color:#1d4ed8" class="force-blue p-4 pt-0 border-t border-gray-200 bg-black/[0.02] leading-relaxed font-sans text-xs select-text"> Par induction structurelle sur $a$ .

Cas $a = Vide$ . $serialise (a) @ ℓ = "." :: ℓ$ , et aux rend $(Vide, ℓ)$ .

Cas $a = N œ ud (g, e, d)$ . Alors

$serialise (a) @ ℓ = e :: (serialise (g) @ (serialise (d) @ ℓ)) .$

La fonction lit $e$ , puis appelle aux sur $serialise (g) @ (serialise (d) @ ℓ)$ . L'hypothèse d'induction sur $g$ , appliquée avec la liste $serialise (d) @ ℓ$ , donne le couple $(g, serialise (d) @ ℓ)$ . Le second appel, par hypothèse d'induction sur $d$ avec la liste $ℓ$ , donne $(d, ℓ)$ . On reconstruit donc $N œ ud (g, e, d) = a$ , en laissant $ℓ$ .

L'énoncé renforcé est indispensable : la propriété « $aux (serialise (a)) = (a, [])$ » ne s'hérite pas, car dans le cas récursif l'appel sur $g$ ne porte pas sur une liste vide. C'est la difficulté du problème, et elle est de méthode : quand une induction échoue, il faut souvent prouver plus.

En prenant $ℓ = []$ , on obtient $aux (serialise (a)) = (a, [])$ , donc deserialise ne lève pas l'exception et rend $a$ .

4. Le nombre de jetons est $2 n + 1$ . Mesure : $15$ jetons pour $n = 7$ . La preuve est une induction immédiate : $Vide$ donne $1 = 2 \times 0 + 1$ , et $N œ ud (g, e, d)$ donne $1 + (2 n_{g} + 1) + (2 n_{d} + 1) = 2 (1 + n_{g} + n_{d}) + 1$ .

Autrement dit : un arbre à $n$ nœuds a exactement $n + 1$ sous-arbres vides. C'est le même comptage que les $n + 1$ intervalles délimités par $n$ points, et il resservira au chapitre chap:tas.

Coût. La désérialisation est en $Θ (n)$ : chaque jeton est consommé une fois. La sérialisation, telle qu'écrite, est en $Θ (n^{2})$ sur un peigne à cause du @ — exercice 10.5. Un accumulateur la ramène à $Θ (n)$ :


let rec serialise_acc a acc = match a with
  | Vide -> "." :: acc
  | Noeud (g, e, d) -> string_of_int e :: serialise_acc g (serialise_acc d acc)

Ce que le problème apprend. On a mesuré le prix de la réversibilité : $n + 1$ jetons de plus, soit un peu plus du double. C'est le prix universel de la sérialisation d'un arbre — et il explique pourquoi les formats réels préfèrent souvent écrire, à la place, le nombre de fils de chaque nœud : même quantité d'information, autre découpage.

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.