@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)...
@Elizafox if you want to watch a lecture from the woman who taught me, it's the "lecture 15" part of http://goldman.cse.wustl.edu/crc2007/lectures/compressed.html ; she's fantastic and even though this is material you've already seen maybe a different perspective from honestly the best professor I had would help.
