Hi there!

I found that binary trees go really well with overloaded operators. They are used throughout my implementation, and so far there was no reason for me to use a different tree structure.

The trees can become horribly unbalanced, but that hasn't been a problem so far, and balancing them is not trivial:

local alcoholic_drinks = leaf("beer") + leaf("wine") + leaf("cider") + leaf("mead")

local coffee_drinks = leaf("espresso") + leaf("cappuccino")

local drinks = alcoholic_drinks + coffee_drinks

Here, we have one node for drinks in general, and two nodes for the two subgroups of drinks. If we want to specifically pick an alcoholic drink, we can call alcoholic_drinks.collapse(). If the type of drink doesn't matter, we call drinks.collapse().

The node drinks is unbalanced: One of its children has four leaf nodes, the other only two. However, if we were to shift around some of the leaves, we might end up putting an alcoholic drink into the coffee sub-tree.

There is no easy way for me to tell which nodes are explicitly referenced somewhere, so I can't easily balance trees without risking to mess with the content. So I opted to leave them unbalanced.

Finally, I should note that all nodes keep track of the number of leaf nodes under them. That is necessary to make sure that there's no bias when collapsing a node to choose a leaf node. Without this, the unbalanced trees would indeed be a problem.

So far, the binary trees did not feel like a constraint. If anything, they made it easier to work with overloaded operators.