type avl_tree =
    | Nil
    | Noeud of avl_tree * int * avl_tree * int

let hauteur = function
    | Nil -> 0
    | Noeud(_, _, _, h) -> h

let update_height = function
    | Nil -> Nil
    | Noeud(g, x, d, _) -> Noeud(g, x, d, 1 + max (hauteur g) (hauteur d))

let desequilibre = function
    | Nil -> 0
    | Noeud(g, x, d, _) -> hauteur g - hauteur d

let rotation_droite = function
    | Nil -> failwith "Structure invalide 1 !"
    | Noeud( Nil, _, _, _) -> failwith "Structure invalide 2 !"
    | Noeud( Noeud(t1, y, t2, h1), x, t3, _) ->
        let new_x = Noeud(t2, x, t3, -1) in
        let new_y = Noeud(t1, y, update_height new_x, -1) in
        update_height new_y

let rotation_gauche = function
    | Nil -> failwith "Structure invalide 3 !"
    | Noeud(_, _, Nil, _) -> failwith "Structure invalide 4 !"
    | Noeud(t1, x, Noeud(t2, y, t3, _), _) ->
        let new_x = Noeud(t1, x, t2, -1) in
        let new_y = Noeud(update_height new_x, y, t3, -1) in
        update_height new_y

let equilibre_noeud tree = match desequilibre tree with
    | x when x < - 1 -> rotation_gauche tree
    | x when x > 1 -> rotation_droite tree
    | _ -> update_height tree

let rec contient x = function
    | Nil -> false
    | Noeud(g, y, d, _) when y = x -> true
    | Noeud(g, y, _, _) when y > x -> contient x g
    | Noeud(_, _, d, _) -> contient x d

let rec insere x = function
    | Nil -> Noeud(Nil, x, Nil, 0)
    | Noeud(g, y, d, _) when y > x -> equilibre_noeud (Noeud(insere x g, y, d, -1))
    | Noeud(g, y, d, _)            -> equilibre_noeud (Noeud(g, y, insere x d, -1))

let main () =
    let tree = ref Nil in
    for i = 0 to 100000 do
        tree := insere i !tree;
    done;
    print_int (hauteur !tree);
    print_newline ();
    ()

let t = main ()