@Elizafox The other rule: the root is black, so you fix a red/red problem where the parent is the root by turning the root black. This is the only way to add black nodes - they rotate into the root. This happens when your rebalancing can't find a home for your extra red node so it makes it all the way to the root; all root-to-leaf paths are still "black equal" (because they were before you added a red node, your rotations don't change black depth, and your red node is red)...
