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.
---Reply---
Ludovic Courtès@civodul@toot.aquilenet.fr (2026-10-26 22:20:00)
@dthompson We need this in Guile proper!

---Replies---

dave@dthompson@toot.cat (2026-10-26 22:25:10)
@civodul so @pinoaffe has a WIP implementation of diets and was trying to implement character sets for Hoot using them:

https://codeberg.org/pinoaffe/guile-diet

https://codeberg.org/spritely/hoot/pulls/761

This code was from last year but it had been on my to-do list to understand how diets work. I finally got around to it and have been making my own separate implementation.