Listing 4: Moving temporary tree nodes into the existing tree.

initialize a pointer to the rollback tree
for each element, e, in the range (first, last]
   if e is not already in the existing tree
      if e is not already in the rollback tree
         add e to the rollback tree
for each node n in the rollback tree
   remove n from the rollback tree
   add n to the existing tree