This is cool. I've never done a production grade tree like this, but implementing a toy immutable AVL tree you bump into the issue of rebuilding subtrees when modifying a node deep in the tree. According to Eric's notes, it seems that the red tree internally can be mutated when it needs to be edited.