7
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197
/** C implementation for Red-Black Tree Insertion**/
#include <stdio.h>
#include <stdlib.h>
// Structure to represent each
// node in a red-black tree
struct node {
int d; // data
int c; // 1-red, 0-black
struct node* p; // parent
struct node* r; // right-child
struct node* l; // left child
};
// global root for the entire tree
struct node* root = NULL;
// function to perform BST insertion of a node
struct node* bst(struct node* trav,
struct node* temp)
{
// If the tree is empty,
// return a new node
if (trav == NULL)
return temp;
// Otherwise recur down the tree
if (temp->d < trav->d)
{
trav->l = bst(trav->l, temp);
trav->l->p = trav;
}
else if (temp->d > trav->d)
{
trav->r = bst(trav->r, temp);
trav->r->p = trav;
}
// Return the (unchanged) node pointer
return trav;
}
// Function performing right rotation
// of the passed node
void rightrotate(struct node* temp)
{
struct node* left = temp->l;
temp->l = left->r;
if (temp->l)
temp->l->p = temp;
left->p = temp->p;
if (!temp->p)
root = left;
else if (temp == temp->p->l)
temp->p->l = left;
else
temp->p->r = left;
left->r = temp;
temp->p = left;
}
// Function performing left rotation
// of the passed node
void leftrotate(struct node* temp)
{
struct node* right = temp->r;
temp->r = right->l;
if (temp->r)
temp->r->p = temp;
right->p = temp->p;
if (!temp->p)
root = right;
else if (temp == temp->p->l)
temp->p->l = right;
else
temp->p->r = right;
right->l = temp;
temp->p = right;
}
// This function fixes violations
// caused by BST insertion
void fixup(struct node* root, struct node* pt)
{
struct node* parent_pt = NULL;
struct node* grand_parent_pt = NULL;
while ((pt != root) && (pt->c != 0)
&& (pt->p->c == 1))
{
parent_pt = pt->p;
grand_parent_pt = pt->p->p;
/* Case : A
Parent of pt is left child
of Grand-parent of
pt */
if (parent_pt == grand_parent_pt->l)
{
struct node* uncle_pt = grand_parent_pt->r;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle_pt != NULL && uncle_pt->c == 1)
{
grand_parent_pt->c = 1;
parent_pt->c = 0;
uncle_pt->c = 0;
pt = grand_parent_pt;
}
else {
/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt == parent_pt->r) {
leftrotate(parent_pt);
pt = parent_pt;
parent_pt = pt->p;
}
/* Case : 3
pt is left child of its parent
Right-rotation required */
rightrotate(grand_parent_pt);
int t = parent_pt->c;
parent_pt->c = grand_parent_pt->c;
grand_parent_pt->c = t;
pt = parent_pt;
}
}
/* Case : B
Parent of pt is right
child of Grand-parent of
pt */
else {
struct node* uncle_pt = grand_parent_pt->l;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if ((uncle_pt != NULL) && (uncle_pt->c == 1))
{
grand_parent_pt->c = 1;
parent_pt->c = 0;
uncle_pt->c = 0;
pt = grand_parent_pt;
}
else {
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt == parent_pt->l) {
rightrotate(parent_pt);
pt = parent_pt;
parent_pt = pt->p;
}
/* Case : 3
pt is right child of its parent
Left-rotation required */
leftrotate(grand_parent_pt);
int t = parent_pt->c;
parent_pt->c = grand_parent_pt->c;
grand_parent_pt->c = t;
pt = parent_pt;
}
}
}
root->c = 0;
}
// Function to print inorder traversal
// of the fixated tree
void inorder(struct node* trav)
{
if (trav == NULL)
return;
inorder(trav->l);
printf("%d ", trav->d);
inorder(trav->r);
}
// driver code
int main()
{
int n = 7;
int a[7] = { 7, 6, 5, 4, 3, 2, 1 };
for (int i = 0; i < n; i++) {
// allocating memory to the node and initializing:
// 1. color as red
// 2. parent, left and right pointers as NULL
// 3. data as i-th value in the array
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->r = NULL;
temp->l = NULL;
temp->p = NULL;
temp->d = a[i];
temp->c = 1;
// calling function that performs bst insertion of
// this newly created node
root = bst(root, temp);
// calling function to preserve properties of rb
// tree
fixup(root, temp);
}
printf("Inorder Traversal of Created Tree\n");
inorder(root);
return 0;
}
C
INFO