signature DIET = sig datatype diet = EMPTY | NODE of int * int * diet * diet val empty : diet val insert : int * diet -> diet val delete : int * diet -> diet val member : int * diet -> bool end structure Diet : DIET = struct datatype diet = EMPTY | NODE of int * int * diet * diet exception EmptyTree val empty = EMPTY fun splitMax (NODE (x,y,l,EMPTY)) = (x,y,l) | splitMax (NODE (x,y,l,r)) = let val (u,v,r') = splitMax r in (u,v,NODE (x,y,l,r')) end fun splitMin (NODE (x,y,EMPTY,r)) = (x,y,r) | splitMin (NODE (x,y,l,r)) = let val (u,v,l') = splitMin l in (u,v,NODE (x,y,l',r)) end fun joinLeft (t as NODE (x,y,EMPTY,r)) = t | joinLeft (NODE (x,y,l,r)) = let val (x',y',l') = splitMax l in if y'+1=x then NODE (x',y,l',r) else NODE (x,y,l,r) end fun joinRight (t as NODE (x,y,l,EMPTY)) = t | joinRight (NODE (x,y,l,r)) = let val (x',y',r') = splitMin r in if y+1=x' then NODE (x,y',l,r') else NODE (x,y,l,r) end fun insert (z,EMPTY) = NODE (z,z,EMPTY,EMPTY) | insert (z,t as NODE (x,y,l,r)) = if zy then if z=y+1 then joinRight (NODE (x,z,l,r)) else NODE (x,y,l,insert (z,r)) else t (* z in [x,y] *) fun merge (l,EMPTY) = l | merge (EMPTY,r) = r | merge (l,r) = let val (x,y,l') = splitMax l in NODE (x,y,l',r) end fun delete (z,EMPTY) = EMPTY | delete (z,NODE (x,y,l,r)) = if zy then NODE (x,y,l,delete (z,r)) else if z=x then if x=y then merge (l,r) (* node must be deleted *) else NODE (x+1,y,l,r) (* interval can be simply shrunk *) else if z=y then NODE (x,y-1,l,r) (* since z<>x => y>x *) else NODE (x,z-1,l,NODE (z+1,y,EMPTY,r)) (* split interval *) fun member (x,EMPTY) = false | member (x,NODE (y,z,l,r)) = if x>=y andalso x<=z then true else if xz *) member (x,r) end (* some examples: fun build l = List.foldl Diet.insert Diet.empty l; val l = [6,9,2,13,8,14,10,7,5]; val d = build l; *)