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 : :


/*  C Program to implement Red Black Tree Insertion  algorithm  */

#include <stdio.h>
#include <stdlib.h>

struct node
{
	enum {black, red} color;
	int info;
	struct  node *lchild;
	struct  node *rchild;
	struct  node *parent;
};

void insert (int);
void insert_balance(struct node *nptr );
void RotateLeft(struct node *ptr);
void RotateRight(struct node *ptr);
void display(struct node *ptr,int level);

struct node *root;
struct node *sentinel;/*will be parent of root node and replace NULL */

int main()
{
	int choice,num;

	sentinel = (struct node *) malloc(sizeof(struct node));
	sentinel->info = -1;
	sentinel->color = black;
	root = sentinel;

	while(1)
	{
		printf("\n");
		printf("1.Insert\n");
		printf("2.Display\n");
		printf("3.Quit\n");
		printf("\nEnter your choice : ");
		scanf("%d",&choice);

		switch(choice)
		{
		 case 1:
			printf("\nEnter the number to be inserted : ");
			scanf("%d",&num);
			insert(num);
			break;

		 case 2:
		     printf("\n");
			 display(root,0);
			 printf("\n");
			 break;

		 case 3:
			exit(1);


		 default:
			printf("Wrong choice\n");

		}/*End of switch */
	}/*End of while */

	return 0;

}/*End of main()*/

void insert (int ikey )
{
	struct node *tmp, *ptr, *par;

	par = sentinel;
	ptr = root;

	while( ptr != sentinel )
	{
		par = ptr;
		if( ikey < ptr->info )
			ptr = ptr->lchild;
		else if( ikey > ptr->info )
			ptr = ptr->rchild;
		else
		{
			printf("Duplicate\n");
			return;
		}
	}
	tmp = (struct node *) malloc(sizeof(struct node));
	tmp->info = ikey;
	tmp->lchild = sentinel;
	tmp->rchild = sentinel;
	tmp->color = red;
	tmp->parent = par;

	if(par==sentinel)
		root = tmp;
	else if(tmp ->info < par->info )
		par->lchild = tmp;
	else
		par->rchild = tmp;

	insert_balance(tmp);
}/*End of insert( )*/

void insert_balance(struct node *nptr )
{
	struct node *uncle, *par, *grandPar;

	while( nptr->parent->color == red )
	{
		par = nptr->parent;
		grandPar = par->parent;

		if( par == grandPar->lchild )
		{
			uncle = grandPar->rchild;

			if(uncle->color == red )	/* Case L_1 */
			{
				par->color = black;
				uncle->color = black;
				grandPar->color =red;
				nptr = grandPar;
			}
			else	/* Uncle is black */
			{
				if( nptr == par->rchild) /* Case L_2a */
				{
					RotateLeft(par);
					nptr = par;
					par = nptr->parent;
				}
				par->color = black;	 /* Case L_2b */
				grandPar->color = red;
				RotateRight(grandPar);
			}
		}
		else
		{
			if(par == grandPar->rchild )
			{
				uncle = grandPar->lchild;

				if(uncle->color == red )  /* Case R_1 */
				{
					par->color = black;
					uncle->color = black;
					grandPar->color =red;
					nptr = grandPar;
				}
				else	/*uncle is black */
				{
					if( nptr == par->lchild)   /* Case R_2a */
					{
						RotateRight(par);
						nptr = par;
						par = nptr->parent;
					}
					par->color = black;    /* Case R_2b */
					grandPar->color = red;
					RotateLeft(grandPar);
				}
			}
		}
	}
	root->color = black;
}/*End of insert_balance()*/


void RotateLeft(struct node *pptr)
{
	struct node *aptr;

	aptr = pptr->rchild;	/*aptr is right child of pptr*/
	pptr->rchild= aptr->lchild;

	if(aptr->lchild !=sentinel)
        aptr->lchild->parent = pptr;

	aptr->parent = pptr->parent;

	if(pptr->parent == sentinel )
		root = aptr;
	else if( pptr == pptr->parent->lchild )
		pptr->parent->lchild = aptr;
	else
		pptr->parent->rchild = aptr;
    aptr->lchild = pptr;
	pptr->parent = aptr;
}/*End of RoatateLeft( )*/

void RotateRight(struct node *pptr)
{
	struct node *aptr;

	aptr = pptr->lchild;
	pptr->lchild= aptr->rchild;

	if(aptr->rchild !=sentinel )
        aptr->rchild->parent = pptr;

	aptr->parent = pptr->parent;

	if(pptr->parent == sentinel )
		root = aptr;
	else if( pptr == pptr->parent->rchild )
		pptr->parent->rchild = aptr;
	else
		pptr->parent->lchild = aptr;

	aptr->rchild = pptr;
	pptr->parent = aptr;
}/*End of RotateRight( )*/


void display(struct node *ptr,int level)
{
	int i;
	if ( ptr!=sentinel )
	{
		display(ptr->rchild, level+1);
		printf("\n");
		for(i=0; i<level; i++)
			printf("    ");
		printf("%d", ptr->info);
		if(ptr->color==red)
			printf("R");
		else
			printf("B");
		display(ptr->lchild, level+1);
	}
}/*End of display()*/

OUTPUT : :


/*  C Program to implement Red Black Tree Insertion  algorithm  */

---------------------------------------------------------------------------------------------

Create a Red Black Tree by inserting following sequence of numbers :: 
                       8, 18, 5, 15, 17, 25, 40, 80 

----------------------------------------------------------------------------------------------

1.Insert
2.Display
3.Quit

Enter your choice : 1

Enter the number to be inserted : 8

1.Insert
2.Display
3.Quit

Enter your choice : 2


8B

1.Insert
2.Display
3.Quit

Enter your choice : 1

Enter the number to be inserted : 18

1.Insert
2.Display
3.Quit

Enter your choice : 2


    18R
8B

1.Insert
2.Display
3.Quit

Enter your choice : 1

Enter the number to be inserted : 5

1.Insert
2.Display
3.Quit

Enter your choice : 2


    18R
8B
    5R

1.Insert
2.Display
3.Quit

Enter your choice : 1

Enter the number to be inserted : 15

1.Insert
2.Display
3.Quit

Enter your choice : 2


    18B
        15R
8B
    5B

1.Insert
2.Display
3.Quit

Enter your choice : 1

Enter the number to be inserted : 17

1.Insert
2.Display
3.Quit

Enter your choice : 2


        18R
    17B
        15R
8B
    5B

1.Insert
2.Display
3.Quit

Enter your choice : 1

Enter the number to be inserted : 25

1.Insert
2.Display
3.Quit

Enter your choice : 2


            25R
        18B
    17R
        15B
8B
    5B

1.Insert
2.Display
3.Quit

Enter your choice : 1

Enter the number to be inserted : 40

1.Insert
2.Display
3.Quit

Enter your choice : 2


            40R
        25B
            18R
    17R
        15B
8B
    5B

1.Insert
2.Display
3.Quit

Enter your choice : 1

Enter the number to be inserted : 80

1.Insert
2.Display
3.Quit

Enter your choice : 2


            80R
        40B
    25R
        18B
17B
        15B
    8R
        5B

1.Insert
2.Display
3.Quit

Enter your choice : 3

Process returned 1

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