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

Note Detail

dave@dthompson@toot.cat (2026-10-26 22:10:54)
I read Chris Okasaki's "Red-Black Trees in a Functional Setting" (1993) paper over the weekend and it's brilliant. Pretty much all the resources on red-black trees out there describe very imperative algorithms but this paper describes a functional insert algorithm that is much simpler than anything else I've seen.

https://www.cs.tufts.edu/~nr/cs257/archive/chris-okasaki/redblack99.pdf

Unfortunately, Okasaki conveniently leaves out deletion! Red-black tree deletion is mind bending! Thankfully I'm not the first person to notice this. Kimball Germane and Matthew Might published a functional pearl of their own in 2014: "Deletion: The curse of the red-black tree"

https://matt.might.net/papers/germane2014deletion.pdf

I'm reading about all of this in an effort to add the balancing properties of red-black trees to the discrete interval encoding trees (diets) as described in Martin Erwig's "Diets for fat sets" (1993):

https://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf

My benchmarking is showing about a 10% improvement in set membership queries over the unbalanced version with a randomly generated large set. Maybe it's not worth all the effort but I don't really like implementing trees that *could* degenerate to O(n) query time.

---Replies---

dave@dthompson@toot.cat (2026-10-26 22:18:01)
The great thing about functional pearl papers is that they are short enough to be printed out so you can highlight and write notes on the pages and have it by your side while implementing.

Ludovic Courtès@civodul@toot.aquilenet.fr (2026-10-26 22:20:00)
@dthompson We need this in Guile proper!

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