I've never understood the allure of red-black trees. One of the things I have on my agenda is to compare their performance with other, cooler, data structures,

I've never understood the allure of red-black trees. One of the things I have on my agenda is to compare their performance with other, cooler, data structures, to see if perhaps there's a practical reason to favor them. If it's just the rotations you like, there are umpteen more intuitive tree structures that use them too, like AVL.