(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)
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 outdegree, 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 unique binary search tree representations.