On se propose ici d’écrire une fonction supprimant un élément {x} d’un ABR {\mathcal{A}.} La première chose à remarquer est cette suppression n’affecte que la partie de {\mathcal{A}} dont {x} est la racine. Le problème est donc essentiellement de savoir supprimer la racine d’un ABR. Si on supprime la racine {x} de Noeud(g,x,d), on doit renvoyer Noeud(g',y,d), où {g^{\prime }} est l’arbre {g} privé de son maximum {y.} On écrit donc deux utilitaires : la fonction delmax, d’argument {\mathcal{A},} renvoie le couple {(\mathcal{B},y)} où {\mathcal{B}} représente {\mathcal{A}} privé de son maximum {y.} Ensuite la fonction decapite, d’argument {\mathcal{A},} renvoie l’arbre privé de sa racine (et réorganisé en ABR, bien sûr) :
|
1 2 3 4 5 6 |
let rec delmax a = match a with | Vide -> failwith "arbre vide" | Noeud(g, e, Vide) -> g, e | Noeud(g, e, d) -> let (d', x) = delmax d in Noeud(g, e, d'), x;; val delmax : 'a arbre -> 'a arbre * 'a = <fun> |
|
1 2 3 4 5 6 |
let rec decapite a = match a with | Vide -> failwith "arbre vide" | Noeud(Vide, e, d) -> d | Noeud(g, e, d) -> let (g', y) = delmax g in Noeud(g', y, d);; val decapite : 'a arbre -> 'a arbre = <fun> |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres