@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 yeah, red black trees were by far the hardest thing in Algorithms for me, and according to Dr. Goldman it was the hardest thing for everyone including her; "delete a node" was extra credit for our homework because it was considered too difficult for the main implementation
@Elizafox the easiest way to make sense of it is to just pretend that the tree was fine before you added a node to it, and then you can fix it so it's okay again, and you don't have to worry about the rest. "the cool part" about red-black trees is how they figure out that they need to rebalance - the red-red rule is the only one necessary because it's the only rule that inserting a red node can break
@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.
