[emmanueloga_]

Some feedback on readability: the article utilizes the term "logarithmic weight-balance" 6 times without explaining what it is (and several more times after). On the 7th mention, it links to a paper: "Frias[40] published top-down logarithmic weight-balance trees in 2005, under advice from Roura." But the referenced paper doesn't mention logarithmic weight-balance even once, I think [40] calls them "Logarithmic binary search trees", and links to "Roura S., 2001, A new method for balancing binary search trees".

After reading the last paragraph:

"Any current red-black tree implementation in practice can be replaced by a logarithmic weight-balance tree to achieve better balance, better performance, and get positional access as a bonus, all with a simpler algorithm."

... it is clear the article is advocating for these, and the title should hence be something like "Advantages of logarithmic weight-balanced Trees over other balanced trees", or something like that, immediately followed by an explanation of what these are, and what other people call them.

The repository linked at the top includes a lot of stuff and makes it hard to find a logarithmic weight-balance tree implementation, lost in all other kinds of trees in there. Would be helpful to see a separated logarithmic weight-balanced tree go module for people looking forward studying its source code.

40: L. Frias, Extending STL maps using LBSTs, 2005.

[rtheunissen]

Part 2 defines that "a node is logarithmically weight-balanced if the binary log of the weights of its subtrees differ by no more than 1" and references Roura directly there. Roura uses the acronym LBST, which corresponds to the file trees/lbst.go in the repository. I hoped that this would be intuitive enough to follow.

They are definitely part of the class of weight-balanced trees, using the exact same algorithms as BB[a] trees, which are the classic weight-balanced trees.

When I started this project, it was unclear that the conclusion would advocate for them. In fact, I did not even know about them when I started. My intention was to focus on the exploration more than the conclusion. I'm in the process of writing another conclusion around relaxed balance as a concept, which could just as well be the title.

I appreciate this feedback very much. Perhaps the paper could mention specifically that Roura and Frias call the logarithmic binary search trees, abbreviated as LBST. The repository's README could also provide an index to each tree in the source.

For reference: the weight-balanced algorithms can be found in [1], [2] and [3]. The logarithmic weight-balance rules are defined in [4].

[1] https://github.com/rtheunissen/bst/blob/main/trees/wbst_bott...

[2] https://github.com/rtheunissen/bst/blob/main/trees/wbst_topd...

[3] https://github.com/rtheunissen/bst/blob/main/trees/wbst_rela...

[4] https://github.com/rtheunissen/bst/blob/main/trees/lbst.go

[emmanueloga_]

I'm glad it is helpful! Why not just calling them LBSTs as the papers do? Catchier than LWBT I think... (gotta think of the marketing side too) :-p

Thanks for the extra pointers!

[rtheunissen]

Haha true, that's a good point. There's also WAVL and RAVL for weak AVL and relaxed AVL, but no equivalent acronyms for the red-black variants. RRB is the same as Relaxed Radix-Balanced! In my notes I found it easier to avoid acronyms, and then "logarithmic binary search tree" became ambiguous because "aren't they all logarithmic (in height and complexity)?" I found that grouping them as part of the weight-balanced class of trees is the most intuitive, and I wish the original paper did the same, but that's okay.

What I'll do for now is mention specifically that the literature refer to them as LBSTs, and I'll add an index to each tree in the repository to make them easier to navigate. Thanks again.