Red Black Tree Insertion

This page contains steps to inserting in a red black tree

Steps of Insertion

1. Perform a standard BST insertion to insert new node and labeling it RED
2. If new node is the root change color to BLACK and stop
3. If parent is BLACK, stop. If parent is RED a violation exists
4. Check color of parent's sibling(uncle) to determine how to resolve violation
5. Case 1: Uncle is RED: Recolor parent and uncle to BLACK, and grandparent to RED. Move pointer to grandparent and repeat the fix-up process
6. Case 2: Uncle is BLACK or null: Perform rotations and recoloring based on whether the node is a left or right child
• If both red nodes are not in line with grandparent first rotate newNode and parent.
• Once in line rotate the grandparent and parent red node and color swap grandparent and parent. New grandparent should become black and old grandparent should become red.

Violaton Resolution Visual

Read more along with example code