Rules of Red-black trees

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.

See this YouTube video for more information about Red-black tree insertions. We are looking at one specific case in this webpage.

Here is an image of a Red-black tree color violation with a red uncle.

Handling a color violation with a red uncle

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