Info_MPSI/test2/dm2.ml

type arbre_bin =
  | Vide
  | Noeud of int * arbre_bin * arbre_bin
;;
let bornesup = 1000000;;
let borneinf = -1000000;;

let ex1 =
  Noeud (
    34,
    Noeud (
      30,
      Noeud (18, Noeud (10, Vide, Vide), Noeud (8, Vide, Vide)),
      Noeud (20, Noeud (11, Vide, Vide), Noeud (14, Vide, Vide))
    ),
    Noeud (32, Noeud (30, Vide, Vide), Noeud (26, Vide, Vide))
  )
;;

let etiquette f =
  match f with
  | Vide -> failwith "rien"
  | Noeud (n, _, _) -> n
;;

let rec test_file f =
  match f with
  | Vide -> true
  | Noeud (n, g, d) ->
      if
        n >= etiquette g
        && n >= etiquette d
        && test_file g
        && test_file d
      then
        true
      else
        false
;;

let rec echange_etiquette f x = match f with
| Vide -> Vide
| Noeud(_,g,d)->Noeud(x,g,d)
;;

let rec percolation arbre =
  match arbre with
  | Vide -> Vide
  | Noeud (n, Vide, Vide) -> Noeud (n, Vide, Vide)
  | Noeud (n, g, d) ->
      let plus_grand_fils =
        if etiquette g >= etiquette d then
          g
        else
          d
      in
      if etiquette plus_grand_fils > n then
        Noeud (etiquette plus_grand_fils, percolation (echange_etiquette g n), d)
      else
        Noeud (n, percolation g, d)
;;

let rec supp_feuille arbre =
  match arbre with
  | Vide -> failwith "Impossible de supprimer une feuille d'un arbre vide"
  | Noeud (n, Vide, Vide) -> Vide, n
  | Noeud (n, g, Vide) ->
      let nouveau_g, feuille_supprimee = supp_feuille g in
      Noeud (n, nouveau_g, Vide), feuille_supprimee
  | Noeud (n, Vide, d) ->
      let nouveau_d, feuille_supprimee = supp_feuille d in
      Noeud (n, Vide, nouveau_d), feuille_supprimee
  | Noeud (n, g, d) ->
      let nouveau_g, feuille_supprimee = supp_feuille g in
      Noeud (n, nouveau_g, d), feuille_supprimee
;;

let supp_racine arbre =
  match arbre with
  | Vide -> failwith "Impossible de supprimer la racine d'un arbre vide"
  | Noeud (n, gauche, droit) ->
      let nouvel_arbre = echange_etiquette arbre (etiquette (fst (supp_feuille arbre))) in
      percolation nouvel_arbre
;;

let rec insere x arbre = match arbre with
| Vide -> Noeud(x,Vide,Vide)
| Noeud(r,g,d)-> if x > r then 
  begin
    let rand = Random.int 2 in
    if rand = 0 then Noeud(x,insere r g,d)
    else Noeud(x,g,insere r d)
  end
else
  begin
    let rand = Random.int 2 in
    if rand = 0 then Noeud(r,insere x g,d)
    else Noeud(r,g,insere x d)
  end
;;

let rec file_of_liste l = match l with
| [] -> Vide
| t::q-> insere t (file_of_liste q)
;;

let rec arbre_de_tas_aux i tas = match i>= Array.length tas with
| true -> Vide
| false -> 
  let x = tas.(i) in
  let sous_arbre_gauche = arbre_de_tas_aux (2*i +1) tas in
  let sous_arbre_droite = arbre_de_tas_aux (2*i + 2) tas in
  Noeud(x,sous_arbre_gauche,sous_arbre_droite)
;;

let arbre_de_tas tas = arbre_de_tas_aux 0 tas;;

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


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


let rec tas_d_arbre_aux i arbre tas =
    match arbre with
    | Vide -> ()
    | Noeud(x, g, d) ->
      tas.(i) <- x;
      tas_d_arbre_aux (2 * i + 1) g tas;
      tas_d_arbre_aux (2 * i + 2) d tas
;;


let tas_d_arbre arbre =
  let n = taille arbre in
  let tas = Array.make n 0 in
  tas_d_arbre_aux 0 arbre tas;
;;

let est_valide_valeur v gauche droite n tas =
  if gauche < n && tas.(gauche) > v then
    false
  else if droite < n && tas.(droite) > v then
    false
  else
    true
;;

let rec est_tas i n tas =
  if i >= n then
    true
  else
    let gauche = 2 * i + 1 in
    let droite = 2 * i + 2 in
    let v = tas.(i) in
    est_valide_valeur v gauche droite n tas && est_tas gauche n tas && est_tas droite n tas
;;

let verification_tas tas =
  let n = Array.length tas in
  est_tas 0 n tas
;;

let echange t i j =
  let aux = t.(i) in
  t.(i)<-t.(j);
  t.(j)<-aux
;;

let rec remonter_aux i t =
  if i = 0 || t.(i) <= t.((i - 1) / 2) then
    ()
  else
    let parent = (i - 1) / 2 in
    let temp = t.(i) in
    t.(i) <- t.(parent);
    t.(parent) <- temp;
    remonter_aux parent t
;;

let remonter n t =
  remonter_aux n t
;;

let insertion x t =
  let n = Array.length t in
  t.(n)<-x;
  remonter n t;
;;

let creation_tab t = 
  let resultat = Array.make 100 (-1) in
  for i = 0 to Array.length t -1 do
    insertion t.(i) resultat
  done;
;;

let fils_max k t =
  let fg = 2 * k + 1 in
  let fd = 2 * k + 2 in
  let n = Array.length t in
  if fg < n && fd < n then
    if t.(fg) > t.(fd) then
      fg
    else
      fd
  else if fg < n then
    fg
  else
    k
;;

let rec descente_aux k n t=
    let max_child_index = fils_max k t in
    if max_child_index < n && t.(max_child_index) > t.(k) then
      begin
        let temp = t.(k) in
        t.(k) <- t.(max_child_index);
        t.(max_child_index) <- temp;
        descente_aux max_child_index n t
      end
;;

let descente t =
  let n = Array.length t in
  descente_aux 0 n t
;;

let suppression t =
  let n = Array.length t in
  if n > 0 then begin
    t.(0) <- t.(n - 1);
    descente (Array.sub t 0 (n - 1))
  end
;;

let tri_tas t =
  let n = Array.length t in
  let resultat = Array.make n 0 in

  for i = 0 to n - 1 do
    insertion t.(i) resultat
  done;

  for i = 0 to n - 1 do
    suppression resultat
  done;

  for i = 0 to n - 1 do
    t.(i) <- resultat.(i)
  done
;;