Experiment-5
Aim: Implementing Red Black Tree
Theory:
A Red-Black Tree is a self-balancing Binary Search Tree (BST) that ensures O(log n) time for:
• Searching
• Insertion
• Deletion
It maintains balance through color properties and rotations.
Properties of a Red-Black Tree
A binary tree is a Red-Black Tree if it satisfies these 5 properties:
1. Node Color: Every node is either red or black.
2. Root Property: The root is always black.
3. Leaf Property: All leaves (NULL pointers) are considered black.
4. Red Property: A red node cannot have a red child (no two consecutive reds).
5. Black-Height Property: Every path from a node to its descendant NULL nodes must
have the same number of black nodes.
Program in C :
#include <stdio.h>
#include <stdlib.h>
enum Color { RED, BLACK };
struct Node {
int data;
enum Color color;
struct Node *left, *right, *parent;
};
struct Node *root = NULL;
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->color = RED;
newNode->left = newNode->right = newNode->parent = NULL;
return newNode;
}
// Rotate Left
void rotateLeft(struct Node **root, struct Node *x) {
struct Node *y = x->right;
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
y->parent = x->parent;
if (x->parent == NULL)
*root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
// Rotate Right
void rotateRight(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 (y->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;
}
// Fix Red-Black Tree violations
void fixViolation(struct Node **root, struct Node *pt) {
struct Node *parent_pt = NULL;
struct Node *grand_parent_pt = NULL;
while ((pt != *root) && (pt->color != BLACK) &&
(pt->parent->color == RED)) {
parent_pt = pt->parent;
grand_parent_pt = pt->parent->parent;
// Parent is left child of grandparent
if (parent_pt == grand_parent_pt->left) {
struct Node *uncle_pt = grand_parent_pt->right;
// Case 1: Uncle is RED
if (uncle_pt != NULL && uncle_pt->color == RED) {
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
} else {
// Case 2: pt is right child
if (pt == parent_pt->right) {
rotateLeft(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
// Case 3: pt is left child
rotateRight(root, grand_parent_pt);
enum Color temp = parent_pt->color;
parent_pt->color = grand_parent_pt->color;
grand_parent_pt->color = temp;
pt = parent_pt;
}
}
// Parent is right child of grandparent
else {
struct Node *uncle_pt = grand_parent_pt->left;
// Case 1: Uncle is RED
if (uncle_pt != NULL && uncle_pt->color == RED) {
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
} else {
// Case 2: pt is left child
if (pt == parent_pt->left) {
rotateRight(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
// Case 3: pt is right child
rotateLeft(root, grand_parent_pt);
enum Color temp = parent_pt->color;
parent_pt->color = grand_parent_pt->color;
grand_parent_pt->color = temp;
pt = parent_pt;
}
}
}
(*root)->color = BLACK;
}
// Insert a new node
void insert(struct Node **root, int data) {
struct Node *pt = createNode(data);
struct Node *y = NULL;
struct Node *x = *root;
// BST insertion
while (x != NULL) {
y = x;
if (pt->data < x->data)
x = x->left;
else
x = x->right;
}
pt->parent = y;
if (y == NULL)
*root = pt;
else if (pt->data < y->data)
y->left = pt;
else
y->right = pt;
// Fix Red-Black Tree property
fixViolation(root, pt);
}
// Inorder Traversal
void inorder(struct Node *root) {
if (root == NULL)
return;
inorder(root->left);
printf("%d(%s) ", root->data, (root->color == RED) ? "R" : "B");
inorder(root->right);
}
int main() {
int choice, val;
while (1) {
printf("\n\nRed-Black Tree Operations:\n");
printf("1. Insert\n");
printf("2. Display (Inorder)\n");
printf("3. Exit\n");
printf("Enter choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &val);
insert(&root, val);
break;
case 2:
printf("Inorder Traversal (Value(Color)):\n");
inorder(root);
printf("\n");
break;
case 3:
exit(0);
default:
printf("Invalid choice!\n");
}
}
return 0;
}
OUTPUT: