Adloun

Insertion dans un ABR

Exercice · OCaml (option informatique), chapitre 3 — Types sommes et arbres

Énoncé

Écrire insere x a qui renvoie un nouvel ABR contenant x (sans modifier a), en préservant la propriété d'ABR. Une valeur déjà présente laisse l'arbre inchangé.

Corrigé

let rec insere x a =
  match a with
  | Vide -> Noeud (Vide, x, Vide)
  | Noeud (g, v, d) ->
      if x = v then a
      else if x < v then Noeud (insere x g, v, d)
      else Noeud (g, v, insere x d)

On insère à la place du premier Vide rencontré en suivant la règle de comparaison. La reconstruction Noeud (insere x g, v, d) ne recopie que le chemin de la racine au point d'insertion : le reste de l'arbre est partagé, non dupliqué. C'est la version persistante (immuable) d'un ABR.

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.