The primary attraction of treaps (aside from fast intersection/union/diff) is that they are probably one of the easiest types of balanced trees that can be implemented manually if you need a dependency-free balanced tree. There are only two types of rotations, they are straightforward, and they are mirror images of each other.
These days, where an agent can just write you an AVL tree, red-black tree, or B-tree library in under a minute, it probably matters less.
3 comments:
The primary attraction of treaps (aside from fast intersection/union/diff) is that they are probably one of the easiest types of balanced trees that can be implemented manually if you need a dependency-free balanced tree. There are only two types of rotations, they are straightforward, and they are mirror images of each other.
These days, where an agent can just write you an AVL tree, red-black tree, or B-tree library in under a minute, it probably matters less.
this is non-rotation treap (fhq treap), it is more common among competitive programming folks, for other cs folks, i believe the rotating variant is more popular: https://www.cs.umd.edu/class/spring2022/cmsc420-0101/Lects/l...
A very nice problem solved using treap: https://stackoverflow.com/questions/79751600/solve-cses-moun...