Unique binary search tree representations and equality-testing of sets and sequences

Given an ordered universe U, we study the problem of representing each subset of U by a unique binary search tree so that dictionary operations can be performed efficiently. While efficient randomized solutions to the problem are known, its deterministic complexity has remained unexplored. We exhibit representations that permit the execution of dictionary operations in optimal deterministic time when the dictionary is sufficiently sparse or sufficiently dense. Our results demonstrate an exponential separation between the deterministic and randomized complexities of the problem. We apply unique representations to obtain efficient data structures for maintaining a collection of sets/sequences under queries that test the equality of a pair of objects. Our data structure for set equality-testing is based on an efficient implementation of cascades of CONS operations on uniquely stored S-expressions.