Probleme – L'aller-retour de la sérialisation d'un arbre

1. La désérialisation. Elle suit la structure de l'écriture : un jeton # rend $\text{Vide}$, un nombre lit son fils gauche puis son fils droit.

exception Format_invalide

(* Reconstruit l'arbre écrit par serialise. Lève Format_invalide si la chaîne
   ne code aucun arbre, ou en code un suivi de jetons superflus.
   Complexité : Theta(nombre de jetons) = Theta(2n+1). *)
let deserialise s =
  let reste = ref (List.filter (fun j -> j <> "")
                     (String.split_on_char ' ' s)) in
  let suivant () = match !reste with
    | [] -> raise Format_invalide          (* la chaîne s'arrête trop tôt *)
    | j :: r -> reste := r; j in
  let rec lire () =
    let j = suivant () in
    if j = "#" then Vide
    else
      let e = int_of_string j in
      let g = lire () in                   (* l'ORDRE compte : gauche AVANT droit *)
      let d = lire () in
      Noeud (g, e, d) in
  let a = lire () in
  if !reste <> [] then raise Format_invalide   (* des jetons en trop *)
  else a

Les deux contrôles ne sont pas décoratifs. Sans le premier, une chaîne tronquée provoquerait une exception obscure ; sans le second, "# 5 # #" serait acceptée en ne lisant que son premier jeton, et l'on perdrait silencieusement le reste. Un désérialiseur lit des données venues de l'extérieur : il doit refuser, pas deviner.

Mesuré : sur l'arbre du chapitre chap:arbres, deserialise (serialise a) = a rend true, et la chaîne compte $15$ jetons pour $7$ nœuds.

2. L'injectivité. On la démontre par un argument de code préfixe, plus fort et plus utile que l'induction directe.

Associons à chaque jeton un poids : $+1$ pour une étiquette, $-1$ pour un #. Posons $c_0=1$ et $c_j=c_{j-1}+\text{poids}(j)$ : $c_j$ compte les sous-arbres qu'il reste à écrire après $j$ jetons. Une étiquette consomme une place et en crée deux ($+1$ net) ; un # en consomme une ($-1$).

Affirmation : une suite de jetons est la sérialisation d'un arbre si et seulement si $c_j>0$ pour tout $j$ strictement inférieur à la longueur, et $c_{\text{fin}}=0$. La démonstration se fait par induction structurelle : la suite d'un arbre vide est #, avec $c_1=0$ ; celle de $\text{Nœud}(g,e,d)$ est la concaténation de $e$, de celle de $g$ et de celle de $d$, et le compteur y passe de $1$ à $2$ puis descend à $1$ à la fin de $g$, puis à $0$ à la fin de $d$ — sans jamais s'annuler avant.

Conséquence immédiate : aucun préfixe strict d'une sérialisation n'est lui-même une sérialisation, puisque $c$ ne s'annule qu'à la fin. La lecture est donc déterministe — à chaque instant, un seul découpage est possible — et l'écriture est injective. Vérifié par programme : sur $2000$ arbres tirés au hasard, le compteur reste strictement positif avant la fin et s'annule exactement à la fin ; et sur $4652$ préfixes stricts, aucun n'est une sérialisation valide.

Ce compteur donne aussi le comptage de jetons : $c$ part de $1$, monte de $n$ et descend de $(n+1)$ pour finir à $0$, d'où $2n+1$ jetons.

3. Le cas de l'arbre binaire de recherche. Ici le # devient inutile : le parcours préfixe seul détermine l'arbre.

Pourquoi. Soit $e_1,e_2,\dots ,e_n$ le parcours préfixe d'un ABR. La racine est $e_1$. Les étiquettes du sous-arbre gauche sont toutes $<e_1$, celles du droit toutes $>e_1$, et le préfixe visite le gauche entièrement avant le droit. Donc le sous-arbre gauche est exactement le préfixe des $e_i$ inférieurs à $e_1$, et le droit le reste. La coupure est déterminée par les valeurs, là où l'arbre quelconque devait l'écrire.

(* Reconstruit un ABR à partir de son SEUL parcours préfixe.
   Précondition : l est le parcours préfixe d'un ABR dont les étiquettes sont
   deux à deux distinctes, et distinctes de min_int et de max_int.
   Complexité : O(n) — chaque jeton est consommé une fois. *)
let abr_de_prefixe l =
  let reste = ref l in
  let rec lire bmin bmax =
    match !reste with
    | e :: r when bmin < e && e < bmax ->    (* e appartient à CE sous-arbre *)
        reste := r;
        let g = lire bmin e in
        let d = lire e bmax in
        Noeud (g, e, d)
    | _ -> Vide                              (* hors bornes : le sous-arbre finit *)
  in lire min_int max_int

Vérification exhaustive : pour $k$ de $1$ à $8$, on engendre tous les ABR sur les clés $1,\dots ,k$ — leur nombre est le $k$-ième nombre de Catalan, mesuré $1,2,5,14,42,132,429,1430$ — et l'on contrôle que leurs parcours préfixes sont deux à deux distincts et que abr_de_prefixe redonne l'arbre. Les deux propriétés tiennent dans tous les cas.

Le gain, et pourquoi il ne change pas la règle. Le format passe de $2n+1$ jetons à $n$ : plus de moitié économisée. Mais il ne vaut que pour un ABR à clés distinctes, et il exige de la lecture qu'elle connaisse cette hypothèse. Un format compact est un format qui délègue de l'information à la convention — ce qui est un gain tant que les deux bouts partagent la convention, et une catastrophe silencieuse dès qu'ils divergent. La règle du chapitre reste donc la bonne par défaut : écrire la forme.