functor SEARCHTREE( structure T : BTreeSig
                    type Item
                    val < : Item * Item -> bool ) =
struct
open T
exception NoChange
local
fun ins (e, Lf) = Nd(Lf, e, Lf)
  | ins (e, Nd(lt, v, rt)) =
      if      e < v then Nd(ins(e, lt), v, rt) 
      else if v < e then Nd(lt, v, ins(e, rt))
      else raise NoChange
in
fun insert(e, t) = ins(e, t) handle NoChange => t
end

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 deq (Nd(lt, v, Lf)) = (lt, v)
  | deq (Nd(lt, v, rt)) = 
    let val (r, m) = deq rt
     in (Nd(lt, v, r), m) end

local
fun join Lf x = x
  | join x Lf = x
  | join lt rt = 
    let val (l, m) = deq lt
     in Nd(l, m, rt) end

fun del(e, Lf) = raise NoChange
  | del(e, Nd(lt, v, rt)) =
      if      e < v then Nd(del(e, lt), v, rt) 
      else if v < e then Nd(lt, v, del(e, rt))
      else join lt rt
in
fun delete(e, T) = del(e, T) handle NoChange => T
end
end