Info_MPSI/MP/abr2.ml

(* A2324 - Arbres binaires de recherche *)

(* d�finition du type arbre dont les �tiquettes sont des entiers,
nous rappelons l'existence des deux constantes max_int et min_int de typ int 
que vous pourrez assimiler respectivement � +infini et -infini *)
type arbre = Vide | Noeud of int * arbre * arbre ;;

(* exemple d'un arbre *)
let a_ex = Noeud (150,
             Noeud (60,
               Noeud (40,
                 Noeud(20,
                   Vide,
                   Noeud(30,Vide,Vide)
                   ),
                 Noeud(50,Vide,Vide)
                 ),
               Noeud (70,
                 Vide,
                 Noeud(130,
                   Noeud(90,Vide,Vide),
                   Vide
                 )
               )
            ),
             Noeud (190,
               Noeud (170,
                 Vide,
                 Noeud (180,Vide,Vide)
               ),
               Noeud(200,Vide,Vide)
               )
             )
;;
(* Q1 : repr�senter proprement cet arbres sur votre copie, 
est-ce un ABR ? aucune justification n'est demand�e *)

(* recherche de la valeur maximale, de la valeur minimale des �tiquettes d'un arbre quelconque *)
(*Comme a est un arbre, on peut comparer la racine du noeud courant avec le maximum du fils droit et le maximum du fils gauche*)
let rec max_arbre (a:arbre) : int = match a with
  | Vide -> min_int
  | Noeud (r,fg,fd) -> max (max r (max_arbre fg)) (max_arbre fd) ;;
  
max_arbre a_ex ;;
(*De même, on prend le minimum du noeud courant, et on lance les appels récursifs*)
let rec min_arbre (a:arbre) : int = match a with
  | Vide -> max_int
  | Noeud (r,fg,fd) -> min (min r (min_arbre fg)) (min_arbre fd) ;;
  
min_arbre a_ex ;;

(* Q2 : �crire une fonction qui teste si un arbre est un ABR *)
(*Pour tester si un arbre est un abr, il suffit de vérifier que la racine est plus grande que tous ses fils de gauche, plus petite que tous ses fils de droite, et que ces 2 fils sont bien des abr*)
let rec test_abr (a:arbre) : bool = match a with
| Vide -> true
| Noeud(r,g,d)-> (max_arbre g < r) && (r < min_arbre d) && (test_abr g) && (test_abr d)
;;

test_abr a_ex ;;

(* Q3 : �crire une fonction qui effectue le parcours en profondeur en mode infixe d'un arbre *)
(*Comme le parcours en profondeur, mode infixe repose sur la deuxième fois que l'on voit un objet, on le met en seconde position, et on effectue le parcours sur les 2 sous-arbres*)

let rec parcours_pro_inf (a:arbre) :(int list) = match a with
| Vide -> []
| Noeud(r,g,d) -> (parcours_pro_inf g) @ [r] @ (parcours_pro_inf d)
;;

parcours_pro_inf a_ex ;;

(* Q4 : �crire une fonction qui recherche une valeur dans les �tiquettes d'un ABR
en profitant de la,structure d'ABR *)
(*On profite de la structure d'abr, en ne recherchant que dans le sous-fil correspondant à la valeur de x<r, ce qui réduit drastiquement la complexité*)
let rec recherche_abr (a:arbre) (x:int) : bool = match a with
| Vide -> false
| Noeud(r,g,d) -> if r = x then true
                  else if r > x then recherche_abr g x
                  else recherche_abr d x
;;

recherche_abr a_ex 91 ;;

(* Q5 : �crire une fonction qui recherche l'�tiquette de valeur maximale dans un ABR en complexit� logarithmique *)
(*On profite de la structure d'abr pour chercher le maximum, qui se trouvera forcèment dans le sous-arbre de droite. De plus, il se situe sur les feuilles, donc ces 2 sous-fils sont Vide*)
(*Pour les 2 programmes, on prend Vide->0, ce choix est dû au fait que notre arbre est uniquement composé d'entiers positifs*)
let rec cle_max (a:arbre) : int = match a with
| Vide -> 0
| Noeud(r,g,d) -> if d = Vide then r
                  else cle_max d
;;
cle_max a_ex;;
(* Q6 : �crire une fonction qui recherche l'�tiquette de valeur maximale dans un ABR en complexit� logarithmique *)
(*De même, sauf que cette fois, on regarde le minimum dans le sous-arbre de gauche*)
let rec cle_min (a:arbre) : int = match a with
| Vide -> 0
| Noeud(r,g,d) -> if g = Vide then r
                  else cle_min g  
;;

cle_min a_ex ;;

(* Q7 : �crire une fonction qui renvoie la plus grande valeur e parmi les �tiquettes de l'arbre
strictement inf�rieure � une valeur donn�e *)
(*On utilise la structure d'abr, si r<c, alors on recher le maximum entre la racine et la clé prédecesseur dans le sous-fil droit. Sinon, si r>=c, alors on recherche un predeccesseur dans le sous-arbre gauche. Quand on arrive sur les feuilles, on les compare avec -Inf*)
let rec cle_predecesseur (a:arbre) (c:int) : int = match a with
| Vide -> min_int
| Noeud(r,g,d) -> if r < c then max r (cle_predecesseur d c)
                  else cle_predecesseur g c
;;

cle_predecesseur a_ex 141 ;;

(* Q7 : �crire une fonction qui renvoie la plus petite valeur e parmi les �tiquettes de l'arbre
strictement sup�rieure � une valeur donn�e *)
(*De même, sauf que cette fois on recherche un minimum, donc on compare par rapport à +Inf*)
let rec cle_successeur (a:arbre) (c:int) : int = match a with
| Vide -> max_int
| Noeud(r,g,d) -> if r > c then min r (cle_successeur g c)
                  else cle_successeur d c
;;
cle_successeur a_ex 71;;
(* Q8 : �crire une fonction qui ins�re un �l�ment dans un ABR en conservant la structure d'ABR,
insertion an niveau des feuilles de l'arbre *)
(*On compare la feuille à insérer avec le noeud courant: si le noeud courant est plus grand que l'entier à insérer, alors on insére récursivement sur le sous-fil gauche*)
(*Sinon, on insère récursivement dans le sous-fil droit, pour conserver le caractère d'abr*)
let rec insertion_feuilles (a:arbre) (c:int) : arbre = match a with
| Vide -> Noeud(c,Vide,Vide)
| Noeud(r,g,d) -> if r > c then Noeud(r,insertion_feuilles g c,d)
                  else Noeud(r,g,insertion_feuilles d c)
;;

insertion_feuilles a_ex 80 ;;

(* Q9 : �crire une fonction qui ins�re un �l�ment dans un ABR en conservant la structure d'ABR,
insertion an niveau de la racine de l'arbre *)
(*on cherche à séparer en 2, par rapport à c. Ainsi, si le noeud courant est plus grand que c, alors on sépare le sous-fil gauche*)
(*Si on sépare l'arbre vide, alors on renvoit le couple de 2 arbres vides, qui est une partition de l'arbre vide*)
(*Puis on crée récursivement une partition de l'arbre, par rapport à c*)
(*le couple crée est composée, d'une part de la partie inférieure à c, d'autre part de la partie supérieure à c*)
let rec partition (a:arbre) (c:int) : (arbre*arbre) = match a with
| Vide -> (Vide,Vide)
| Noeud(r,g,d) -> if r > c then let (g1,d1) = partition g c in (g1, Noeud(r,d1,d))
    else let (g1,d1) = partition d c in (Noeud(r,g,g1),d1) 
;;
partition a_ex 80 ;;
(*Comme on a la partition, on crée la partiition de a par rapport à c, puis on crée un arbre avec c comme racine, partiition gauche à gauche et partition droite à droite: Noeud(c,g1,d1)*)
let insertion_racine (a:arbre) (c:int) : arbre = match a with
| Vide -> Noeud(c,Vide,Vide)
| Noeud(r,g,d) -> let (g1,d1) = partition a c in Noeud(c,g1,d1)
;;

insertion_racine a_ex 80 ;;

(* Q10 a : �crire une fonction qui renvoie la valeur minimale des �tiquettes de l'arbre
et l'arbre priv� d'un sommet ayant une �tiquette de cette valeur minimale *)
(*On recherche le minimum dans un arbre, tout en la supprimant*)
(*Pour cela, on vérifie si g n'est pas Vide, car sinon le minimum se trouve en le noeud courant*)
(*Sinon, on supprime récursivement le minimum dans le sous-fil gauche*)
(*On utilise min_int afin de trouver le minimum et d'avoir un élément de comparaison qui sera bien plus petit que tout élément de l'arbre, que nous supposons être des entiers naturels*)
let rec supprime_cle_min (a:arbre) : (int*arbre) = match a with
| Vide -> (min_int,Vide)
| Noeud(r,g,d) -> if g = Vide then (r,d)
                  else let (r1,g1) = supprime_cle_min g in (r1,Noeud(r,g1,d))
;;
supprime_cle_min a_ex ;;
(* Q10 b : �crire une fonction qui supprime un �l�ment dans un ABR en conservant le structure d'ABR 
ATTENTION : faute de frappe sur le cours, avec valeur minimale, �changer gauche et droit ! *)
(* pr�condition : une �tiquette de l'arbre est �gale � c *)
(*On cherche à supprimer un élément dans un abr, en conservant la structure d'abr*)

(*Si la racine r est égale à la clé c, cela signifie que le nœud à supprimer est trouvé.
Il appelle la fonction supprime_cle_min sur le sous-arbre droit d pour trouver le nœud avec la clé minimale 
dans le sous-arbre droit, le supprime et remplace la racine par ce nœud. 
La fonction supprime_cle_min devrait renvoyer une paire (r1,d1) où r1 est la clé minimale 
et d1 est le sous-arbre droit après avoir supprimé le nœud avec la clé minimale.*)

(*Sinon, le noeud courant est plus grand que la valeur à enlever, alors on supprime récursivement dans le sous-fil gauche*)
(*Sinon, on fait la même chose dans le sous-fil droit*)
let rec supprime_cle (a:arbre) (c:int) : arbre = match a with
| Vide -> Vide
| Noeud(r,g,d) -> if r = c then let (r1,d1) = supprime_cle_min d in Noeud(r1,g,d1)
                  else if r > c then Noeud(r,supprime_cle g c,d)
                  else Noeud(r,g,supprime_cle d c)
;;
supprime_cle a_ex 150;;

(*On effectue un parcours en profondeur de l'arbre, en rajoutant la condition que si le sous - arbre gauche est vide, alors on ajoute à droite la feuille*)
let rec parcours_pro_inf_bis (a:arbre) :(int list) = match a with
| Vide -> []
| Noeud(r,Vide,d)-> (parcours_pro_inf_bis d) @ [r]
| Noeud(r,g,d) -> (parcours_pro_inf_bis g) @ [r] @ (parcours_pro_inf_bis d)
;;

parcours_pro_inf_bis a_ex;;