Home | Notifications | New Note | Local | Federated | Search | Logout

pinoaffe@pinoaffe@hsnl.social

christian, anarchist, tinkerer

hackerspace: @revspace
languages: nl, de, en
Joined: 2026-10-26 23:02:26
1 notes, 0 following, 0 followers

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