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?