### 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 language | English (US) |
---|---|

Title of host publication | Proc 22nd Annu ACM Symp Theory Comput |

Publisher | Publ by ACM |

Pages | 18-25 |

Number of pages | 8 |

ISBN (Print) | 0897913612, 9780897913614 |

DOIs | |

State | Published - 1990 |

Externally published | Yes |

Event | Proceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA Duration: May 14 1990 → May 16 1990 |

### Publication series

Name | Proc 22nd Annu ACM Symp Theory Comput |
---|

### Other

Other | Proceedings of the 22nd Annual ACM Symposium on Theory of Computing |
---|---|

City | Baltimore, MD, USA |

Period | 5/14/90 → 5/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

*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