Scribd
Upload
9 views7 pages

Red-Black Tree Implementation

The document outlines the implementation of a Red-Black Tree (RBT) that supports insertion, deletion, searching, and traversal. It describes the properties of RBTs, the methodology for insertion and deletion operations, and provides a complete implementation in C. The code includes functions for creating nodes, performing rotations, fixing violations, and traversing the tree in sorted order.

Uploaded by

Amal Waghas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views7 pages

Red-Black Tree Implementation

The document outlines the implementation of a Red-Black Tree (RBT) that supports insertion, deletion, searching, and traversal. It describes the properties of RBTs, the methodology for insertion and deletion operations, and provides a complete implementation in C. The code includes functions for creating nodes, performing rotations, fixing violations, and traversing the tree in sorted order.

Uploaded by

Amal Waghas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

RED-BLACK TREE IMPLEMENTATION

Aim
To implement a Red-Black Tree (RBT) to support:
●​ Insertion
●​ Deletion
●​ Searching & Traversal

Methodology

A Red-Black Tree is a Binary Search Tree (BST) with additional coloring rules:

Properties of RBT
1.​ Every node is either Red or Black.​

2.​ The root is always Black.​

3.​ No two consecutive red nodes are allowed (red node cannot have red parent).​

4.​ Every path from root to a leaf/null node has the same number of black nodes
(black-height).​

5.​ Null leaves are considered Black.​

Operations
(a) Insertion
1.​ Insert the new node as in a BST.
2.​ Color the new node Red.
3.​ Fix violations by rotations and recoloring (using parent, uncle, and grandparent
relations).​

(b) Deletion
1.​ Standard BST deletion (replace with successor if needed).
2.​ Fix double-black cases using rotations and recoloring.​

(c) Traversal
●​ Inorder Traversal: Sorted order of keys.
Implementation 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* NIL;


struct Node* root = NULL;

struct Node* createNode(int data) {


struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->color = RED;
node->left = NIL;
node->right = NIL;
node->parent = NULL;
return node;
}

void leftRotate(struct Node* x) {


struct Node* y = x->right;
x->right = y->left;
if (y->left != NIL) 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;
}

void rightRotate(struct Node* x) {


struct Node* y = x->left;
x->left = y->right;
if (y->right != NIL) y->right->parent = x;
y->parent = x->parent;
if (x->parent == NULL) root = y;
else if (x == x->parent->right) x->parent->right = y;
else x->parent->left = y;
y->right = x;
x->parent = y;
}

void fixInsert(struct Node* k) {


while (k->parent && k->parent->color == RED) {
if (k->parent == k->parent->parent->left) {
struct Node* u = k->parent->parent->right;
if (u->color == RED) {
k->parent->color = BLACK;
u->color = BLACK;
k->parent->parent->color = RED;
k = k->parent->parent;
} else {
if (k == k->parent->right) {
k = k->parent;
leftRotate(k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
rightRotate(k->parent->parent);
}
} else {
struct Node* u = k->parent->parent->left;
if (u->color == RED) {
k->parent->color = BLACK;
u->color = BLACK;
k->parent->parent->color = RED;
k = k->parent->parent;
} else {
if (k == k->parent->left) {
k = k->parent;
rightRotate(k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
leftRotate(k->parent->parent);
}
}
}
root->color = BLACK;
}

void insert(int data) {


struct Node* node = createNode(data);
struct Node* y = NULL;
struct Node* x = root;
while (x != NIL) {
y = x;
if (node->data < x->data) x = x->left;
else x = x->right;
}
node->parent = y;
if (y == NULL) root = node;
else if (node->data < y->data) y->left = node;
else y->right = node;
fixInsert(node);
}

struct Node* minimum(struct Node* node) {


while (node->left != NIL) node = node->left;
return node;
}

void transplant(struct Node* u, struct Node* v) {


if (u->parent == NULL) root = v;
else if (u == u->parent->left) u->parent->left = v;
else u->parent->right = v;
v->parent = u->parent;
}

void fixDelete(struct Node* x) {


while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
struct Node* s = x->parent->right;
if (s->color == RED) {
s->color = BLACK;
x->parent->color = RED;
leftRotate(x->parent);
s = x->parent->right;
}
if (s->left->color == BLACK && s->right->color == BLACK) {
s->color = RED;
x = x->parent;
} else {
if (s->right->color == BLACK) {
s->left->color = BLACK;
s->color = RED;
rightRotate(s);
s = x->parent->right;
}
s->color = x->parent->color;
x->parent->color = BLACK;
s->right->color = BLACK;
leftRotate(x->parent);
x = root;
}
} else {
struct Node* s = x->parent->left;
if (s->color == RED) {
s->color = BLACK;
x->parent->color = RED;
rightRotate(x->parent);
s = x->parent->left;
}
if (s->right->color == BLACK && s->left->color == BLACK) {
s->color = RED;
x = x->parent;
} else {
if (s->left->color == BLACK) {
s->right->color = BLACK;
s->color = RED;
leftRotate(s);
s = x->parent->left;
}
s->color = x->parent->color;
x->parent->color = BLACK;
s->left->color = BLACK;
rightRotate(x->parent);
x = root;
}
}
}
x->color = BLACK;
}

void delete(int data) {


struct Node* z = root;
while (z != NIL && z->data != data) {
if (data < z->data) z = z->left;
else z = z->right;
}
if (z == NIL) return;
struct Node* y = z;
enum Color y_original_color = y->color;
struct Node* x;
if (z->left == NIL) {
x = z->right;
transplant(z, z->right);
} else if (z->right == NIL) {
x = z->left;
transplant(z, z->left);
} else {
y = minimum(z->right);
y_original_color = y->color;
x = y->right;
if (y->parent == z) x->parent = y;
else {
transplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
if (y_original_color == BLACK) fixDelete(x);
}

void inorder(struct Node* node) {


if (node != NIL) {
inorder(node->left);
printf("%d(%s) ", node->data, node->color == RED ? "R" : "B");
inorder(node->right);
}
}

int main() {
NIL = (struct Node*)malloc(sizeof(struct Node));
NIL->color = BLACK;
NIL->left = NIL->right = NIL->parent = NULL;
root = NIL;

int arr[] = {20, 15, 25, 10, 5, 1, 30, 28};


for (int i = 0; i < 8; i++) insert(arr[i]);

printf("Inorder: ");
inorder(root);

printf("\nDeleting 15...\n");
delete(15);
inorder(root);

return 0;
}

Output

You might also like