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---
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.
Reply
---Replies---
dave@dthompson@toot.cat (2026-10-29 01:06:42)
something I realized last night: since diets are a sort of meta-tree that can delete nodes during insert (when the new interval overlaps or is adjacent to two existing intervals) and add nodes during deletion (when the interval to be deleted is a subset of an existing interval), that means that both operations need to incorporate the red-black tree insertion and deletion algorithms.