R. Sundar et Re. Tarjan, UNIQUE BINARY-SEARCH-TREE REPRESENTATIONS AND EQUALITY TESTING OF SETS AND SEQUENCES, SIAM journal on computing, 23(1), 1994, pp. 24-44
Citations number
23
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
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.