SHARE
TWEET

Untitled

a guest Aug 23rd, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. type avl_tree =
  2.     | Nil
  3.     | Noeud of avl_tree * int * avl_tree * int
  4.  
  5. let hauteur = function
  6.     | Nil -> 0
  7.     | Noeud(_, _, _, h) -> h
  8.  
  9. let update_height = function
  10.     | Nil -> Nil
  11.     | Noeud(g, x, d, _) -> Noeud(g, x, d, 1 + max (hauteur g) (hauteur d))
  12.  
  13. let desequilibre = function
  14.     | Nil -> 0
  15.     | Noeud(g, x, d, _) -> hauteur g - hauteur d
  16.  
  17. let rotation_droite = function
  18.     | Nil -> failwith "Structure invalide 1 !"
  19.     | Noeud( Nil, _, _, _) -> failwith "Structure invalide 2 !"
  20.     | Noeud( Noeud(t1, y, t2, h1), x, t3, _) ->
  21.         let new_x = Noeud(t2, x, t3, -1) in
  22.         let new_y = Noeud(t1, y, update_height new_x, -1) in
  23.         update_height new_y
  24.  
  25. let rotation_gauche = function
  26.     | Nil -> failwith "Structure invalide 3 !"
  27.     | Noeud(_, _, Nil, _) -> failwith "Structure invalide 4 !"
  28.     | Noeud(t1, x, Noeud(t2, y, t3, _), _) ->
  29.         let new_x = Noeud(t1, x, t2, -1) in
  30.         let new_y = Noeud(update_height new_x, y, t3, -1) in
  31.         update_height new_y
  32.  
  33. let equilibre_noeud tree = match desequilibre tree with
  34.     | x when x < - 1 -> rotation_gauche tree
  35.     | x when x > 1 -> rotation_droite tree
  36.     | _ -> update_height tree
  37.  
  38. let rec contient x = function
  39.     | Nil -> false
  40.     | Noeud(g, y, d, _) when y = x -> true
  41.     | Noeud(g, y, _, _) when y > x -> contient x g
  42.     | Noeud(_, _, d, _) -> contient x d
  43.  
  44. let rec insere x = function
  45.     | Nil -> Noeud(Nil, x, Nil, 0)
  46.     | Noeud(g, y, d, _) when y > x -> equilibre_noeud (Noeud(insere x g, y, d, -1))
  47.     | Noeud(g, y, d, _)            -> equilibre_noeud (Noeud(g, y, insere x d, -1))
  48.  
  49. let main () =
  50.     let tree = ref Nil in
  51.     for i = 0 to 100000 do
  52.         tree := insere i !tree;
  53.     done;
  54.     print_int (hauteur !tree);
  55.     print_newline ();
  56.     ()
  57.  
  58. let t = main ()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top