Info_MPSI/MP/JALLAT_DS2.ml

type ensemble = int list;;

(*Insérer dans un ensemble*)

let rec insere x (e:ensemble) = match e with
| [] -> [x]
| t::q -> if t=x then e else t::(insere x q);;

(*Evaluation de la complexité, en fonction du nombre d'éléments de E, ne prendra en compte*)
(*que le nombre d'appels récursifs*)
(*Complexité linéaire*)

(*Recherche dans un ensemble*)
let rec recherche x (e:ensemble) = match e with
| [] -> false
| t::q -> if t=x then true else recherche x q;;

(*Exemples de valeurs pour x et e, tels que l'on soit dans le pire ou le meilleur des cas*)
(*x = 1, e = [1;2;3;4;5;6;7;8;9;10]*)
(*x = 11, e = [1;2;3;4;5;6;7;8;9;10]*)

(*Complexité linéaire*)

(*Nous travaillons avec des arbres binaires entiers*)

(*Profondeur d'un arbre avec la profondeur du sous-arbre gauche, noté G, et la profondeur du sous-arbre*)
(*droit, noté D*)
(*Si l'arbre est l'arbre vide, alors sa profondeur est de zéro*)
(*Sinon, c'est le maximum entre la profondeur du sous-arbre gauche et celle du droit, +1*)


(*On définit un arbre binaire d'entiers, par le déséquilibre du noeud, son sous-fil gauche, l'étiquette associé*)
(*à la racine, puis le sous-fil droit*)
type arbre = Vide | Noeud of int * arbre * int * arbre;;

let ex1 = Noeud(0,
Noeud(-1,
Vide,
9,
Noeud(0,Vide,6,Vide)),
7,
Noeud(1,
Noeud(0,Vide,3,Vide),
8,
Vide));;
(*Troisième arbre de l'exemple II.3*)
let ex3 = Noeud(-1, Noeud(0, Noeud(0, Vide, 1, Vide), 3, Noeud(0,Vide,4,Vide)), 6, 
Noeud(1,Noeud(-1,Vide,7,Noeud(0,Vide,8,Vide)),9,Noeud(0,Vide,10,Vide)));;

let rec profondeur a = match a with
| Vide -> 0
| Noeud(_,g,_,d) -> 1 + max (profondeur g) (profondeur d);;

profondeur ex1;;

let rec valider_decoration a = match a with
| Vide -> true
| Noeud(deco,g,_,d) -> ((profondeur g) - (profondeur d)) = deco && valider_decoration g && valider_decoration d;;
;;

valider_decoration ex1;;

(*Estimation de la complexité, en fonction du nombre d'appels récursifs*)

(*Complexité logarithmique*)

(*On considère des arbres binaires de recherche*)

(*Je crée une fonction auxiliaire racine, ce qui me permet d'observer la racine des sous-arbres*)
(*On considère des entiers naturels strictement positifs, donc Vide ne renvoit rien*)
let rec racine a = match a with
| Vide -> failwith "Arbre vide"
| Noeud(_,g,e,d) -> e;;

racine ex1;;
racine ex3;;

let rec valider_abr a = match a with
| Vide -> true
| Noeud(_,Vide,_,Vide) -> true
| Noeud(_,Vide,_,d) -> (racine d) > (racine a) && valider_abr d
| Noeud(_,g,_,Vide) -> (racine g) < (racine a) && valider_abr g
| Noeud(_,g,_,d) -> (racine g) < (racine a) && (racine d) > (racine a) && valider_abr g && valider_abr d;;

valider_abr ex3;;

let rec recherche_abr x a = match a with
| Vide -> false
| Noeud(_,g,e,d) -> if x=e then true else if x<e then recherche_abr x g else recherche_abr x d;;

recherche_abr 1 ex3;;

(*Exemples de valeurs de paramètres de x et a pour les meilleurs et pires cas*)
(*x = 6, a = ex3*)
(*x = 11, a = ex3*)

(*Evaluation de la complexité, en fonction du nombre d'appels récursifs*)

(*Complexité logarithmique*)

(*Insertion dans un ABR*)
(*Cette fonction doit calculer le nouveau déséquilibre pour les noeuds où il change*)
let rec insere_abr x a = match a with
| Vide -> Noeud(0,Vide,x,Vide)
| Noeud(deco,g,e,d) -> if x=e then a else if x<e then Noeud(deco+1,insere_abr x g,e,d) else Noeud(deco-1,g,e,insere_abr x d);;

insere_abr 11 ex3;;

(*Exemples de valeurs de paramètres de x et a pour les meilleurs et pires cas*)
(*x = 6, a = ex3*)
(*x = 11, a = ex3*)

(*Evaluation de la complexité, en fonction du nombre d'appels récursifs*)

(*Complexité logarithmique*)

(*Rotations d'un ABR*)

(*Rotation simple de type D*)
let rec rotationSD a = match a with
| Vide -> failwith "Arbre vide"
| Noeud(_,Vide,_,_) -> failwith "Rotation impossible"
| Noeud(_,Noeud(_,Vide,_,_),_,_) -> failwith "Rotation impossible"
| Noeud(_,Noeud(_,Noeud(_,Vide,_,_),_,_),_,_) -> failwith "Rotation impossible"
| Noeud(_,Noeud(_,Noeud(_,g1,e1,d1),e2,d2),e3,d3) -> Noeud(0,g1,e1,Noeud(0,d1,e2,Noeud(0,d2,e3,d3)));;

(*Rotation simple de type G*)
let rec rotationSG a = match a with
| Vide -> failwith "Arbre vide"
| Noeud(_,_,_,Vide) -> failwith "Rotation impossible"
| Noeud(_,_,_,Noeud(_,_,_,Vide)) -> failwith "Rotation impossible"
| Noeud(_,_,_,Noeud(_,_,_,Noeud(_,_,_,Vide))) -> failwith "Rotation impossible"
| Noeud(_,g3,e3,Noeud(_,g2,e2,Noeud(_,g1,e1,d1))) -> Noeud(0,Noeud(0,Noeud(0,g3,e3,g2),e2,g1),e1,d1);;

(*Rotation double de type D*)
let rec rotationDD a = match a with
| Vide -> failwith "Arbre vide"
| Noeud(_,Vide,_,_) -> failwith "Rotation impossible"
| Noeud(_,Noeud(_,Vide,_,_),_,_) -> failwith "Rotation impossible"
| Noeud(_,Noeud(_,Noeud(_,Vide,_,_),_,_),_,_) -> failwith "Rotation impossible"
| Noeud(_,Noeud(_,Noeud(_,g1,e1,d1),e2,d2),e3,d3) -> Noeud(0,Noeud(0,g1,e1,Noeud(0,d1,e2,d2)),e3,d3);;

(*Rotation double de type G*)
let rec rotationDG a = match a with
| Vide -> failwith "Arbre vide"
| Noeud(_,_,_,Vide) -> failwith "Rotation impossible"
| Noeud(_,_,_,Noeud(_,_,_,Vide)) -> failwith "Rotation impossible"
| Noeud(_,_,_,Noeud(_,_,_,Noeud(_,_,_,Vide))) -> failwith "Rotation impossible"
| Noeud(_,g3,e3,Noeud(_,g2,e2,Noeud(_,g1,e1,d1))) -> Noeud(0,Noeud(0,g3,e3,Noeud(0,g2,e2,d1)),e1,d1);;


(*On considère des arbres qui sont en plus équilibrés*)
(*Donner les différentes formes possibles pour le noeud déséquilibré le plus profond produit lors de*)
(*l'insertion d'une nouvelle étiquette dans un arbre binaire équilibré en précisant la valeur du déséquilibre*)
(*de ce noeud*)


(*Equilibrage d'un arbre*)
(*equilibrage a, a un abr dont la racine est déséquilibré, mais dont les sous-fils sont équilibrés*)

let equilibrage a = match a with
| Vide -> failwith "Arbre vide"
| Noeud(_,Vide,_,_) -> failwith "Arbre équilibré"
| Noeud(_,Noeud(_,Vide,_,_),_,_) -> failwith "Arbre équilibré"
| Noeud(_,Noeud(_,Noeud(_,Vide,_,_),_,_),_,_) -> failwith "Arbre équilibré"
| Noeud(_,Noeud(_,Noeud(_,g1,e1,d1),e2,d2),e3,d3) -> if (profondeur g1) > (profondeur d1) then rotationSD a else rotationDD a;;

equilibrage ex3;;

(*Insertion dans un ABR équilibré*)
(*On réequilibre à chaque fois*)
let rec insere_abr_equilibre x a = match a with
| Vide -> Noeud(0,Vide,x,Vide)
| Noeud(deco,g,e,d) -> if x=e then a 
            else if x<e then equilibrage (Noeud(deco+1,insere_abr_equilibre x g,e,d)) 
            else equilibrage (Noeud(deco-1,g,e,insere_abr_equilibre x d));;