TP 09/06/2021 Avec clémmmmm

ocaml_bintree_search.ml

type 'a binaryTree =
	| None
	| Node of ('a binaryTree)*'a*('a binaryTree)
;;

let tree1 = Node(
	Node(
		Node(None, 5, None),
		12,
		Node(
			Node(None, 17, None),
			19,
			Node(
				Node(None, 20, None),
				24,
				Node(None, 26, None)
			)
		)
	),
	27,
	Node(
		Node(None, 36, None),
		43,
		Node(None, 77, None)
	)
);;

open Graphics;;
#load "graphics.cma";;

let draw_tree tree =
	Graphics.open_graph "1000x1000";
	Graphics.clear_graph ();
	Graphics.set_color Graphics.black;
	Graphics.fill_rect 0 0 1000 1000;

	let rec aux subTree x y i = match subTree with
		| None -> ()
		| Node(left, la, right) -> (
			Graphics.moveto (x) (y);
			(if left != None then (
				Graphics.moveto (x-3) (y-5);
				let toX = x-(i/2) and toY = (y-100) in
	 			Graphics.set_color Graphics.white;
				Graphics.lineto (toX+5) (toY+10);
				aux left toX toY (i/2);
			));
			(if right != None then (
				let toX = x+(i/2) and toY = (y-100) in
				Graphics.moveto (x+9) (y-5);
	 			Graphics.set_color Graphics.white;
				Graphics.lineto (toX+5) (toY+10);
				aux right toX toY (i/2);
			));
			Graphics.set_color Graphics.white;
			Graphics.fill_circle (x+5) (y+5) 17;
			Graphics.set_color Graphics.black;
			Graphics.fill_circle (x+5) (y+5) 15;
			let label = (string_of_int la) in
			Graphics.moveto (x-(if la >= 10 then 3 else 0)) (y-(if la >= 10 then 2 else 1));
			Graphics.set_color Graphics.white;
			Graphics.draw_string label;

		)
	in
	(aux tree 500 800 500);;
(*
Graphics.moveto 0 480;;
Graphics.draw_string "hello, world!";;
*)
draw_tree tree1;;

type comparaison = Inf | Egal | Sup;;

let compare_int x y = if x<y then Inf else if x=y then Egal else Sup;;

(* Vérifie si x est dans l'arbre de recherche *)
let rec recherche tree x comp = match tree with
	| None -> false
	| Node(left, e, right) -> 
		match (comp x e)  with
		| Egal -> true
		| Inf -> recherche left x comp
	   | Sup -> recherche right x comp
	  ;;

recherche tree1 15 compare_int;;

let rec min_gauche_max_droit tree = match tree with
	| None -> failwith "Message d'erreur ptdr"
	| Node(None, e, None) -> (e, e)
	| Node(left, e, None) -> (fst (min_gauche_max_droit left), e)
	| Node(None, e, right) -> (e, snd (min_gauche_max_droit right))
	| Node(left, e, right) ->  (fst (min_gauche_max_droit left), snd (min_gauche_max_droit right))
	;;
min_gauche_max_droit tree1;;

let rec verif_arb_rech tree = match tree with
	| None -> failwith "Message d'erreur ptdr"
	| Node(None, e, None) -> (e, e)
	| Node(left, e, None) -> (fst (min_gauche_max_droit left), e)
	| Node(None, e, right) -> (e, snd (min_gauche_max_droit right))
	| Node(left, e, right) ->  (fst (min_gauche_max_droit left), snd (min_gauche_max_droit right))
	;;

(* VERSION PAS OPTI *)
let rec verif_arb_rech tree comp = match tree with
	| None -> failwith "Coup dur, tu n'a pas pu gifler macron"
	| Node(None, e, None) -> true
	| Node(left, e, right) -> (
		 (verif_arb_rech left comp) &&
		 (verif_arb_rech right comp) &&
		 (comp e (snd (min_gauche_max_droit left))) == Sup &&
		 (comp e (snd (min_gauche_max_droit right))) == Inf
	 )
	(* MONTJOIE SAINT DENIS!!!! le plus à droite de l'elem gauche doit être plus
	 petit que la racine et la racine doit être inf que l'elem le plus à droite  *)
;;

verif_arb_rech tree1 compare_int;;

(* VERSION UN PEU + OPTI *)
let isSearch tree comp = 
	let rec aux tree = match tree with
		| None -> failwith "Coup dur"
		| Node(None, e, None) -> (e, e, true)
		| Node(left, e, None) -> (
			let (min, max, isSearch) = (aux left) in
			(min, e, isSearch && ((comp e min) = Egal || (comp e min) = Inf))
	 	 )
		| Node(None, e, right) -> (
			let (min, max, isSearch) = (aux right) in
			(min, e, isSearch && ((comp e max) = Egal || (comp e max) = Sup))
	 	 )
		| Node(left, e, right) -> (
			let (minL, maxL, isSearchL) = (aux left) in
			let (minR, maxR, isSearchR) = (aux right) in
			(
				minL, maxR,
				isSearchL && isSearchR && (
					(comp e maxL = Sup || comp e maxL = Egal) &&
   				(comp e minR = Inf || comp e minR = Egal)
				)
			)
		)
		in
	aux tree
;;

isSearch tree1 compare_int;;

(* Question 4, Deuxième méthode *)

let rec verif_tri liste comp = 
	match liste with
	| [] -> true
	| [a] -> true
	| a::b::reste -> ((comp a b) == Inf || (comp a b) == Egal) && (verif_tri (b::reste) comp)
	;;


verif_tri [ -2; -1; 0; 2; 10; 50; 52 ] compare_int;;

let rec infixe bt = match bt with
		| None -> []
		| Node(left, x, right) -> 
			(infixe left)@[x]@(infixe right)
		;;

let verif_2 arbre comp = 
	let i = infixe arbre in
	verif_tri i comp;;
	
verif_2 (Node(Node(None, 12, None), 2, None)) compare_int;;
		
(* DS: Exo complexité  plutot simple comment calculer l'odre de grandeur complexit et autre  exo sur les arbre *)