signature TOTALORDER = sig type element; val lt : element * element -> bool end; functor MakeBST(Lt: TOTALORDER): sig type 'label btree; exception EmptyTree; val create : Lt.element btree; val lookup : Lt.element * Lt.element btree -> bool; val insert : Lt.element * Lt.element btree -> Lt.element btree; val deletemin : Lt.element btree -> Lt.element * Lt.element btree; val delete : Lt.element * Lt.element btree -> Lt.element btree end = struct open Lt; datatype 'label btree = Empty | Node of 'label * 'label btree * 'label btree; val create = Empty; fun lookup(x, Empty) = false | lookup(x, Node(y,left,right)) = if lt(x,y) then lookup(x, left) else if lt(y,x) then lookup(x, right) else (* x=y *) true; fun insert(x,Empty) = Node(x,Empty,Empty) | insert(x, T as Node(y,left,right)) = if lt(x,y) then Node(y,insert(x,left),right) else if lt(y,x) then Node(y,left,insert(x,right)) else (* x=y *) T; (* do nothing; x was already there *) exception EmptyTree; (* deletemin(T) returns a pair consisting of the least element y in tree T and the tree that results if we delete y from T. It is an error if T is empty *) fun deletemin(Empty) = raise EmptyTree | deletemin(Node(y,Empty,right)) = (y,right) (* The critical case. If the left subtree is empty, then the element at current node is min. *) | deletemin(Node(w,left,right)) = let val (y,L) = deletemin(left) in (y, Node(w,L,right)) end; fun delete(x, Empty) = Empty | delete(x, Node(y,left,right)) = if lt(x,y) then Node(y,delete(x,left),right) else if lt(y,x) then Node(y,left,delete(x,right)) else (* x=y *) case (left,right) of (Empty,r) => r | (l,Empty) => l | (l,r) => let val (z,r1) = deletemin(r) in Node(z,l,r1) end; end; structure StringBST = MakeBST( struct type element = string; fun lt(x,y) = let fun lower(nil) = nil | lower(c::cs) = (Char.toLower c)::lower(cs); in implode(lower(explode(x))) < implode(lower(explode(y))) end; end );