Red Black Tree

Red Black Tree

  8:38 PM    mayuravaani

---

Rules

• Self-balancing Binary Search Tree
• The node color can be either red or black (It is possible to have all black nodes but impossible to have all red nodes)
• The root node must be black
• There is no two red adjacent nodes (It will not have a parent and a child node in red color)
• NULL node is always black
• Every path from root to NULL node should have the same number of black nodes

Insertion

• If tree is empty, create a root node with black color
• If tree node is not empty, create a new child node as leaf node with red color
• If parent of new node is black then do nothing 
• If parent of new node is red then check the color of parent's sibling of new node (uncle of new node)
•      If the sibling node is black or NULL then do suitable rotation and re-color 
•      If the sibling node is red then re-color and check grand parent of new node
•         If grand parent is root then do nothing
•         else change the color of grand parent node and recheck 

Deletion