Skip to content

Instantly share code, notes, and snippets.

@Harshapriya123
Created October 22, 2019 16:59
Show Gist options
  • Save Harshapriya123/68fe55a0fc20e3358fb4fedfdbae7508 to your computer and use it in GitHub Desktop.
Save Harshapriya123/68fe55a0fc20e3358fb4fedfdbae7508 to your computer and use it in GitHub Desktop.
// C program for Red-Black Tree insertion
#include<stdio.h>
#include<stdlib.h>
//A Red-Black tree node structure
struct node
{
int data;
char color;
struct node *left, *right, *parent;
};
// Left Rotation
void LeftRotate(struct node **root,struct node *x)
{
if (!x || !x->right)
return ;
//y stored pointer of right child of x
struct node *y = x->right;
//store y's left subtree's pointer as x's right child
x->right = y->left;
//update parent pointer of x's right
if (x->right != NULL)
x->right->parent = x;
//update y's parent pointer
y->parent = x->parent;
// if x's parent is null make y as root of tree
if (x->parent == NULL)
(*root) = y;
// store y at the place of x
else if (x == x->parent->left)
x->parent->left = y;
else x->parent->right = y;
// make x as left child of y
y->left = x;
//update parent pointer of x
x->parent = y;
}
// Right Rotation (Similar to LeftRotate)
void rightRotate(struct node **root,struct node *y)
{
if (!y || !y->left)
return ;
struct node *x = y->left;
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
x->parent =y->parent;
if (x->parent == NULL)
(*root) = x;
else if (y == y->parent->left)
y->parent->left = x;
else y->parent->right = x;
x->right = y;
y->parent = x;
}
// Utility function to fixup the Red-Black tree after standard BST insertion
void insertFixUp(struct node **root,struct node *z)
{
// iterate until z is not the root and z's parent color is red
while (z != *root && z != (*root)->left && z != (*root)->right && z->parent->color == 'R')
{
struct node *y;
// Find uncle and store uncle in y
if (z->parent && z->parent->parent && z->parent == z->parent->parent->left)
y = z->parent->parent->right;
else
y = z->parent->parent->left;
// If uncle is RED, do following
// (i) Change color of parent and uncle as BLACK
// (ii) Change color of grandparent as RED
// (iii) Move z to grandparent
if (!y)
z = z->parent->parent;
else if (y->color == 'R')
{
y->color = 'B';
z->parent->color = 'B';
z->parent->parent->color = 'R';
z = z->parent->parent;
}
// Uncle is BLACK, there are four cases (LL, LR, RL and RR)
else
{
// Left-Left (LL) case, do following
// (i) Swap color of parent and grandparent
// (ii) Right Rotate Grandparent
if (z->parent == z->parent->parent->left &&
z == z->parent->left)
{
char ch = z->parent->color ;
z->parent->color = z->parent->parent->color;
z->parent->parent->color = ch;
rightRotate(root,z->parent->parent);
}
// Left-Right (LR) case, do following
// (i) Swap color of current node and grandparent
// (ii) Left Rotate Parent
// (iii) Right Rotate Grand Parent
if (z->parent && z->parent->parent && z->parent == z->parent->parent->left &&
z == z->parent->right)
{
char ch = z->color ;
z->color = z->parent->parent->color;
z->parent->parent->color = ch;
LeftRotate(root,z->parent);
rightRotate(root,z->parent->parent);
}
// Right-Right (RR) case, do following
// (i) Swap color of parent and grandparent
// (ii) Left Rotate Grandparent
if (z->parent && z->parent->parent &&
z->parent == z->parent->parent->right &&
z == z->parent->right)
{
char ch = z->parent->color ;
z->parent->color = z->parent->parent->color;
z->parent->parent->color = ch;
LeftRotate(root,z->parent->parent);
}
// Right-Left (RL) case, do following
// (i) Swap color of current node and grandparent
// (ii) Right Rotate Parent
// (iii) Left Rotate Grand Parent
if (z->parent && z->parent->parent && z->parent == z->parent->parent->right &&
z == z->parent->left)
{
char ch = z->color ;
z->color = z->parent->parent->color;
z->parent->parent->color = ch;
rightRotate(root,z->parent);
LeftRotate(root,z->parent->parent);
}
}
}
(*root)->color = 'B'; //keep root always black
}
// Utility function to insert newly node in RedBlack tree
void insert(struct node **root, int data)
{
// Allocate memory for new node
struct node *z = (struct node*)malloc(sizeof(struct node));
z->data = data;
z->left = z->right = z->parent = NULL;
//if root is null make z as root
if (*root == NULL)
{
z->color = 'B';
(*root) = z;
}
else
{
struct node *y = NULL;
struct node *x = (*root);
// Follow standard BST insert steps to first insert the node
while (x != NULL)
{
y = x;
if (z->data < x->data)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (z->data > y->data)
y->right = z;
else
y->left = z;
z->color = 'R';
// call insertFixUp to fix reb-black tree's property if it
// is voilated due to insertion.
insertFixUp(root,z);
}
}
// A utility function to traverse Red-Black tree in inorder fashion
void inorder(struct node *root)
{
static int last = 0;
if (root == NULL)
return;
inorder(root->left);
printf("%d ", root->data);
if (root->data < last)
printf("\nPUTE\n");
last = root->data;
inorder(root->right);
}
#include <time.h>
#define NB_ELEMS 250
/* Drier program to test above function*/
int main()
{
srandom(time(NULL));
struct node *root = NULL;
clock_t t0 = clock();
for (int i = 0; i < NB_ELEMS; ++i)
insert(&root, random());
clock_t t1 = clock();
printf("inorder Traversal Is :\n");
inorder(root);
printf("\n");
float time_taken = (float)(t1 - t0) / CLOCKS_PER_SEC * 1000;
printf("insertion took %fms -> %fus/elem\n",
time_taken,
time_taken / NB_ELEMS * 1000);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment