• API
• FAQ
• Tools
• Archive
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.

Top