Skip to content

Instantly share code, notes, and snippets.

@VictorGarritano

VictorGarritano/red-black-tree.c

Created May 17, 2015 16:57
Show Gist options
  • Save VictorGarritano/5f894be162d39e9bdd5c to your computer and use it in GitHub Desktop.
Save VictorGarritano/5f894be162d39e9bdd5c to your computer and use it in GitHub Desktop.
Download ZIP
Raw
red-black-tree.c
// 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;
}
@AdityaGirishPawate
Copy link

AdityaGirishPawate commented Sep 26, 2019 •
edited
Loading

Thanks a lot buddy you are awesome!

@heyRahull
Copy link

Thank u so much. The code is very simplistic and easy to understand.

@GabrieleGatti866714
Copy link

guys, there here an error: if input 4-8-12 the three is not balanced

@danish1001
Copy link

danish1001 commented Sep 12, 2020 •
edited
Loading

// 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);
}
}

@danish1001
Copy link

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

@NietoCurcio
Copy link

Thank you, nice code

@yspkm
Copy link

yspkm commented Oct 3, 2022

Thank you :)

@mawulz
Copy link

mawulz commented Jun 1, 2023

Thank you so much, it's help me a lot to understand!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment