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

Case 2

Case 3

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.