<p><a href="http://user.it.uu.se/~arnea/abs/andetigh.html" rel="nofollow noreferrer">Andersson and Ottmann's "New tight bounds on uniquely represented dictionaries"</a> has a good survey on the subject of of canonical (or "unique", as they call it) forms for dictionaries.</p>

<p>Before I describe it, I should note that their structure is actually stronger than you are looking for. Their structures are <em>size-unique</em>, 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 <em>set-unique</em> data structures open, though see below about randomization.</p>

<p>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 <a href="http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&amp;doc=GetTRDoc.pdf&amp;AD=ADA223643" rel="nofollow noreferrer">an earlier structure of Sundar and Tarjan</a> (which <a href="http://www.springerlink.com/index/d1u426468144k3h8.pdf" rel="nofollow noreferrer">Ottmann claims in "Trees - A Personal View"</a> 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.</p>

<p>If you're willing to accept "canonical" meaning "taken from the same sample space of trees", then <a href="http://acs.lbl.gov/~aragon/treaps.html" rel="nofollow noreferrer">treaps</a> 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.</p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/2430/proving-skip-lists-strongly-weight-balanced-in-expectation">some tree-views of skip lists</a> on another question at this site. Others that may deserve mention are </p>

<ul>
<li>Daniel Golovin's <a href="http://arxiv.org/abs/1005.0662" rel="nofollow noreferrer">The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees</a></li>
<li>Michael Spiegel and Paul F. Reynolds's <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.170.2950" rel="nofollow noreferrer">Lock-free multiway search trees</a> and      <a href="http://www.cs.virginia.edu/~ms6ep/publications/CS-2009-05.pdf" rel="nofollow noreferrer">The Dense Skip Tree: A Cache-Conscious Randomized Data Structure</a></li>
</ul>

<p>I've also been recently <a href="https://cstheory.stackexchange.com/questions/4145/faster-join-of-treaps-with-approximately-the-same-size">thinking about a treap-like structure in which every key is stored in a leaf, as mentioned in the related question I posed here</a>. I hope to post something there on the matter soon.</p>

CC BY-SA 2.5
2011-01-09T23:00:07.490Z
that's a nice answer !
Suresh Venkat
CC BY-SA 2.5
2011-01-09T05:05:11.680Z
2011-01-09T05:05:11.680Z
2017-04-13T12:32:28.053Z
jbapple
<p>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.</p>

<ds.data-structures><tree>
Optimal Self Balancing Trees with Canonical Form?
Jonathan
# Optimal Self Balancing Trees with Canonical Form?

(Asked by: username_0 on 2011-01-08)

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.

**Tags:** ds.data-structures, tree

---

## 1 answers

### Answer by username_1 on 2011-01-09. Score: 7 | Accepted answer

[Andersson and Ottmann's "New tight bounds on uniquely represented dictionaries"](http://user.it.uu.se/~arnea/abs/andetigh.html) 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](http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA223643) (which [Ottmann claims in "Trees - A Personal View"](http://www.springerlink.com/index/d1u426468144k3h8.pdf) 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](http://acs.lbl.gov/~aragon/treaps.html) 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](https://cstheory.stackexchange.com/questions/2430/proving-skip-lists-strongly-weight-balanced-in-expectation) 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](http://arxiv.org/abs/1005.0662)
* Michael Spiegel and Paul F. Reynolds's [Lock-free multiway search trees](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.170.2950) and [The Dense Skip Tree: A Cache-Conscious Randomized Data Structure](http://www.cs.virginia.edu/~ms6ep/publications/CS-2009-05.pdf)

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](https://cstheory.stackexchange.com/questions/4145/faster-join-of-treaps-with-approximately-the-same-size). I hope to post something there on the matter soon.

> **Comments:**
> **username_2**: that's a nice answer !  

---

