• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?