Le miroir

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

Énoncé

Écrire miroir, prouver que $miroir \circ miroir = id$ , et déterminer le parcours infixe du miroir en fonction de celui de l'arbre.

Corrigé


(* Renvoie l'arbre symetrique de a. Complexite : Theta(n) en temps. *)
let rec miroir = function
  | Vide -> Vide
  | Noeud (g, e, d) -> Noeud (miroir d, e, miroir g)     (* d et g ECHANGES *)

<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-key mr-2"></i>Démonstration (du fait que $miroir (miroir (a)) = a$ )</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. Deux constructeurs, deux cas.

Cas $a = Vide$ . $miroir (miroir (Vide)) = Vide$ .

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

$miroir (miroir (a)) = miroir (N œ ud (miroir (d), e, miroir (g))) = N œ ud (miroir (miroir (g)), e, miroir (miroir (d))),$

qui vaut $N œ ud (g, e, d) = a$ par hypothèse d'induction appliquée à $g$ et à $d$ .

Le parcours infixe est renversé : $infixe (miroir (a)) = renverse (infixe (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"> Induction structurelle. Le cas $Vide$ est immédiat. Pour $a = N œ ud (g, e, d)$ :

$infixe (miroir (a)) = infixe (miroir (d)) @ (e :: infixe (miroir (g))) = renverse (infixe (d)) @ (e :: renverse (infixe (g))) = renverse (infixe (g) @ (e :: infixe (d))) = renverse (infixe (a)),$

l'avant-dernière égalité utilisant $renverse (u @ v) = renverse (v) @ renverse (u)$ , démontré au chapitre chap:induction.

Vérification : sur l'arbre de l'exercice 10.1, $infixe (a) = 1, 3, 4, 6, 8, 7, 9$ et $infixe (miroir (a)) = 9, 7, 8, 6, 4, 3, 1$ . Les deux listes sont bien l'inverse l'une de l'autre, et $miroir (miroir (a)) = a$ : vérifié.

Et les deux autres parcours ? Le préfixe du miroir n'est pas l'inverse du préfixe : c'est l'inverse du postfixe. En effet, préfixe visite racine-gauche-droite ; en renversant l'arbre puis la liste, on obtient gauche-droite-racine, qui est le postfixe. Symétriquement, $postfixe (miroir (a)) = renverse (prefixe (a))$ . Seul l'infixe est stable par cette double symétrie, parce qu'il est le seul des trois à être symétrique dans sa définition.

À quoi cela sert. À obtenir gratuitement la variante décroissante de tout algorithme fondé sur l'infixe : parcourir un arbre binaire de recherche par ordre décroissant, c'est parcourir son miroir par ordre croissant — ou, plus économiquement, échanger les deux appels récursifs, ce qui coûte $Θ (1)$ au lieu de $Θ (n)$ .

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.