rtheunissen
Just Another GPT Wrapper
Regex101 is an excellent tool.
For instance, fewer values per node means less information to copy when copying the node. Locking is more granular with fewer values per node because fewer values are locked at a time.
The binary structure also makes it possible to support randomized balancing and self-adjusting strategies like splay trees.
I am disappointed to still see frequent mention of red-black trees – I see no reason for red-black trees to ever be the best choice in practice, or in theory, or in school. LBST's (logarithmic binary search trees) [1] are generally simpler, more intuitive, and more efficient [2] than red-black trees. They also support positional access inherently, so the balancing information is useful (subtree size).
[1] https://www.semanticscholar.org/paper/A-New-Method-for-Balan... [2] https://rtheunissen.github.io/bst
https://github.com/rtheunissen/bst/blob/main/trees%2Fbalance...
Show HN: Binary search tree shape animations using Go and WASM
My inclination towards lower abstraction in this project is entirely for the sake of reading and reference, to minimize the need for the reader to re-compose from various components split across files.
During development, abstraction helps because it makes prototyping faster and more consistent, but once everything is mostly "done", it can help the reader/student to maximize local reasoning.
Another comment mentioned they found it difficult to find the LBST implementation - this is exactly the sort of experience I hope to avoid.
Re: binary symmetry, if I'm understanding correctly, another author that makes use of the symmetry is Ben Pfaff in libavl [1]. At the top of [2], which seems a bit misplaced now, I wrote:
>A choice was made to not unify the symmetric cases using the direction-based technique of Ben Pfaff and others because it makes the logic more difficult to follow even though there would be less code overall.
The choice of Go was to provide implementations that are both reliable to benchmark (though not as robust as C or Rust for example) but also easy to read. I would like to further reduce abstraction by decomposing common parts such that all the strategies are "one-file" references. This is then effectively the opposite of what the macro-based implementation achieves. Both have value, of course.
[1] https://adtinfo.org/libavl.html/BST-Node-Structure.html
[2] https://github.com/rtheunissen/bst/blob/main/trees/avl_botto...
The Charter font was a particularly good find as part of the "transitional" system font stack. I'll definitely use it for other projects in the future.
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.
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
Focusing on fundamental algorithms in the abstract provides a fun playground to explore and learn and teach, before you learn about memory hierarchy when all your hopes and dreams of the ideal data structure fades away.
I don't think there is any time wasted exploring the fundamental. Who knows what technology might see renaissance in the future as hardware continues to change. Analog computers, binary search trees, who knows.
It's fun to dream and take a break from reality sometimes, digging deep into a simple concept with a rich design space and complex analysis.
There are also LLRB trees that would be interesting to see compared within this framework. All the red-black trees are implemented as rank-balanced trees, so there is no concept of "color" exactly, but the authors do mention the left-leaning 2-3 rule and the left-leaning red-black rule -- I just haven't implemented those yet.
See Pg. 5 of https://citeseerx.ist.psu.edu/document?type=pdf&doi=52330eed...
I tried to focus specifically on BSTs in the context of online persistence and concurrency, where they are particularly effective at very large sizes. There is a section on the paper that mentions B-trees but I did not want to include a direct comparison as part of the scope. Take the best candidate from this set, and compare against a good B-tree implementation in whatever situation you might require them.
Show HN: Exploring the design space of binary search trees
Instead, within just the scope of binary search trees specifically, what cool things might we uncover by taking a closer look. In a hypothetical future, our hardware might be so different and caches so large and advanced that the best practices of today might not apply all the same.
Binary search trees today are probably only viable for absolutely massive collections, and at that scale there is almost definitely a better, bespoke solution available. Exploring without necessarily thinking about the hardware, in the abstract, has been a fun sandbox to play in. The fact that we still teach them suggests that they provide value beyond practical application.
Thank you for your feedback, you are absolutely right. In most cases today, a B-tree would achieve better results in real use cases on real hardware.
Exploring the design space of binary search trees
My phone is always on low brightness at night, but for some reason my monitor is always at 100% without question, which means light theme during the day (to match paper/pencil in front of me) and dark theme at night because it is otherwise too much light. Then one day, I tried a light theme at night at 50% monitor brightness and my eyes relaxed immediately. I realized that I have been squinting constantly to brace against the maximum brightness.
The usual advice is to instead increase ambient/room light but I have the room light set perfectly for writing and reading on paper.