OCaml (option informatique) · Chapitre 3 · Exercice de TD
Insertion dans un ABR
Types sommes et arbres · niveau 3 (difficile)
É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.
Exercices semblables
- Compter les feuilles corrigé
- Miroir d'un arbre corrigé
- Évaluer une expression arithmétique corrigé
- Appartenance dans un arbre binaire de recherche corrigé
- Parcours infixe corrigé