Appartenance dans un arbre binaire de recherche
Exercice · OCaml (option informatique), chapitre 3 — Types sommes et arbres
Énoncé
Un arbre binaire de recherche (ABR) est un 'a arbre tel que, en tout nœud, toutes les étiquettes du sous-arbre gauche sont inférieures à l'étiquette, et celles du sous-arbre droit supérieures. Écrire appartient x a qui exploite cette propriété pour ne descendre que d'un côté.
Corrigé
let rec appartient x a =
match a with
| Vide -> false
| Noeud (g, v, d) ->
if x = v then true
else if x < v then appartient x g
else appartient x dLa propriété d'ABR permet, à chaque nœud, d'éliminer la moitié de l'arbre : si x < v, inutile de chercher à droite. Sur un arbre équilibré de nœuds, la recherche coûte — bien mieux que le parcours linéaire d'une liste.
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.