Info_MPSI/MP/concours/Deuxieme annee/abr.ml

type 'a avl = Vide | Noeud of 'a * int * 'a avl * 'a avl;;

type 'a arbre = Vide | Noeud of 'a * 'a arbre * 'a arbre;;

let rec max_arbre a = match a with
| Vide -> 0
| Noeud(r,Vide,Vide) -> r
| Noeud(r,g,d) -> max (max (max_arbre g) (max_arbre d)) r;;

let rec min_arbre a = match a with
| Vide -> 0
| Noeud(r,Vide,Vide) -> r
| Noeud(r,g,d) -> min (min (min_arbre g) (min_arbre d)) r;;

let rec test_abr a = match a with
| Vide -> true
| Noeud(r,Vide,Vide) -> true
| Noeud(r,Vide,d) -> (r <= min_arbre d) && (test_abr d)
| Noeud(r,g,Vide) -> (r >= max_arbre g) && (test_abr g)
| Noeud(r,g,d) -> (r >= max_arbre g) && (r <= min_arbre d) && (test_abr g) && (test_abr d);;

(*Parcours en profondeur en mode infixe d'un ABR*)
let rec parcours_profondeur_infixe a = match a with
| Vide -> []
| Noeud(r,g,d) -> (parcours_profondeur_infixe g) @ [r] @ (parcours_profondeur_infixe d);;

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

let rec etiquette_max a = match a with
| Vide -> failwith "Erreur"
| Noeud(r,Vide,Vide) -> r
| Noeud(r,g,d) -> etiquette_max d;;

let rec etiquette_min a = match a with
| Vide -> failwith "Erreur"
| Noeud(r,Vide,Vide) -> r
| Noeud(r,g,d) -> etiquette_min g;;

let rec etiquette_predecesseur a k = match a with
| Vide -> failwith "Erreur"
| Noeud(r,g,d) -> if r = k then 
  etiquette_max g 
else if r < k then 
  etiquette_predecesseur d k 
else etiquette_predecesseur g k;;

let rec etiquette_successeur a k = match a with
| Vide -> failwith "Erreur"
| Noeud(r,g,d) -> if r = k then 
  etiquette_min d 
else if r < k then 
  etiquette_successeur d k 
else etiquette_successeur g k;;

let rec insertion_feuille a k = match a with
| Vide -> Noeud(k,Vide,Vide)
| Noeud(r,g,d) -> if r = k then 
  a 
else if r < k then 
  Noeud(r,g,(insertion_feuille d k)) 
else Noeud(r,(insertion_feuille g k),d);;

let rec partition a k = match a with
| Vide -> (Vide,Vide)
| Noeud(r,g,d) -> if r < k then 
  let (g1,d1) = partition d k in 
  (Noeud(r,g,g1),d1) 
else let (g1,d1) = partition g k in 
( g1,Noeud(r,d1,d));;

(*Inserer la nouvelle racine k grâce à la fonction partition*)
let rec insertion_racine a k = match a with
| Vide -> Noeud(k,Vide,Vide)
| Noeud(r,g,d) -> let (g1,d1) = partition a k in
Noeud(k,g1,d1);;

let rec supprime_etiquette_min a = match a with
| Vide -> failwith "Erreur"
| Noeud(r,Vide,Vide) -> Vide
| Noeud(r,g,d) -> Noeud(r,supprime_etiquette_min g,d);;

(*Supprime l'étiquette k dans a utilisant la fonction supprime_etiquette_min*)
let rec supprime_etiquette a k = match a with
| Vide -> Vide
| Noeud(r,g,d) -> if r = k then 
  if g = Vide then d else if d = Vide then g else Noeud(etiquette_min d,g,supprime_etiquette_min d) 
else if r < k then 
  Noeud(r,g,(supprime_etiquette d k)) 
else Noeud(r,(supprime_etiquette g k),d);;