Representing sets with constant time equality testing

Abstract

Most data structures for sets efficiently implement the operations insert, delete, and member so that a sequence of N such operations has a total complexity of O(N log N). However, if we additionally allow the operation equal(Si, Sj), which tests whether or not two sets Si and Sj are equal, the total complexity of N operations can be as much as O(N2). In this paper we introduce two new set representations that efficiently implement the operations insert, delete, member, and equal on sets. Both representations support equality testing in constant time. The first representation has O(log N + k) worst case time complexity per operation (other than equality), where N is the number of operations and k is the number of nonempty sets at the time of the operation. It has space complexity O(N + k2). When k is known to be less than log N, this representation is time and space efficient. Furthermore, it also supports the operation subset (Si, Sj), which tests whether or not Si is a subset of Sj, in constant time. The second representation has O((log N)2) worst case time complexity per operation (other than equality) and space complexity of O(N log N). A variant on this scheme has expected amortized time complexity of O(log N) per operation and space complexity of O(N log N). © 1992.