Zip Trees

If you’re on a phone, here’s an HTML version of the paper <a href="https:&#x2F;&#x2F;www.arxiv-vanity.com&#x2F;papers&#x2F;1806.06726&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.arxiv-vanity.com&#x2F;papers&#x2F;1806.06726&#x2F;</a>

A Cartesian tree (treap) with zip&#x2F;merge change routine is a well known datastructure in competitive programming. The only difference from the paper would be rank selection algorithm - uniform instead of geometric.<p>Unclear if authors were aware of it.

Correct me if I&#x27;m wrong, but isn&#x27;t this the &quot;standard&quot; [1] treap with split&#x2F;merge (which is somewhat acknowledged in the footnote of page 8), simply with a different distribution of priorities? The result is certainly impressive, but it seems like a small modification to an otherwise known structure.<p>[1]: See here <a href="http:&#x2F;&#x2F;e-maxx.ru&#x2F;algo&#x2F;treap" rel="nofollow">http:&#x2F;&#x2F;e-maxx.ru&#x2F;algo&#x2F;treap</a> for an old reference of this structure. Google translate does a decent job with it, and the code is readable without translation.

&gt; insertion and deletion can be done purely top-down, with O(1) expected restructuring time and exponentially infrequent occurrences of expensive restructuring. Certain kinds of deterministic balanced search trees, in particular weak AVL trees and red-black trees achieve these bounds in the amortized sense [3], but at the cost of somewhat complicated update algorithms.<p>It&#x27;s a neat, novel data structure with O(1) typical insert and delete times. Very cool!

I&#x27;m curious about how expensive the restructuring is, and importantly, can that be &quot;scheduled&quot;: can i violate some conditions and then do the expensive restructuring at a time that is convenient?

Data structure from competitive programming is also known as &quot;treap with implicit keys&quot;, related question on stackoverflow: <a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;3497875&#x2F;treap-with-implicit-keys" rel="nofollow">https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;3497875&#x2F;treap-with-impli...</a>

Any links to the implementation of this? The paper says that there&#x27;s a concurrent implementation in the author&#x27;s thesis, but Princeton charges $5 per copy of theses, so I can&#x27;t view the actual implementation:<p><a href="https:&#x2F;&#x2F;dataspace.princeton.edu&#x2F;jspui&#x2F;handle&#x2F;88435&#x2F;dsp01gh93h214f" rel="nofollow">https:&#x2F;&#x2F;dataspace.princeton.edu&#x2F;jspui&#x2F;handle&#x2F;88435&#x2F;dsp01gh93...</a>

I wonder if this would be a good candidate for the basis of a persistent (&quot;functional&quot;) data structure?<p>O(1) pointer changes for insert&#x2F;remove is a good sign, since pointer changes tend to become <i>space</i> overhead in a persistent data structure.

Readers already familiar with similar data structures may save time by proceeding directly to section 4, &quot;Previous Related Work&quot;.

Is cool to see new innovation in this area