Faster uniquely represented dictionaries
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 642-649
- https://doi.org/10.1109/sfcs.1991.185430
Abstract
The authors present a solution to the dictionary problem where each subset of size n of an ordered universe is represented by a unique structure, containing a (unique) binary search tree. The structure permits the execution of search, insert, and delete operations in O(n/sup 1/3/) time in the worst case. They also give a general lower bound, stating that for any unique representation of a set in a graph of, bounded outdegree, one of the operations search or update must require a cost of Omega (n/sup 1/3/) Therefore, the result sheds new light on previously claimed lower bounds for unique binary search tree representations.<>Keywords
This publication has 1 reference indexed in Scilit:
- Symbol manipulation by threaded listsCommunications of the ACM, 1960