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

Rajamani Sundar, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProc 22nd Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages18-25
Number of pages8
ISBN (Print)0897913612, 9780897913614
DOIs
StatePublished - 1990
Externally publishedYes
EventProceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA
Duration: May 14 1990May 16 1990

Publication series

NameProc 22nd Annu ACM Symp Theory Comput

Other

OtherProceedings of the 22nd Annual ACM Symposium on Theory of Computing
CityBaltimore, MD, USA
Period5/14/905/16/90

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Unique binary search tree representations and equality-testing of sets and sequences'. Together they form a unique fingerprint.

  • Cite this

    Sundar, R., & Tarjan, R. E. (1990). Unique binary search tree representations and equality-testing of sets and sequences. In Proc 22nd Annu ACM Symp Theory Comput (pp. 18-25). (Proc 22nd Annu ACM Symp Theory Comput). Publ by ACM. https://doi.org/10.1145/100216.100219