Home | Notifications | New Note | Local | Federated | Search | Logout
Note Detail
Reply to @dthompson@toot.cat
pinoaffe@pinoaffe@hsnl.social (2026-10-26 22:38:56)
@dthompson I wonder if simply balancing the (sub)tree at every nth step would have decent (amortized) complexity, though it's not a very elegant solution. Alternatively, randomized (partial) rebalancing could perhaps work, but would be even uglier in my opinion
Back when I implemented diets, I also briefly considered a variant based on a binary search tree listing all x such that x is in the set but x + 1 is not in the set or vice versa, noting which of the two is the case for said x. However, I didn't end up fully working out the operations for this variant. I think that doing (something like) this with red-black trees would result in a self-balancing alternative to diets (if it works)
on a more general note, I feel like there is a scarcity of reusable "algorithms" written in scheme/guile, so I think I might dust off and polish up some of the stuff i have lying around
---Reply---
dave@dthompson@toot.cat (2026-10-26 23:02:12)
@pinoaffe my experience has been that the addition of red-black rebalancing rules to the insert operation works and is worth it. deletion is more complicated and I'm not done with implementation but it's probably worth the complexity. we could explore using a different balanced binary tree, as well, but red-black feels like a sweet spot between time spent rebalancing and query speed.
Reply
---Replies---
Robin H. Hansen@robinheghan@snabelen.no (2026-10-27 16:22:37)
@dthompson @pinoaffe I found this paper sometime last year. It uses the sub-tree height to determine the need for rotations. The benefit is that insert and remove are straight forward, and I believe performance is comparable to a red-black tree.
https://www.sciencedirect.com/science/article/pii/S0304397512010572?via%3Dihub