TY - JOUR
T1 - Unique binary-search-tree representations and equality testing of sets and sequences
AU - Sundar, Rajamani
AU - Tarjan, Robert Endre
PY - 1994/1/1
Y1 - 1994/1/1
N2 - This paper studies the problem of representing sets over an ordered universe by unique binary search trees, so that dictionary operations can be performed efficiently on any set. Although efficient randomized solutions to the problem are known, its deterministic complexity has been open. The paper exhibits representations that permit the execution of dictionary operations in optimal deterministic time when the dictionary is sufficiently sparse or sufficiently dense. The results demonstrate an exponential separation between the deterministic and randomized complexities of the problem.
AB - This paper studies the problem of representing sets over an ordered universe by unique binary search trees, so that dictionary operations can be performed efficiently on any set. Although efficient randomized solutions to the problem are known, its deterministic complexity has been open. The paper exhibits representations that permit the execution of dictionary operations in optimal deterministic time when the dictionary is sufficiently sparse or sufficiently dense. The results demonstrate an exponential separation between the deterministic and randomized complexities of the problem.
UR - http://www.scopus.com/inward/record.url?scp=0028378074&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0028378074&partnerID=8YFLogxK
U2 - 10.1137/S0097539790189733
DO - 10.1137/S0097539790189733
M3 - Article
AN - SCOPUS:0028378074
SN - 0097-5397
VL - 23
SP - 24
EP - 44
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 1
ER -