Problème — Écrire un arbre sur une ligne, et le relire

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 $\text{deserialise}\circ \text{serialise}=\text{id}$. On démontre l'énoncé renforcé, sans lequel l'induction ne passe pas :

$$(\mathcal{Q})\text{pour tout arbre }a\text{ et toute liste }\ell ,\text{aux}(\text{serialise}(a)@\ell )=(a,\ell ).$$

Démonstration

Par induction structurelle sur $a$.

Cas $a=\text{Vide}$. $\text{serialise}(a)@\ell =\text{"."}::\ell$, et aux rend $(\text{Vide},\ell )$.

Cas $a=\text{Nœud}(g,e,d)$. Alors

$$\text{serialise}(a)@\ell =e::(\text{serialise}(g)@(\text{serialise}(d)@\ell )).$$

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

L'énoncé renforcé est indispensable : la propriété « $\text{aux}(\text{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 $\ell =[]$, on obtient $\text{aux}(\text{serialise}(a))=(a,[])$, donc deserialise ne lève pas l'exception et rend $a$.

4. Le nombre de jetons est $2n+1$. Mesure : $15$ jetons pour $n=7$. La preuve est une induction immédiate : $\text{Vide}$ donne $1=2\times 0+1$, et $\text{Nœud}(g,e,d)$ donne $1+(2n_g+1)+(2n_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 $\Theta (n)$ : chaque jeton est consommé une fois. La sérialisation, telle qu'écrite, est en $\Theta (n^2)$ sur un peigne à cause du @ — exercice 10.5. Un accumulateur la ramène à $\Theta (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.