3.ml

3.ml

type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;;

let rec height t =
    match t with
        Lf -> 1
    |   Br (_, t1, t2) -> 
            if (height t1) > (height t2) then
                1 + (height t1)
            else
                1 + (height t2);;

let rec balance t =
    match t with
        Lf -> Lf
    |   Br (_, t1, t2) ->
            Br ((height t1) - (height t2), balance t1, balance t2);;