type 'a tree = Empty | Node of ('a tree)*'a*('a tree) ;; let vie = Node( Node(Empty,"miam",Empty),"dodo",Node(Node(Empty,"maths",Empty),"taff",Node(Empty,"info",Empty)) ) ;; let rec nb_noeuds = function | Empty -> 0 | Node(Empty,e,Empty) -> 0 | Node(f1,n,f2) -> (nb_noeuds f1) + 1 + (nb_noeuds f2) ;; let rec nb_feuilles = function | Empty -> 0 | Node(Empty,n,Empty) -> 1 | Node(f1,n,f2) -> (nb_feuilles f1) + (nb_feuilles f2) ;; let etiquette ar = let rec ss l1 = function | Empty -> l1 | Node(f1,et,f2) -> ss (et::(ss l1 f2)) f1 in (ss [] ar) ;; let rec profondeur = function | Empty -> 0 | Node(f1,n,f2) -> 1+ max (profondeur f1) (profondeur f2) ;; etiquette vie ;; let rec recherche x = function | Empty -> false | Node(f1,et,f2) when et=x -> true | Node(f1,et,f2) -> if et < x then recherche x f2 else recherche x f1 ;; (* en O(h) ou h est la profondeur *) let rec insere x = function | Empty -> Node(Empty,x,Empty) | Node(f1,et,f2) -> if et < x then Node(f1,et,insere x f2) else Node(insere x f1,et,f2) ;; (insere 2 (insere 1 Empty)) ;; (* on insere chaque element , on les affiche infixe ... le tri est en O(n*n) donc pas plus rapide que le tri par insertion *) let alea() = random__int 100000000;; let rec insere_mult = function | 0 -> Empty | n -> insere (alea()) (insere_mult (n-1)) ;; let big = insere_mult 1000;; profondeur big ;; nb_feuilles big ;; (* 42 *) vect_of_list [1;2;3];; let union_arbre ar1 ar2 = let rec merge = function | ([],l) -> l | (l,[]) -> l | (a::q,x::t) -> if a < x then a::(merge (q,x::t)) else x::(merge (a::q,t)) in let tab = vect_of_list (merge (etiquette ar1,etiquette ar2)) in let rec arborise i j = if j=i then Empty else begin let mil = (i+j)/2 in if mil = i then Node(Empty,tab.(i),Empty) else Node(arborise i mil , tab.(mil) , arborise (mil+1) j ) end in arborise 0 (vect_length tab) ;; etiquette (union_arbre (insere_mult 3) (insere_mult 3)) ;; let rec maxi = function | Empty -> 0 | Node(f1,n,f2) -> ( max n (max (maxi f1) (maxi f2) ) ) ;; let t = insere_mult 10 ;; let rec supprime x = function | Empty -> Empty | Node(Empty,n,Empty) when n=x -> Empty | Node(Empty,n,f2) when n=x -> f2 | Node(f1,n,f2) when n=x -> let m = maxi f1 in Node(supprime m f1,m,f1) | Node(f1,n,f2) -> if n > x then Node(supprime x f1,n,f2) else Node(f1,n,supprime x f2) ;; nb_noeuds t ;; maxi t ;; let tt = supprime (maxi t) t ;; maxi tt;; nb_noeuds tt;; ;; (* en profondeur *) exception non_rot ;; type 'a treap = Vide | Treap of 'a treap*(int*'a)*'a treap ;; let rot_d = function | Treap(Treap(a,x,b),p,c) -> Treap(a,x,Treap(b,p,c) ) | _ -> raise non_rot ;; let rot_g = function | Treap(a,x,Treap(b,p,c) ) -> Treap(Treap(a,x,b),p,c) | _ -> raise non_rot ;; let rec appartient x = function | Vide -> false | Treap(f1,(pr,et),f2) when et = x -> true | Treap(f1,(pr,et),f2) -> if et < x then appartient x f2 else appartient x f1 ;; let cote = function | Treap(Vide,n,Vide) -> 0 | Treap(Vide,n,_) -> -1 | Treap(_,n,Vide) -> 1 | Treap( Treap(_,(p1,e1),_) ,(p2,e2) , _ ) when p1 > p2 -> 1 | Treap( _ ,(p2,e2) , Treap(_,(p1,e1),_) ) when p1 > p2 -> (-1) | _ -> 0 ;; let valeur = function | Vide -> failwith "peut pas dire" | Treap(_,(p,e),_) -> e ;; let tr_remet tr = match cote tr with | 1 -> rot_d tr | -1 -> rot_g tr | _ -> tr ;; let rec tr_insere (p,x) = function | Vide -> Treap(Vide,(p,x),Vide) | Treap(f1,(pr,et),f2) -> let ret = if et >= x then Treap(tr_insere (p,x) f1,(pr,et),f2) else Treap(f1,(pr,et),tr_insere (p,x) f2) in tr_remet ret ;; let rec tr_suppr x = function | Vide -> Vide | Treap(f1,(pr,et),Vide) when et=x -> f1 | Treap(Vide,(pr,et),f2) when et=x -> f2 | Treap(Treap(g1,(p1,e1),d1),(pr,et),Treap(g2,(p2,e2),d2)) when et=x -> if p1 > p2 then Treap( tr_suppr e1 (Treap(g1,(p1,e1),d1)) , (p1,e1) ,Treap(g2,(p2,e2),d2) ) else Treap(Treap(g1,(p1,e1),d1) , (p2,e2) , tr_suppr e2 (Treap(g2,(p2,e2),d2)) ) | Treap(f1,(pr,et),f2) -> if et < x then Treap(f1,(pr,et),tr_suppr x f2) else Treap(tr_suppr x f1,(pr,et),f2) ;; let rec tr_mult = function | 0 -> Vide | n -> tr_insere (alea(),alea()) (tr_mult (n-1)) ;; let t = tr_mult 100 ;; tr_suppr 9445273 (tr_suppr 2476249 (tr_suppr 28120355 t)) ;; let rec tr_taille = function | Vide -> 0 | Treap(f1,_,f2) -> 1 + (taille f1) + (taille f2) ;; let split x t = match tr_insere ((1000*1000*1000),x) t with | Vide -> (Vide,Vide) | Treap(f1,m,f2) -> (f1,f2) ;; let (t1,t2) = split (50000000) t ;; t;; tr_taille t1 ;; t1 ;; tr_taille t2 ;; let rec tr_aff l = function | Vide -> l | Treap(g,(p,e),d) -> tr_aff (e::(tr_aff l d)) g ;; let rec tr_union = function | (Vide,b) -> b | (a,Vide) -> a | (Treap(g1,(p1,e1),d1) , Treap(g2,(p2,e2),d2) ) when p1 < p2 -> tr_union (Treap(g2,(p2,e2),d2),Treap(g1,(p1,e1),d1)) | (Treap(g,(p,e),d),b) -> let (b1,b2) = split e b in Treap ( tr_union (g,b1) , (p,e) , tr_union (d,b2) ) ;; let a1 = tr_mult 3 ;; tr_aff [] a1 ;; let a2 = tr_mult 3 ;; tr_aff [] a2 ;; tr_aff [] (tr_union (a1,a2)) ;;