Treaps reinvented?

Revision en2, by bicsi, 2020-12-08 21:52:38

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?

Tags research, treap

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English bicsi 2020-12-08 21:52:38 2 Tiny change: 've that traps withou' -> 've that treaps withou'
en1 English bicsi 2020-12-08 21:30:46 527 Initial revision (published)