Have "Brodal search trees" really been implemented for practical use?

Question

Brodal et al. demonstrated in their ESA '06 paper the existence of a purely functional structure with logarithmic-time search, update and insertion, and constant-time merge. (Note I'm not talking about Brodal heaps, which are a different data structure, quite widely used to implement purely functional priority queues.) This seems to be a very lucrative result, and should lead to efficient purely functional sets and maps, but I don't see them used anywhere:

• Haskell's containers uses Adams trees;
• OCaml standard library uses AVL trees;
• Scala's immutable sorted maps are implemented using red-black trees.

If Brodal trees really have such good results, why have they not been adapted into mainstream functional programming languages standard libraries? In fact, I have not seen even one implementation of Brodal trees at all!

Specifically, is this because:

• they are very hard (or in fact nearly impossible) to implement correctly;
• the constants are very large, and real gains seem small;
• other reasons;
• or a combination of the aforementioned?

Typo

There are few citations on Google scholar. Maybe very few people have read or are aware of the paper for whatever reason. Here are the most interesting grandchildren papers scholar.google.com/… Maybe you could implement it in Haskell and see how it works? – Lidless

@Lidless Problem is, the description in the original ESA '06 paper is very vague and I can't really figure out how a Brodal tree really works just from that paper (after all, I am no expert in PFDS). That corresponds to (1), but I'm pretty sure that at least one expert has figured out how to actually implement it. – Typo

There is surprisingly no benchmark in the original paper. One very likely reason is that the constant factor is absurdly high and completely dwarf the algorithmic improvements. Trees need to behave decently also when creating lot's of small tree, which requires constants not to be too large. – Mckeehan

@Mckeehan There isn't even code or pseudocode in the original paper and I feel suspicious about that... – Typo

Aside from the difficulties others have mentioned, there are several significant problems. 1. The structure doesn't actually claim to support general merge in O(1) time. It only claims to support a much more restricted join function concatenating trees that are sorted relative to each other. Given a way to split trees, this operation is useful for parallel computation, but in that context logarithmic join is quite cheap enough for any practical purpose. 2. The structure doesn't support splitting at an element, and no efficient implementations are offered for unions, intersections, etc. – Clintclintock

Constant-time general merge (union) time would imply constant update (just merge with a singleton). – Earlie

Large constants should be a problem, because you can always optimize for smaller sizes: https://mcmap.net/q/501088/-why-are-sets-of-up-to-4-elements-ordered-but-larger-ones-are-not/1886510 – Pentosan

Answer 1

As mentioned in the comments there is very limited information in the paper, leading one to suspect very large constants, in addition:

1. The structure doesn't actually claim to support general merge in O(1) time. It only claims to support a much more restricted join function concatenating trees that are sorted relative to each other. Given a way to split trees, this operation is useful for parallel computation, but in that context logarithmic join is quite cheap enough for any practical purpose.
2. The structure doesn't support splitting at an element, and no efficient implementations are offered for unions, intersections, etc.

Somewhat overlapping with the above, reading the article I would think the following note from the conclusion may be why not much effort has been made toward implementation

Splitting will invalidate this property for every tree-collection and will lead to (log n log log n) search and update times.

Etherize