(* Correction du TP 4 : Structures arborescentes *) (**************) (*** Oups ! ***) (**************) (* Question 1 *) type 'a arbre = Vide | Noeud of 'a * 'a arbre * 'a arbre;; (* Il manquait le cas de base, le constructeur de l'arbre Vide *) (*****************************************************) (*** Introduction aux arbres binaires de recherche ***) (*****************************************************) (* ABR exemple *) let perdu = Noeud(15, Noeud(4, Vide, Noeud(8, Vide, Vide)), Noeud(23, Noeud(16, Vide, Vide), Noeud(42, Vide, Vide)));; (* Question 2 *) let rec arbre_taille t = match t with | Vide -> 0 | Noeud(_,l,r) -> 1 + arbre_taille l + arbre_taille r;; let rec arbre_hauteur t = match t with | Vide -> 0 | Noeud(_,l,r) -> 1 + max (arbre_hauteur l) (arbre_hauteur r);; (* Versions récursives terminales *) let arbre_taille_tr t = let rec aux t l a = match t, l with | Vide, [] -> a | Vide, h::t -> aux h t a | Noeud(_,g,d), _ -> aux g (d::l) (a+1) in aux t [] 0;; let arbre_hauteur_tr t = let rec aux t c l a = match t, l with | Vide, [] -> max c a | Vide, (ah, h)::t -> aux h ah t (max a c) | Noeud(_,g,d), _ -> aux g (c+1) ((c+1, d)::l) a in aux t 0 [] 0;; (* Question 3 *) let infixe t = let rec aux t al a = match t, al with | Vide, [] -> rev a | Vide, Vide::t -> aux Vide t a | Vide, Noeud(v,_,r)::t -> aux r t (v::a) | Noeud(_,l,_) as n, _ -> aux l (n::al) a in aux t [] [];; (* Cette fonction étant linéaire, on va pouvoir en abuser par la suite. *) (* Question 4 *) let rec chercher_abr t v = match t with | Vide -> false | Noeud(x,g,d) -> if v=x then true else chercher_abr (if v true | Some mi, None -> x>=mi | None, Some ma -> x<=ma | Some mi, Some ma -> x>=mi && x<=ma in match t with | Vide -> true | Noeud(x,g,d) -> if verifier x then aux g mini (Some x) && aux d (Some x) maxi else false in aux t None None;; (* Seconde version: abus de la fonction infixe. *) let verifier_abr t = let rec est_trie l = match l with | h1::(h2::_ as t) -> if h1

true | [] -> true in est_trie (infixe t);; (* Question 6 *) let rec ajouter_abr t v = match t with | Vide -> Noeud(v, Vide, Vide) | Noeud(x,l,r) -> if v x,l | Noeud(x,l,r) -> let m,nr = supprimer_maximum r in m,Noeud(x, l, nr) | Vide -> failwith "Impossible" in match t with | Vide -> failwith "La valeur n'est pas dans l'arbre." | Noeud(x,l,r) -> if xv then Noeud(x,supprimer_abr l v,r) else if l=Vide then r else let m,nl=supprimer_maximum l in Noeud(m, nl, r);; (***************) (*** Tas-max ***) (***************) type 'a tas == 'a vect * int ref;; (* Question 9 *) type echange = Gauche | Droite | Aucun;; let tamiser (tv, tn) ind = let swap a b = let tmp = tv.(a) in begin tv.(a) <- tv.(b); tv.(b) <- tmp end in let ech = if 2*ind+2< !tn && tv.(2*ind+1)>tv.(ind) && tv.(2*ind+2)>tv.(ind) then if tv.(2*ind+1)>tv.(2*ind+2) then Gauche else Droite else if 2*ind+1< !tn && tv.(2*ind+1)>tv.(ind) then Gauche else if 2*ind+2< !tn && tv.(2*ind+2)>tv.(ind) then Droite else Aucun in begin if ech!=Aucun then swap ind (2*ind + if ech=Gauche then 1 else 2); ech end;; (* Question 10 *) let rec tamiser_branche tas ind = match tamiser tas ind with | Aucun -> () | Gauche -> tamiser_branche tas (2*ind+1) | Droite -> tamiser_branche tas (2*ind+2);; (* Question 11 *) let entasser v = let n=vect_length v in let tas=(v, ref n) in begin for i=n-1 downto 0 do tamiser_branche tas i done; tas end;; (* Question 12 *) let ajouter_tas (tv, tn) v = let rec tamis_renv i = begin tamiser (tv, tn) i; if i<>0 then tamis_renv ((i-1)/2) end in begin tv.(!tn) <- v; incr tn; tamis_renv ((!tn - 2)/2); () end;; (* Question 13 *) let extraire_tas (tv,tn) = let m = tv.(0) in begin decr tn; tv.(0) <- tv.(!tn); tamiser_branche (tv, tn) 0; m end;; (* Question 14 *) let tri_tas l = let s=ref [] in let tas = entasser (vect_of_list l) in begin for i=1 to (list_length l) do s := extraire_tas tas :: !s done; !s end;; (* Il est possible d'écrire entasser pour qu'il ait une complexité O(n), toute * fois, la fonction extraire_tas est en O(log n), ce tri est donc en O(n log n) *) (* Question 16 *) (* On peut équilibrer un ABR à l'aide d'un tas (c'est ce que l'on appelle un Treap) * - À chaque clef insérée on ajoute une valeur aléatoire * - On a un arbre de paire (clef, rnd), on utilise les algorithmes sur les tas * pour faire en sorte que les rnds forment un tas et les algorithmes sur les * ABR pour faire en sorte que les clefs forment un ABR. *)