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