bicsi's blog

Treaps reinvented?
By bicsi, history, 4 years ago, In English

I recently found put about this paper paper by Tarjan et al describing a data structure that strikes a lot of similarity to the data structure a lot of us have been familiar throughout the years, the treap without rotation.

I was wondering what you think about it. Is it just a coincidence? Is there something more subtle that ‘Zip trees’ have that treaps without rotations don’t? And, moreover, are there no notable mentions of this Treap implementation in literature?

  • Vote: I like it
  • +105
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +46 Vote: I do not like it

It looks like the only difference with treaps is that, instead of choosing $$$priority$$$ uniformly randomly from $$$1 \ldots n^{O(1)}$$$, we only store $$$\log(priority)$$$, which would be geometrically distributed from $$$1 \ldots O(\log(n))$$$. This means you only need to store $$$\log \log n$$$ bits instead of $$$\log n$$$ bits. Overall, seems like a very slim optimization.

The paper mentions these comparisons on the last paragraph of page 4 and the footnote.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +20 Vote: I do not like it

    ‘and different insertion and deletion algorithms’

    Also, this seems to me as the most praised ‘advantage’ of this data structure, from the paper.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

      Yeah, the footnote also discusses prior mentions of the split/merge implementation:

      2 Seidel and Aragon [8] hinted at the possibility of doing insertions and deletions by unzipping and zipping: in a footnote they say, “In practice it is preferable to approach these operations the other way around. Joins and splits of treaps can be implemented as iterative top-down procedures; insertions and deletions can then be implemented as accesses followed by splits or joins.” But they provide no further details.

      I think just split/merge treaps have not been novel enough to publish a separate paper, but if you add some other twist (like compressed priorities), then it becomes different enough to publish?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Coming up, Zip trees with $$$O(0)$$$ bits of extra memory for ranks.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          Yeah lol, it's kinda already here, they mention that, both for zip trees and treaps, you can compute the rank as a pseudorandom function of the key (which breaks if keys aren't distinct).

          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +37 Vote: I do not like it

        In my opinion, decreasing the extra space from O(logn) to O(loglogn) is quite interesting, and random bits are expensive (they have a remark on page 11 about that). In "practice" we are using pseudorandom bits, so it makes sense to analyse how much randomness is really required... at least in theory.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Yeah, in theory it's a nontrivial improvement, but in a typical wordRAM model, O(log n) bits is a single word anyways, so it's a little moot. (We're already using O(log n) extra space to store pointers to children.)

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          On second thought, you're right that decreasing the necessary randomness from $$$O(n \log n)$$$ bits to EV $$$O(n)$$$ is a pretty big deal.

          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        I think just split/merge treaps have not been novel enough to publish a separate paper

        They are not but on the other hand they are in this strange position where they are "folklore" — known but really not documented very well. Maybe the situation has become better now when more people are writing CP tutorials but in 2016 when I first learned about treaps almost all sources just showed how to get split and merge from insert/delete and not the other way around. Finally someone just mentioned that you can do it the other way and I just kinda had to work it out on paper, I couldn't find any source that explained how it is done.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +20 Vote: I do not like it

          Yeah, totally agree, it's a shame that there isn't always a place where "folklore" is collected. People won't bother publishing them in academic journals because they're not novel results, but academic papers are often the main reference source people look for. Also, there's a lot of folklore that's just not very important to algorithms research, but is very useful for implementations/CP. It's good that things like emaxx/cp-algorithms or other books/sites are gathering this content, but it's definitely a work in progress.

          → Reply
»
4 years ago, # |
  Vote: I like it -106 Vote: I do not like it

Check my block ~~~~~ Check my blog!)))))) ~~~~~

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Zip trees are essentially treaps (Seidel and Aragon 1996),

→ Reply