Something that's not mentioned in that article is that you can maintain any monoid efficiently over balanced trees, not just the subtree size (aka you need an identity element and an associative operation). Most widely known monoids are boring, but there are more interesting monoids. Interval trees can be implemented as an augmentation using a monoid (this concept is more widely known as augmenting a tree). Range min max augmentations can be used to implement succinct trees (this comes from Sadakane's work on succinct trees, he didn't describe it as a monoid IIRC, but it turns out it is one).
By looking at it from a monoid angle, the specific balanced tree can be abstracted away. Treaps are VERY easy to implement, but the monoids apply to any n-ary balanced trees. There was an article a few days ago about very efficient B-Trees, but from what I've seen they did not support general purpose augmentations, probably because the implementation would have to be partially evaluated to be optimal while being general.
In any case, cool stuff and totally under-explored in my opinion. I hope LLMs will help us become optimal in this area one day and help us automatically select an optimal augmentation and balanced tree. There are so many problems that can be sped up by balanced trees and augmentations.
For an n-ary tree like a B-tree I think you have to take at least log2(n) monoid op evals per monoid update? So I can see why it would take away efficiency.
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.
> Maintaining the sizes of subtrees
Something that's not mentioned in that article is that you can maintain any monoid efficiently over balanced trees, not just the subtree size (aka you need an identity element and an associative operation). Most widely known monoids are boring, but there are more interesting monoids. Interval trees can be implemented as an augmentation using a monoid (this concept is more widely known as augmenting a tree). Range min max augmentations can be used to implement succinct trees (this comes from Sadakane's work on succinct trees, he didn't describe it as a monoid IIRC, but it turns out it is one).
By looking at it from a monoid angle, the specific balanced tree can be abstracted away. Treaps are VERY easy to implement, but the monoids apply to any n-ary balanced trees. There was an article a few days ago about very efficient B-Trees, but from what I've seen they did not support general purpose augmentations, probably because the implementation would have to be partially evaluated to be optimal while being general.
In any case, cool stuff and totally under-explored in my opinion. I hope LLMs will help us become optimal in this area one day and help us automatically select an optimal augmentation and balanced tree. There are so many problems that can be sped up by balanced trees and augmentations.
For an n-ary tree like a B-tree I think you have to take at least log2(n) monoid op evals per monoid update? So I can see why it would take away efficiency.
> Treaps have been proposed by Raimund Siedel and Cecilia Aragon in 1989.
The correct name is Raimund Seidel https://en.wikipedia.org/wiki/Raimund_Seidel
How ... what
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.
I personally found balancing weight balanced trees pretty straightforward: https://yoichihirai.com/bst.pdf
What I like about immutable treaps is that, if you using hashing rather than randomness, you can achieve O(1) equality for entire trees.
Unfortunately, my current language of choice makes hash consing too slow.
A very nice problem solved using treap: https://stackoverflow.com/questions/79751600/solve-cses-moun...
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...
Yeah