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

Rajamani Sundar, Robert Endre Tarjan

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)24-44
Number of pages21
JournalSIAM Journal on Computing
Volume23
Issue number1
DOIs
StatePublished - Jan 1 1994

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(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