datatype 'label btree = Empty | Node of 'label * 'label btree * 'label btree; fun lower(nil) = nil | lower(c::cs) = (Char.toLower c)::lower(cs); fun strLT(x,y) = implode(lower(explode x)) < implode(lower(explode y)); 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 lt Empty x = Empty | delete lt (Node(y,left,right)) x = if lt(x,y) then Node(y,(delete lt left x),right) else if lt(y,x) then Node(y,left,(delete lt right x)) 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;