Listing 3: Modification of the typical existing implementation.

initialize a pointer to the rollback list
try
   for each element, e, in the range (first, last]
      search the tree for a place to insert e
      if e is not already in the tree
         allocate a new node, n
         try
            call n's constructor
         catch
            deallocate n
            rethrow the exception
         add n to the tree
         add n to the rollback list
catch
   for each node, n, in the rollback list
      remove n from the tree
      call n's destructor
      deallocate n
   rethrow the exception