Unique Binary Search Tree Representations and Equality-Testing of Sets and Sequences
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. We exhibit representations that permit the execution of dictionary operations in optimal time when the dictionary is sufficiently sparse or sufficiently dense. 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. In the process, we devise an interesting method for maintaining a dynamic, sparse array.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1989
- Accession Number
- ADA223643
Entities
People
- Rajamani Sundar
- Robert Tarjan
Organizations
- Princeton University