RED BLACK TREE INSERTION

Red Black Tree Properties

• Every node is either red(0) or black(1)
• Root Node is always black
• Every leaf node which is null is black
• No two adjacent nodes can be red
• The black height of the tree remains consistent

Important Pointers for Insert Algorithm

• If the tree is empty, create a new node as a root node with the color black
• If the tree is not empty, create a new node as a leaf node with the color red
• If the parent of the leaf node is red, check the color of parent's sibling. If color is black then perform suitable rotation and recolor. If color is red, then only recolor and check for the grandparent(if the grandparent is root, leave it black else recolor and recheck).

For more information about the insert algorithm and other algorithms refer here: Red Black Trees