functor T23(type Item val < : Item * Item -> bool)=
struct
datatype 'a Tree = Lf | Two of 'a Tree * 'a * 'a Tree
             | Three of 'a Tree * 'a * 'a Tree * 'a * 'a Tree

exception Split of Item Tree * Item * Item Tree
      and NoChange
val empty = Lf

fun split x = raise Split x

fun ins(x, Lf) = split(Lf, x, Lf)
  | ins(x, Two(lt, v, rt)) =
    if x < v then Two(ins(x, lt), v, rt)
             handle Split(xl,xv,xr) => Three(xl, xv, xr, v, rt)
    else if v < x then Two(lt, v, ins(x, rt))
             handle Split(xl,xv,xr) => Three(lt, v, xl, xv, xr)
    else raise NoChange
  | ins(x, Three(lt, lv, mt, rv, rt)) =
    if x < lv 
       then Three(ins(x,lt), lv, mt, rv, rt) 
       handle Split left => split(Two left, lv, Two(mt, rv, rt)) 
    else if rv < x 
       then Three(lt, lv, mt, rv, ins(x, rt))
       handle Split right => split(Two(lt,lv,mt),rv,Two right)
    else if lv < x andalso x < rv
       then Three(lt,lv,ins(x,mt),rv,rt)
       handle Split(xl, xv, xr) => split(Two(lt,lv,xl),xv,Two(xr,rv,rt))
    else raise NoChange

fun member Lf x = false
  | member (Two(lt,v,rt)) x = 
       if x < v then member lt x
       else if v < x then member rt x
       else true
  | member (Three(lt, lv, mt, rv, rt)) x =
       if x < lv then member lt x
       else if rv < x then member rt x
       else if lv < x andalso x < rv then member mt x
       else true

fun insert(x, t) = ins(x,t)
                   handle NoChange  => t
                        | Split two => Two two
end;