# Red Black Tree Insert Algorithm

## Insert

This method **always** inserts a red the end of a Red Black Tree

This Introduces a Red Node with a Red Child violation that needs to be fixed

Here are the three cases of fixing the violation

- Case 1: Red child's parent and parent's sibling are both Red
- Case 2: Red child is on the same side as the parent's sibling
- Case 3: Red child is on the opposite side as the parent's sibling

## Case 1

- 1. Make the parent and parent's sibling black
- 2. Make the grandparent red
- 3. If the grandparent is the root, make the grandparent black
- 4. Keep moving up the tree to fix any violations introduced after

## Case 2

- 1. Rotate the parent and the child
- 2. This will lead to Case 3

## Case 3

- 1. Rotate and color swap the parent and grandparent
- 2. Keep moving up the tree to fix any violations introduced after

**THE ROOT OF THE TREE SHOULD BE BLACK AFTER FIXING THE RED BLACK TREE VIOLATIONS**

Here is a another resource more information about the insert algorithm.