Inserting a new node into a Red-Black tree

Just like the AVL tree, when we insert a new node into a Red-Black tree, some structural property/properties may become invalid

We will need to fix the resulting tree to restore these properties:

Each node in the binary search tree is labeled either as red or as black
The root node is always labeled as black
All the leaf nodes are always labeled as black
Every red node must have 2 black children nodes
(There is no child constraint on black (parent) nodes)
Every path from root node → leaf node must have the same number of black nodes

Intro to insertion into a Red-Black tree

The "generic" insert algorithm for the Red-Black tree is as follows...

Let N be the new node that is inserted.

The insert algorithm for the Red-Black tree:

Insert the node N using the Binary Search Tree insertion algorithm
(Recall: the node N will be inserted in a leaf node position)
Color the node N as RED
Check for any property violations and fix it
There will be 4 different cases that we must consider (and fix)
(There are actually 6 different cases to consider, but 2 of the cases are symmetric)

Example of insertion into a Red-Black tree
- Initial Red-Black tree:
- Insert the node 10:
  Result:
  The resulting tree satisfies all properties of the Red-Black tree and we are DONE !!!
Another example of insertion into a Red-Black tree
- Initial Red-Black tree:
- Insert the node 7:
  Result:
  The resulting tree violates the property #4 of the Red-Black tree !!