Red Black Tree

Red - Black Tree is another varient of Binary Search Tree in which every node is colored either RED or BLACK. We can define a Red Black Tree as follows...
Red Black Tree is a Binary Search Tree in which every node is colored eigther RED or BLACK.
In a Red Black Tree the color of a node is decided based on the Red Black Tree properties. Every Red Black Tree has the following properties.

Properties of Red Black Tree

  • Property #1: Red - Black Tree must be a Binary Search Tree.
  • Property #2: The ROOT node must colored BLACK.
  • Property #3: The children of Red colored node must colored BLACK. (There should not be two consecutive RED nodes).
  • Property #4: In all the paths of the tree there must be same number of BLACK colored nodes.
  • Property #5: Every new node must inserted with RED color.
  • Property #6: Every leaf (e.i. NULL node) must colored BLACK.

Example

THe following is a Red Black Tree which created by inserting numbers from 1 to 9.
The above tree is a Red Black tree and every node is satisfying all the properties of Red Black Tree.
Every Red Black Tree is a binary search tree but all the Binary Search Trees need not to be Red Black trees.

Insertion into RED BLACK Tree:

In a Red Black Tree, every new node must be inserted with color RED. The insertion operation in Red Black Tree is similar to insertion operation in Binary Search Tree. But it is inserted with a color property. After every insertion operation, we need to check all the properties of Red Black Tree. If all the properties are satisfied then we go to next operation otherwise we need to perform following operation to make it Red Black Tree.
  • 1. Recolor
  • 3. Rotation followed by Recolor
The insertion operation in Red Black tree is performed using following steps...
  • Step 1: Check whether tree is Empty.
  • Step 2: If tree is Empty then insert the newNode as Root node with color Black and exit from the operation.
  • step 3: If tree is not Empty then insert the newNode as a leaf node with Red color.
  • Step 4: If the parent of newNode is Black then exit from the operation.
  • Step 5: If the parent of newNode is Red then check the color of parent node's sibling of newNode.
  • Step 6: If it is Black or NULL node then make a suitable Rotation and Recolor it.
  • Step 7: If it is Red colored node then perform Recolor and Recheck it. Repeat the same until tree becomes Red Black Tree.

Example

Deletion Operation in Red Black Tree

In a Red Black Tree, the deletion operation is similar to deletion operation in BST. But after every deletion operation we need to check with the Red Black Tree properties. If any of the property is voilated then make suitable operation like Recolor or Rotaton & Recolor.