Блог пользователя bicsi

Автор bicsi, история, 4 года назад, По-английски

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?

  • Проголосовать: нравится
  • +105
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

    ‘and different insertion and deletion algorithms’

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

          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).

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +37 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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.)

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +17 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +20 Проголосовать: не нравится

          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.

»
4 года назад, # |
  Проголосовать: нравится -106 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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