Red-Black Tree Insertion

How to Insert Into a Red-Black Tree:

1. Insert the new value using the Binary Search Tree insertion algorithm
2. Color this new node (that you just inserted) red
3. Check if all the Red Black Tree properties are still true and repair if necessary, like this:
   • If the root node is red (violating property 2), then repair by recoloring the root node black
   • If a red node has a red child (violating property 3), then repair according to this diagram:
   

Find a helpful red-black tree visualization here!