THE SET UNION PROBLEM WITH UNLIMITED BACKTRACKING

An extension of the disjoint set union problem is considered, where th e extra primitive backtrack(i) can undo the last i unions not yet undo ne. Let n be the total number of elements in all the sets. A data stru cture is presented that supports each union and find in O(log n/log lo g n) worst-case time and each backtrack(i) in O(1) worst-case time, ir respective of i. The total space required by the data structure is 0(n ). A byproduct of this construction is a partially persistent data str ucture for the standard set union problem, capable of supporting union , find, and find-in-the-past operations, each in O(log n/log log n) wo rst-case time. All these upper bounds are tight for the class of separ able-pointer algorithms as well as in the cell probe model of computat ion.