Insertion In Red Black Tree

Insertion In Red Black Tree:
There are three Cases for inserting  a node in Red Black Tree.1.Find the correct leaf to insert new node instead of it
2.Color node in red, and attach 2 black leafs to it
3.Make sure RB-tree properties hold

Insertion in red-black tree

Case 1: a’s uncle (d) is red:
1.Color a’s father (b) and uncle (d) black
2.Color a’s father (c) red

Insertion in red-black tree

   

Case 2: a’s uncle is black, a is a right child
1. Rotate left around a’s father (b)
2.Continue to case 3


Case 3: a’s uncle is black, a is a left child:
1. Rotate right around a’s grandfather (c)
2. Switch colors between a’s father (b)
and a’s (new) sibling (c)

Insertion in red-black tree