Red-black tree rule 1:

Every node is either red or black.

Red-black tree rule 2:

If a node is one color, its child is the opposite color.

Red-black tree rule 3:

Every path from a given node to leaf nodes contains the same number of black nodes.

• Step 1: Change color of parent and uncle
• Step 2: Change color of grandparent
• Step 3: Check for violations up the tree