Info_MPSI/TP4/tp4.ml

type arbre_bin =
|Vide
| Noeud of int*(arbre_bin)*(arbre_bin)
;;

let ex1 = Noeud(
  27,
  Noeud(
    12,
    Noeud(5,Vide,Vide),
    Noeud(
      19,
      Noeud(17,Vide,Vide),
      Noeud(
        24,
        Noeud(20,Vide,Vide),
        Noeud(26,Vide,Vide)
      )
    )
  ),
  Noeud(
    43,
    Noeud(36,Vide,Vide),
    Noeud(77,Vide,Vide)
  )
);;

type comparaison = Inf | Egal | Sup;;

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

let rec recherche a func x = match a with
| Vide -> false
| Noeud(n,g,d)->match func x n with
| Inf -> recherche g func x
| Egal -> true
| Sup -> recherche d func x
;;
(*

La taille des données dans un arbre binaire de recherche est définie comme le nombre total de nœuds dans l'arbre. Chaque nœud contient une étiquette et des références vers les sous-arbres gauche et droit. Donc, la taille des données est proportionnelle au nombre de nœuds dans l'arbre.

L'opération fondamentale dans l'algorithme de recherche est la comparaison entre la valeur recherchée et l'étiquette du nœud courant. Cette comparaison est réalisée en utilisant une fonction de comparaison qui détermine si la valeur est inférieure, égale ou supérieure à l'étiquette. En fonction du résultat de la comparaison, la recherche se poursuit dans le sous-arbre gauche, le sous-arbre droit ou le nœud courant est considéré comme correspondant.

La complexité de l'opération fondamentale de comparaison est généralement considérée comme constante, car elle ne dépend pas de la taille des données. Dans notre cas, la fonction compare_int compare simplement deux entiers et renvoie le résultat de la comparaison. Cette opération peut être réalisée en un temps constant.

Maintenant, considérons la complexité de la recherche dans l'arbre binaire de recherche. Dans le pire des cas, où l'arbre est dégénéré et prend la forme d'une liste chaînée, la hauteur de l'arbre est égale au nombre total de nœuds moins un, c'est-à-dire la taille des données moins un.

Dans ce pire des cas, la recherche doit parcourir chaque nœud de l'arbre pour atteindre le nœud cible. Comme la hauteur de l'arbre est proportionnelle à la taille des données, la complexité de la recherche devient O(taille des données), ce qui est équivalent à O(h), où h est la hauteur de l'arbre.

En conclusion, quelle que soit la structure de l'arbre binaire de recherche, la complexité de la recherche est O(h), où h est la hauteur de l'arbre. Cela signifie que le temps de recherche dans l'arbre est proportionnel à la hauteur de l'arbre et ne dépend pas directement de la taille totale des données dans l'arbre.
*)

(*a est un arbre de recherche dans tous les programmes suivants*)
let rec min_gauche_max_droit arbre =
  match arbre with
  | Vide -> failwith "L'arbre est vide."
  | Noeud(etiquette, Vide, _) -> (etiquette, etiquette)  (* Noeud le plus à gauche et le plus à droite *)
  | Noeud(etiquette, gauche, _) -> 
    let (min_gauche, max_droit) = min_gauche_max_droit gauche in
    (min_gauche, etiquette)  (* Noeud le plus à gauche de tout l'arbre, le noeud courant est le plus à droite *)
;;
let rec verifie_encadre arbre x y =
  match arbre with
  | Vide -> true
  | Noeud(etiquette, gauche, droit) ->
    if x <= etiquette && etiquette <= y then
      verifie_encadre gauche x y && verifie_encadre droit x y
    else
      false
;;

let verif_arbre_rech arbre =
  let (plus_a_gauche, plus_a_droite) = min_gauche_max_droit arbre in
  verifie_encadre arbre plus_a_gauche plus_a_droite
;;
type comparaison = Inf | Egal | Sup

let rec verif_tri liste func =
  match liste with
  | [] | [_] -> true  (* La liste vide ou avec un seul élément est toujours triée *)
  | x :: y :: rest ->
    match func x y with
    | Inf -> false
    | _ -> verif_tri (y :: rest) func
;;

let rec infixe arbre =
  match arbre with
  | Vide -> []
  | Noeud(etiquette, gauche, droit) -> (infixe gauche) @ [etiquette] @ (infixe droit)
;;

let verif_arb_rech2 arbre func =
  let etiquettes = infixe arbre in
  verif_tri etiquettes func
;;

let rec insere_feuille arbre func nouvel_element =
  match arbre with
  | Vide -> Noeud(nouvel_element, Vide, Vide)  (* Place le nouvel élément sur une branche vide *)
  | Noeud(etiquette, gauche, droit) ->
    match func nouvel_element etiquette with
    | Inf -> Noeud(etiquette, insere_feuille gauche func nouvel_element, droit)  (* Insère à gauche *)
    | Egal -> arbre  (* L'élément est déjà présent, renvoie l'arbre inchangé *)
    | Sup -> Noeud(etiquette, gauche, insere_feuille droit func nouvel_element)  (* Insère à droite *)
;;

let insere_racine arbre func nouvel_element =
  match arbre with
  | Vide -> Noeud(nouvel_element, Vide, Vide)  (* Crée un nouvel arbre avec le nouvel élément comme racine *)
  | Noeud(etiquette, gauche, droit) ->
    match func nouvel_element etiquette with
    | Inf -> Noeud(etiquette, insere_feuille gauche func nouvel_element, droit)  (* Insère le nouvel élément à gauche de l'arbre existant *)
    | Egal -> arbre  (* L'élément est déjà présent, renvoie l'arbre inchangé *)
    | Sup -> Noeud(etiquette, gauche, insere_feuille droit func nouvel_element)  (* Insère le nouvel élément à droite de l'arbre existant *)
;;

let rec construction_feuille liste func =
  match liste with
  | [] -> Vide  (* Cas de correspondance avec une liste vide, renvoie un arbre vide *)
  | x :: rest -> insere_feuille (construction_feuille rest func) func x
;;


let rec construction_racine liste func =
  match liste with
  | [] -> Vide  (* Cas de correspondance avec une liste vide, renvoie un arbre vide *)
  | x :: rest -> insere_racine (construction_racine rest func) func x
;;


let liste_ex1 = [1;2;3;4;5;6;7;8;9];;
let liste_ex2 = [1;3;5;7;9;8;6;4;2];;

let rotation_gauche arbre =
  match arbre with
  | Noeud(racine, Vide, droit) ->
    (match droit with
    | Noeud(etiquette_droit, sous_arbre_gauche, sous_arbre_droit) ->
      Noeud(etiquette_droit, Noeud(racine, Vide, sous_arbre_gauche), sous_arbre_droit)
    | _ -> arbre)  (* Pas de rotation possible, renvoie l'arbre inchangé *)
  | _ -> arbre  (* Pas de rotation possible, renvoie l'arbre inchangé *)
;;

let rotation_droite arbre =
  match arbre with
  | Noeud(racine, gauche, Vide) ->
    (match gauche with
    | Noeud(etiquette_gauche, sous_arbre_gauche, sous_arbre_droit) ->
      Noeud(etiquette_gauche, sous_arbre_gauche, Noeud(racine, sous_arbre_droit, Vide))
    | _ -> arbre)  (* Pas de rotation possible, renvoie l'arbre inchangé *)
  | _ -> arbre  (* Pas de rotation possible, renvoie l'arbre inchangé *)
;;


let rec mystere a1 a2 func =
  | _,Vide -> a1
  | Vide,_ -> a2
  | Noeud(e1,ag1,ad1), Noeud(e2, ag2,ad1) when compare e1 e2 = Inf
    -> mystere ad1 (Noeud(e2,mystere Noeud(e1,ag1,Vide) ag2 func, ad2)) func
  | Noeud(e1,ag1,ad1), Noeud(e2,ag2,ad2)
    -> mystere ag1 (Noeud(e2,ag2,mystere Noeud(e1,Vide,ad1) ad2 func)) func
;;

(* Il s'agit d'une fonction de concatenation pour 2 arbres de recherche*)