C Program to implement Red Black Tree Insertion Algorithm

By | April 23, 2017

Red Black Tree Insertion Algorithm


Write a C Program to implement Red Black Tree Insertion Algorithm. Here’s simple Program to implement Red Black Tree Insertion Algorithm in C Programming Language.


What is Red Black Tree ?


Red-Black Tree is a self-balancing Binary Search Tree (BST) where every node follows following rules.

1) Every node has a color either red or black.

2) Root of tree is always black.

3) There are no two adjacent red nodes (A red node cannot have a red parent or red child).

4) Every path from root to a NULL node has same number of black nodes.


RED BLACK Tree Insertion :


In a Red Black Tree, every new node must be inserted with color RED. The Red Black Tree Insertion 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
  • 2. Rotation followed by Recolor

The Red Black tree insertion 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.

Below is the source code for C Program to implement Red Black Tree Insertion Algorithm which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :



OUTPUT : :



If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post….

Leave a Reply