Rendered at 12:50:23 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
modulovalue 2 hours ago [-]
> 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.
lindig 1 hours ago [-]
> 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. There are so many problems that can be sped up by 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.
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.