-
-
Save VictorGarritano/5f894be162d39e9bdd5c 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; // for data part | |
char color; // for color property | |
//links for left, right children and parent | |
struct node *left, *right, *parent; | |
}; | |
// Left Rotation | |
void LeftRotate(struct node **root,struct node *x) | |
{ | |
//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) | |
{ | |
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->parent->color == 'R') | |
{ | |
struct node *y; | |
// Find uncle and store uncle in y | |
if (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->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->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->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->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) | |
{ | |
if (root == NULL) | |
return; | |
inorder(root->left); | |
printf("%d ", root->data); | |
inorder(root->right); | |
} | |
/* Drier program to test above function*/ | |
int main() | |
{ | |
struct node *root = NULL; | |
insert(&root,10); | |
insert(&root,20); | |
insert(&root,40); | |
insert(&root,30); | |
insert(&root,50); | |
insert(&root,35); | |
insert(&root,25); | |
insert(&root,37); | |
printf("inorder Traversal Is : "); | |
inorder(root); | |
return 0; | |
} |
This implementation was a great inspiration for me because the code is very simplistic, I corrected the segfaults just by adding a few ifs (see below, it's not pretty).
I also made my own implementation from this, it's on my framagit (I have to adhere to a strict norm, please don't judge too much)
// 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;
}
Thanks a lot buddy you are awesome!
Thank u so much. The code is very simplistic and easy to understand.
guys, there here an error: if input 4-8-12 the three is not balanced
// Hey i just added few lines to check how it actually looks but there are RED-RED parent-child relationships at many points
// there are few errors in your code dude ( i just copied this code from here and hoping u don't get offend
// C program for Red-Black Tree insertion
#include<stdio.h>
#include<stdlib.h>
#define COUNT 10
void dis2d();
//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);
}
int main()
{
struct node* root=NULL;
printf("R&B");
while(1)
{
printf("\nenter operations\n1->insert 2->display 3->2d display\n");
int ch;
scanf("%d",&ch);
switch(ch)
{
case 0:return 0;
case 1:{
printf("enter data to insert\n");
int data;
scanf("%d",&data);
insert(&root,data);
}break;
case 2:inorder(root);break;
case 3:dis2d(root,0);break;
default:printf("please enter valid inputs");
}
}
}
void dis2d(struct node *root,int space)
{
if(root)
{
space+=COUNT;
dis2d(root->right,space);
printf("\n\n");
for(int i= COUNT; i<space; i++)
{
printf(" ");
}
printf("%d(%c)",root->data,root->color);
dis2d(root->left,space);
}
}
guys, there here an error: if input 4-8-12 the three is not balanced
yes dude Red-Black Trees are not strictly balanced like AVL-Trees
Thank you, nice code
Thank you :)
Thank you so much, it's help me a lot to understand!
The program is ending with a segmentation fault. Please fix it.