Are any efficient [O(log n)] self balancing trees that are canonical? By canonical I mean that for any set of data inserted into the tree, inserting it after any permutation results in the same tree. I'm particularly interested in trees where data is stored in the leaves.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Andersson and Ottmann's "New tight bounds on uniquely represented dictionaries" has a good survey on the subject of of canonical (or "unique", as they call it) forms for dictionaries.
Before I describe it, I should note that their structure is actually stronger than you are looking for. Their structures are size-unique, so any two trees with $n$ elements will have the same shape, even if the sets of elements are unrelated. They leave the problem of set-unique data structures open, though see below about randomization.
Andersson and Ottmann invented a data structure (a graph, not a tree) where updates and lookups take $O(n^{1/3})$ time. By tuning a parameter, they can get $O(\sqrt{n})$ time for updates and $O(\lg n)$ time for lookups, matching an earlier structure of Sundar and Tarjan (which Ottmann claims in "Trees - A Personal View" is not strictly size-unique due to the way they use an auxiliary structure). Andersson and Ottmann also prove that either update or lookup operations must take $\Omega(n^{1/3})$ time in their particular model. An earlier paper by Snyder showed some $\Omega(\sqrt{n})$ lower bounds, but the model he used was too strict for Andersson and Ottmann's taste.
If you're willing to accept "canonical" meaning "taken from the same sample space of trees", then treaps might be exactly what you're looking for -- any set of elements in a tree has shape independent of the order in which they arrived. However, the shape is randomized.
For storing data in the leaves (by which I assume you mean that each key is stored in a leaf, or that value (in a map structure) are all stored in leaves), views of skip-lists as trees may have this property. I mentioned some tree-views of skip lists on another question at this site. Others that may deserve mention are
- Daniel Golovin's The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees
- Michael Spiegel and Paul F. Reynolds's Lock-free multiway search trees and The Dense Skip Tree: A Cache-Conscious Randomized Data Structure
I've also been recently thinking about a treap-like structure in which every key is stored in a leaf, as mentioned in the related question I posed here. I hope to post something there on the matter soon.
