Show HN: Immutable AA Trees in Go

AA trees are a variation of the red–black tree, a form of binary search tree, named after their originator, Swedish computer scientist Arne Andersson.

I found them somewhat simpler to implement compared to other binary search trees. Particularly, the set operations (union/intersection/difference) based on the join primitive by Adams (which I've not seen described elsewhere for AA trees).

Trees are immutable: modifying a tree produces a new tree, which shares as much of the tree structure as possible with the original tree.

If you look at the code, much of the incidental complexity is to ensure immutability while avoiding unnecessary allocations as much as possible (a language with a generational garbage collector could do away with some of that for an even more straightforward implementation).