type 'a tree = Empty | Node of ('a tree) * 'a *('a tree) ;; let rec noeuds = function | Node(a,_,b) -> 1 + (noeuds a) + (noeuds b) | Empty -> 0 let rec feuilles = function | Node(a,_,b) -> max 1 ((feuilles a) + (feuilles b)) | Empty -> 0 ;; let rec hauteur = function | Empty -> 0 | Node(a,_,b) -> max (hauteur a) (hauteur b) ;; let exemple = (Node(Node(Empty,(),Empty),(),Empty)) ;; noeuds exemple ;; let etiquettes t = let rec aux l = function | Empty -> l | Node(a,k,b) -> aux (k::(aux l b)) a in aux [] t ;; etiquettes exemple ;; let rec est_dans x = function | Empty -> false | Node(a,k,b) -> if x Node(Empty,x,Empty) | Node(a,k,b) -> if x insere x t) Empty l) ;; tri [6;7;1;2;4;1;5;3];; let unit t1 t2 = it_list (fun t x -> insere x t) t1 (etiquettes t2) ;; let rec extrait_min = function | Empty -> failwith "Wut?" | Node(Empty,k,b) -> (k,b) | Node(a,k,b) -> let m,t = extrait_min b in (m,Node(a,k,t)) ;; let rec supprime x = function | Empty -> failwith "Wut?" | Node(a,k,b) when k<>x -> if x < k then Node(supprime x a,k, b) else Node(a,k,supprime x b) | Node(a,k,Empty) -> a | Node(a,k,b) -> let m,t = extrait_min b in Node(a,m,t) ;; exemple;; supprime () exemple;; let rotg = function | Node(a,x,Node(b,p,c)) -> Node(Node(a,x,b),p,c) | _ -> failwith "rotg impossible" let rotd = function | Node(Node(a,x,b),p,c) -> Node(a,x,Node(b,p,c)) | _ -> failwith "rotd impossible" ;; type 'a treap == ('a*int) tree;; let rec est_dans_treap x = function | Empty -> false | Node(a,(k,p),b) -> if(x true | Node(_,(_,k),_) -> k<=x let tamise t = match t with | Empty -> Empty | Node(a,(k,p),b) -> if not respecte p a then rotd t else if not respecte p b then rotg t else t let rec insere x = function | Empty -> Node(Empty,(x,random__int 100000000),Empty) | Node(a,(k,p),b) -> tamise (if x < k then Node(insere x a,(k,p),b) else Node(a,(k,p),insere x b)) letlet split x t = match tr_insere ((1000*1000*1000),x) t with | Vide -> (Vide,Vide) | Treap(f1,m,f2) -> (f1,f2) ;; rec suppr x = function | Empty -> failwith "wat?" | Node(a,(k,p),b) when k<>x -> if k < x then Node(suppr x a,(k,p),b) else Node(a,(k,p),suppr x b) | Node(Empty,(k,p),b) -> b | Node(Node(aa,(ka,pa),ba),(k,p),b) -> Node(suppr ka (Node(aa,(ka,pa),ba)),(ka,pa),b)