functor AVLTREE( 
                    type Item
                    val < : Item * Item -> bool ) =
struct
datatype 'a Tree = Lf | Nd of 'a Tree * 'a * 'a Tree
exception NoChange and AVL

datatype Balance = L | B | R

datatype Change = C | N

fun balins((N, lt), v, (N, rt)) = (N, Nd(lt, v, rt))
  | balins((C, lt), (L, c), (N, rt)) = 
    let val Nd(t1, (ab, a), t2) = lt
    in case ab of
          L => (N, Nd( t1, (B, a), Nd( t2, (B, c), rt)))
        | R => let val Nd( t2, (bb, b), t3) = t2
                   val (bl, bn, br) = 
                       case bb of
                         L => (B, B, R)
                       | B => (B, B, B)
                       | R => (L, B, B)
                in (N, Nd(Nd(t1, (bl, a), t2), (bn, b),
                        Nd(t3, (br, c), rt)))
               end
        | B => raise AVL (* changes only propagate when there is imbalance *)
    end
  | balins((C, lt), (B, e), (N, rt)) = (C, Nd(lt, (L, e), rt))
  | balins((C, lt), (R, e), (N, rt)) = (N, Nd(lt, (B, e), rt))
  | balins((C,_),_,(C,_)) = raise AVL
  | balins((N, lt), (R, a), (C, rt)) = 
    let val Nd(t2, (cb, c), t3) = rt
    in case cb of R => (N, Nd( Nd( lt, (B, a), t2), (B, c), t3))
                | L => let val Nd( t1, (bb, b), t2) = t2
                   val (bl, bn, br) = 
                       case bb of
                         R => (L, B, B)
                       | B => (B, B, B)
                       | L => (B, B, R)
                in (N, Nd(Nd(lt, (bl, a), t1), (bn, b),
                          Nd(t2, (br, c), t3)))
                end
                | B => raise AVL (* changes only propagate when there is imbalance *)
    end
  | balins((N, lt), (B, e), (C, rt)) = (C, Nd(lt, (R, e), rt))
  | balins((N, lt), (L, e), (C, rt)) = (N, Nd(lt, (B, e), rt))

fun ins (e, Lf) = (C, Nd(Lf, (B, e), Lf))
  | ins (e, Nd(lt, (b,v), rt)) =
      if      e < v then balins(ins(e, lt), (b,v), (N, rt)) 
      else if v < e then balins((N, lt), (b,v), ins(e, rt))
      else raise NoChange

fun getmax (Nd(lt, (b,e), Lf)) = (lt, (b,e)) (* balance is wrong here?? *)
  | getmax (Nd(lt, v, rt)) = 
    let val (rt', m) = getmax rt
     in (Nd(lt, v, rt'), m) end
  | getmax Lf = raise NoChange

fun join Lf x = x
  | join x Lf = x
  | join lt rt = 
    let val (l, m) = getmax lt
     in Nd(l, m, rt) end
(*
fun del(e, Lf) = raise NoChange
  | del(e, Nd(lt, (b, v), rt)) =
      if      e < v then Nd(del(e, lt),(b, v), rt) 
      else if v < e then Nd(lt, (b, v), del(e, rt))
      else join lt rt*)

type Item = Item and Set = Item Tree
val empty = Lf
fun isEmpty Lf = true | isEmpty _ = false

fun member  Lf              k = false
  | member (Nd(t1, k', t2)) k =
      if k  < k' then member t1 k
      else
      if k' < k  then member t2 k
      else true;

fun insert(e, t) = #2(ins(e, t)) handle NoChange => t
(*
fun delete(e, t) = del(e, t) handle NoChange => t*)

end