SHARE
TWEET

Untitled

a guest Aug 26th, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. let read_int() = Scanf.scanf " %d" (fun x-> x);;
  2.  
  3. type tree =
  4.     | Nil
  5.     | Noeud of tree * int * tree * int * int * string
  6.  
  7. let hauteur = function
  8.     | Nil -> 0
  9.     | Noeud(_,_,_,h, _, _) -> h
  10.  
  11. let taille = function
  12.     | Nil -> 0
  13.     | Noeud(_, _, _, _, n, _) -> n
  14.  
  15. let indice = function
  16.     | Nil -> 0
  17.     | Noeud(g, _, _, _, _, _) -> 1 + taille g
  18.  
  19. let desequilibre = function
  20.     | Nil -> 0
  21.     | Noeud(g, _, d, _, _, _) -> hauteur g - hauteur d
  22.  
  23. let update_hauteur = function
  24.     | Nil -> Nil
  25.     | Noeud(g, x, d, _, t, s) -> Noeud(g, x, d, 1 + max (hauteur g) (hauteur d), t, s)
  26.  
  27. let update_taille = function
  28.     | Nil -> Nil
  29.     | Noeud(g, x, d, h, _, s) -> Noeud(g, x, d, h, 1 + taille g + taille d, s)
  30.  
  31. let update = function
  32.     | Nil -> Nil
  33.     | Noeud(g, x, d, _, _, s) -> update_hauteur (update_taille (Noeud(g, x, d, -1, -1, s)))
  34.  
  35.  
  36. let rotation_droite = function
  37.     | Nil -> failwith "Structure incorrecte 1 !"
  38.     | Noeud(Nil, _, _, _, _, _) -> failwith "Structure incorrecte 2 !"
  39.     | Noeud( Noeud(t1, y, t2, _, _, s), x, t3, _, _, t) ->
  40.         let new_x = update (Noeud(t2, x, t3, -1, -1, t)) in
  41.         update (Noeud(t1, y, new_x, -1, -1, s))
  42.  
  43. let rotation_gauche = function
  44.     | Nil -> failwith "Structure incorrecte 3 !"
  45.     | Noeud(_, _, Nil, _, _, _) -> failwith "Structure incorrecte 4 !"
  46.     | Noeud(t1, x, Noeud(t2, y, t3, _, _, s ), _, _, t) ->
  47.         let new_x = update (Noeud(t1, x, t2, -1, -1, t)) in
  48.         update (Noeud(new_x, y, t3, -1, -1, s))
  49.  
  50. let equilibre tree = match desequilibre tree with
  51.     | n when n < -1 -> rotation_gauche tree
  52.     | n when n > 1 -> rotation_droite tree
  53.     | n -> update tree
  54.  
  55. let rec insere x s = function
  56.     | Nil -> Noeud(Nil, x, Nil, 0, 1, s)
  57.     | Noeud(l, y, r, _, _, t) when x < y -> equilibre (Noeud(insere x s l, y, r, -1, -1, t))
  58.     | Noeud(l, y, r, _, _, t) -> equilibre (Noeud(l, y, insere x s r, -1, -1, t))
  59.  
  60. let rec kth k = function
  61.     | Nil -> failwith "Arbre trop petit"
  62.     | Noeud(g, x, d, _, _, s) when k = 1+taille g -> s
  63.     | Noeud(g, x, d, _, _, _) when k < 1+taille g-> kth k g
  64.     | Noeud(g, x, d, _, _, _)             -> kth (k-1 - (taille g)) d
  65.  
  66.  
  67. let main () =
  68.     let nb_canards = read_int () in
  69.     let tree = ref Nil in
  70.  
  71.     for i = 0 to (nb_canards-1) do
  72.         let nom = Scanf.scanf " %s" (fun x -> x) in
  73.         let pos = read_int() in
  74.         let k = read_int() in
  75.         tree := insere pos nom !tree;
  76.         print_string (kth k !tree);
  77.         print_char '\n'
  78.     done;
  79.     ()
  80.  
  81. 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
 
Top