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. So many problems that can be sped up using balanced trees and augmentations.
lindig
> Treaps have been proposed by Raimund Siedel and Cecilia Aragon in 1989.
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.
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. So many problems that can be sped up using balanced trees and augmentations.
The correct name is Raimund Seidel https://en.wikipedia.org/wiki/Raimund_Seidel
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.