@Elizafox ...So painting the red root black adds 1 to the black depth of every single path simultaneously, since the root is the start of all paths - and then they're all equal again!
Also I realized I forgot the other rule for creating a black node, it doesn't always go through the root, sorry. (Black/black pairs can be "split".) But your fix-up algorithm only has to look at three layers of the tree at a time, working upwards from where your new red leaf comes in.