On voit ici comment insérer un élément {x} dans un ABR {\mathcal{A}(}de telle façon que l’arbre obtenu {\mathcal{A}^{\prime }} soit encore un ABR).
Il y a deux méthodes : « ajout aux feuilles » {(x} est inséré de façon à être une feuille de {\mathcal{A}^{\prime })} et « ajout à la racine » {(x} est inséré de façon à se retrouver à la racine de {\mathcal{A}^{\prime }).}
11.2.1 Insertion aux feuilles
On rappelle la fonction feuille, toujours utile :
|
1 |
let feuille x = Noeud(Vide, x, Vide);; |
La fonction addabr_f ajoute un élément {x} en tant que feuille sur un ABR {\mathcal{A}:} si {\mathcal{A}} est vide on le remplace par une feuille étiquetée {x,} sinon on compare {x} avec la racine {e} de {\mathcal{A}} et suivant le résultat on poursuit récursivement en insérant {x} soit dans le fils droit de {\mathcal{A}(}si {x>e)} soit dans le fils gauche (si {x\le e):}
|
1 2 3 4 5 |
let rec addabr_f a x = match a with | Vide -> feuille x | Noeud(g, e, d) when e < x -> Noeud(g, e, addabr_f d x) | Noeud(g, e, d) -> Noeud(addabr_f g x, e, d);; val addabr_f : 'a arbre -> 'a -> 'a arbre = <fun> |
Exemple : on part de l’arbre de recherche {T} décrit ci-dessous :
|
1 |
let t = Noeud(feuille 3, 5, Noeud(Noeud(feuille 6, 7, feuille 9), 10, feuille 12));; |
On évalue successivement :
|
1 |
let u = addabr_f t 4;; let v = addabr_f u 1;; let w = addabr_f v 8;; |
Voici une représentation des arbres obtenus :

Les fonctions list_of_abr et abr_of_list effectuent la conversion entre un ABR et la liste de ses étiquettes. Pour la fonction list_of_abr, on part de l’arbre vide et on ajoute les éléments de la liste avec addabr_f (la tête de la liste est ajoutée en dernier). Pour la fonction abr_of_list, la liste obtenue montre les étiquettes triées dans l’ordre croissant :
|
1 2 3 4 |
let rec abr_of_list l = match l with | [] -> Vide | x::q -> addabr_f (abr_of_list q) x;; val abr_of_list : 'a list -> 'a arbre = <fun> |
|
1 2 3 4 5 |
let rec list_of_abr a = match a with | Vide -> [] | Noeud(g, e, d) -> (list_of_abr g) @ (e :: list_of_abr d);; val list_of_abr : 'a arbre -> 'a list = <fun> |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres