UNIQUE BINARY-SEARCH-TREE REPRESENTATIONS AND EQUALITY TESTING OF SETS AND SEQUENCES

This paper studies the problem of representing sets over an ordered un iverse by unique binary search trees, so that dictionary operations ca n be performed efficiently on any set. Although efficient randomized s olutions to the problem are known, its deterministic complexity has be en open. The paper exhibits representations that permit the execution of dictionary operations in optimal deterministic time when the dictio nary is sufficiently sparse or sufficiently dense. The results demonst rate an exponential separation between the deterministic and randomize d complexities of the problem. Unique representations are applied to o btain efficient data structures for maintaining a dynamic collection o f sets/sequences under queries that test the equality of a pair of obj ects. The data structure for set equality testing tests equality of se ts in constant time and processes set updates in O(log m) amortized ti me and O(log m) space, where m denotes the total number of updates per formed. It is based on an efficient implementation of cascades of CONS Operations on uniquely stored S-expressions. The data structure for s equence equality testing tests equality of sequences in constant time and processes updates in O(square-root n log m + log m) amortized time and O(square-root n) amortized space where n denotes the length of th e sequence that is updated and m denotes the total number of updates p erformed.