type 'a avl = Empty | Node of int * 'a avl * 'a * 'a avl

  let balanceLL node = 
    match node with 
        (Node (d, Node (lmax, ll, xl, rl), x, r)) ->
          let rmax = max (depth rl) (depth r) + 1 
          in let cmax = max rmax (depth ll) + 1
          in Node (cmax, ll, xl, Node (rmax, rl, x, r))
      | _ -> failwith "Impossible"

  let balanceLR node =
    match node with 
        (Node (d, Node (dl, ll, y, Node (dlr, lrl, z, lrr)), x, r)) -> 
          let lmax = max (depth ll) (depth lrl) + 1
          in let rmax = max (depth lrr) (depth r) + 1
          in let cmax = max lmax rmax + 1
          in Node (cmax, Node (lmax, ll, y, lrl), z, Node (rmax, lrr, x, r))
      | _ -> failwith "Impossible"

  let balanceRR node = match node with
      (Node (d, l, x, Node (dr, lr, xr, rr))) ->
        let lmax = max (depth l) (depth lr) + 1
        in let cmax = max lmax (depth rr) + 1
        in Node (cmax, Node (lmax, l, x, lr), xr, rr)
    | _ -> failwith "Impossible"

  let balanceRL node =
    match node with 
        (Node (d, l, x, Node (dr, Node (drl, rll, z, rlr), y, rr))) ->
          let lmax = max (depth l) (depth rll) + 1
          in let rmax = max (depth rlr) (depth rr) + 1
          in let cmax = max lmax rmax + 1
          in Node (cmax, Node (lmax, l, x, rll), z, Node (rmax, rlr, y, rr)) 
      | _ -> failwith "Impossible"
      

This document was generated using caml2html