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) in Martin Erwig's "Diets for fat sets" (1993):
https://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf
My microbenchmark 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.
@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