New Tight Bounds on Uniquely Represented Dictionaries
Arne Andersson, Thomas Ottmann · SIAM Journal on Computing · 1995
We 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^{1/3})$ time in the worst case. We also give a general lower bound, stating that for any unique representation of a set in a graph of bounded out-degree, one of the operations search or update must require a cost of $\Omega(n^{1/3})$. Therefore, our result sheds new light on previously claimed lower bounds for the unique representation of dictionaries.