An improved scheme for set equality testing and updating

Abstract

This paper is concerned with data structures for representing an arbitrary number of sets such that we can dynamically update each individual set and test whether any two sets are equal. Previous schemes (Yellin, 1990; Sundar and Tarjan, 1990) can support an equality testing in constant time and an insert or delete operation in O(log2 m) time, where m is the number of insert operations performed. The space requirement is O(m log m). Note that m is an upper bound of n, the sum of the sizes of the sets, but maybe a loose one. When we have performed a lot of delete operations, having few elements left in the sets, it is natural to expect the operations to be performed faster. Yet existing schemes are not favored when n is much smaller than m. It is desirable to have a scheme whose performance is in terms of n instead of m. This paper presents a new scheme which is more dynamic in nature, leading to two improved results: (i) An insert or delete operation can be performed in O(log n) time, with the constant time complexity of equality testing maintained. The space requirement is O(n2 log n). (ii) The space requirement can be reduced to O(n log n), while the time complexity of an insert or delete operation increases to O(log1.5 n). © 1998 - Elsevier Science B.V. All rights reserved.