Insertion in a Red-Black Tree
In this tutorial, you will learn how a new node can be inserted into a red-black tree is. Also, you will find working examples of insertions performed on a red-black tree in C.
Red-Black tree is a self-balancing binary search tree in which each node contains an extra bit for denoting the color of the node, either red or black.
Before reading this article, please refer to the article on red-black tree.
While inserting a new node, the new node is always inserted as a RED node. After insertion of a new node, if the tree is violating the properties of the red-black tree then, we do the following operations.
- Recolor
- Rotation
Algorithm to Insert a New Node
Following steps are followed for inserting a new element into a red-black tree:
- The
newNode
be:
New node - Let y be the leaf (ie.
NIL
) andx
be the root of the tree. The new node is inserted in the following tree.
Initial tree - Check if the tree is empty (ie. whether
x
isNIL
). If yes, insertnewNode
as a root node and color it black. - Else, repeat steps following steps until leaf (
NIL
) is reached.- Compare
newKey
withrootKey
. - If
newKey
is greater thanrootKey
, traverse through the right subtree. - Else traverse through the left subtree.
Path leading to the node where newNode is to be inserted
- Compare
- Assign the parent of the leaf as parent of
newNode
. - If
leafKey
is greater thannewKey
, makenewNode
asrightChild
. - Else, make
newNode
asleftChild
.
New node inserted - Assign
NULL
to the left andrightChild
ofnewNode
. - Assign RED color to
newNode
.
Set the color of the newNode red and assign null to the children - Call InsertFix-algorithm to maintain the property of red-black tree if violated.
Why newly inserted nodes are always red in a red-black tree?
This is because inserting a red node does not violate the depth property of a red-black tree.
If you attach a red node to a red node, then the rule is violated but it is easier to fix this problem than the problem introduced by violating the depth property.
Algorithm to Maintain Red-Black Property After Insertion
This algorithm is used for maintaining the property of a red-black tree if insertion of a newNode violates this property.
- Do the following until the parent of
newNode
p
is RED. - If
p
is the left child ofgrandParent
gP
ofnewNode
, do the following.
Case-I:- If the color of the right child of
gP
ofnewNode
is RED, set the color of both the children ofgP
as BLACK and the color ofgP
as RED.
Color change - Assign
gP
tonewNode
.
Reassigning newNode Case-II:
- (Before moving on to this step, while loop is checked. If conditions are not satisfied, it the loop is broken.)
Else ifnewNode
is the right child ofp
then, assignp
tonewNode
.Assigning parent of newNode as newNode - Left-Rotate
newNode
.
Left Rotate Case-III:
- (Before moving on to this step, while loop is checked. If conditions are not satisfied, it the loop is broken.)
Set color ofp
as BLACK and color ofgP
as RED.Color change - Right-Rotate
gP
.
Right Rotate
- If the color of the right child of
- Else, do the following.
- If the color of the left child of
gP
ofz
is RED, set the color of both the children ofgP
as BLACK and the color ofgP
as RED. - Assign
gP
tonewNode
. - Else if
newNode
is the left child ofp
then, assignp
tonewNode
and Right-RotatenewNode
. - Set color of
p
as BLACK and color ofgP
as RED. - Left-Rotate
gP
.
- If the color of the left child of
- (This step is performed after coming out of the while loop.)
Set the root of the tree as BLACK.Set root’s color black
The final tree look like this:

C Examples
// Implementing Red-Black Tree in C
#include <stdio.h>
#include <stdlib.h>
enum nodeColor {
RED,
BLACK
};
struct rbNode {
int data, color;
struct rbNode *link[2];
};
struct rbNode *root = NULL;
// Create a red-black tree
struct rbNode *createNode(int data) {
struct rbNode *newnode;
newnode = (struct rbNode *)malloc(sizeof(struct rbNode));
newnode->data = data;
newnode->color = RED;
newnode->link[0] = newnode->link[1] = NULL;
return newnode;
}
// Insert an node
void insertion(int data) {
struct rbNode *stack[98], *ptr, *newnode, *xPtr, *yPtr;
int dir[98], ht = 0, index;
ptr = root;
if (!root) {
root = createNode(data);
return;
}
stack[ht] = root;
dir[ht++] = 0;
while (ptr != NULL) {
if (ptr->data == data) {
printf("Duplicates Not Allowed!!n");
return;
}
index = (data - ptr->data) > 0 ? 1 : 0;
stack[ht] = ptr;
ptr = ptr->link[index];
dir[ht++] = index;
}
stack[ht - 1]->link[index] = newnode = createNode(data);
while ((ht >= 3) && (stack[ht - 1]->color == RED)) {
if (dir[ht - 2] == 0) {
yPtr = stack[ht - 2]->link[1];
if (yPtr != NULL && yPtr->color == RED) {
stack[ht - 2]->color = RED;
stack[ht - 1]->color = yPtr->color = BLACK;
ht = ht - 2;
} else {
if (dir[ht - 1] == 0) {
yPtr = stack[ht - 1];
} else {
xPtr = stack[ht - 1];
yPtr = xPtr->link[1];
xPtr->link[1] = yPtr->link[0];
yPtr->link[0] = xPtr;
stack[ht - 2]->link[0] = yPtr;
}
xPtr = stack[ht - 2];
xPtr->color = RED;
yPtr->color = BLACK;
xPtr->link[0] = yPtr->link[1];
yPtr->link[1] = xPtr;
if (xPtr == root) {
root = yPtr;
} else {
stack[ht - 3]->link[dir[ht - 3]] = yPtr;
}
break;
}
} else {
yPtr = stack[ht - 2]->link[0];
if ((yPtr != NULL) && (yPtr->color == RED)) {
stack[ht - 2]->color = RED;
stack[ht - 1]->color = yPtr->color = BLACK;
ht = ht - 2;
} else {
if (dir[ht - 1] == 1) {
yPtr = stack[ht - 1];
} else {
xPtr = stack[ht - 1];
yPtr = xPtr->link[0];
xPtr->link[0] = yPtr->link[1];
yPtr->link[1] = xPtr;
stack[ht - 2]->link[1] = yPtr;
}
xPtr = stack[ht - 2];
yPtr->color = BLACK;
xPtr->color = RED;
xPtr->link[1] = yPtr->link[0];
yPtr->link[0] = xPtr;
if (xPtr == root) {
root = yPtr;
} else {
stack[ht - 3]->link[dir[ht - 3]] = yPtr;
}
break;
}
}
}
root->color = BLACK;
}
// Delete a node
void deletion(int data) {
struct rbNode *stack[98], *ptr, *xPtr, *yPtr;
struct rbNode *pPtr, *qPtr, *rPtr;
int dir[98], ht = 0, diff, i;
enum nodeColor color;
if (!root) {
printf("Tree not availablen");
return;
}
ptr = root;
while (ptr != NULL) {
if ((data - ptr->data) == 0)
break;
diff = (data - ptr->data) > 0 ? 1 : 0;
stack[ht] = ptr;
dir[ht++] = diff;
ptr = ptr->link[diff];
}
if (ptr->link[1] == NULL) {
if ((ptr == root) && (ptr->link[0] == NULL)) {
free(ptr);
root = NULL;
} else if (ptr == root) {
root = ptr->link[0];
free(ptr);
} else {
stack[ht - 1]->link[dir[ht - 1]] = ptr->link[0];
}
} else {
xPtr = ptr->link[1];
if (xPtr->link[0] == NULL) {
xPtr->link[0] = ptr->link[0];
color = xPtr->color;
xPtr->color = ptr->color;
ptr->color = color;
if (ptr == root) {
root = xPtr;
} else {
stack[ht - 1]->link[dir[ht - 1]] = xPtr;
}
dir[ht] = 1;
stack[ht++] = xPtr;
} else {
i = ht++;
while (1) {
dir[ht] = 0;
stack[ht++] = xPtr;
yPtr = xPtr->link[0];
if (!yPtr->link[0])
break;
xPtr = yPtr;
}
dir[i] = 1;
stack[i] = yPtr;
if (i > 0)
stack[i - 1]->link[dir[i - 1]] = yPtr;
yPtr->link[0] = ptr->link[0];
xPtr->link[0] = yPtr->link[1];
yPtr->link[1] = ptr->link[1];
if (ptr == root) {
root = yPtr;
}
color = yPtr->color;
yPtr->color = ptr->color;
ptr->color = color;
}
}
if (ht < 1)
return;
if (ptr->color == BLACK) {
while (1) {
pPtr = stack[ht - 1]->link[dir[ht - 1]];
if (pPtr && pPtr->color == RED) {
pPtr->color = BLACK;
break;
}
if (ht < 2)
break;
if (dir[ht - 2] == 0) {
rPtr = stack[ht - 1]->link[1];
if (!rPtr)
break;
if (rPtr->color == RED) {
stack[ht - 1]->color = RED;
rPtr->color = BLACK;
stack[ht - 1]->link[1] = rPtr->link[0];
rPtr->link[0] = stack[ht - 1];
if (stack[ht - 1] == root) {
root = rPtr;
} else {
stack[ht - 2]->link[dir[ht - 2]] = rPtr;
}
dir[ht] = 0;
stack[ht] = stack[ht - 1];
stack[ht - 1] = rPtr;
ht++;
rPtr = stack[ht - 1]->link[1];
}
if ((!rPtr->link[0] || rPtr->link[0]->color == BLACK) &&
(!rPtr->link[1] || rPtr->link[1]->color == BLACK)) {
rPtr->color = RED;
} else {
if (!rPtr->link[1] || rPtr->link[1]->color == BLACK) {
qPtr = rPtr->link[0];
rPtr->color = RED;
qPtr->color = BLACK;
rPtr->link[0] = qPtr->link[1];
qPtr->link[1] = rPtr;
rPtr = stack[ht - 1]->link[1] = qPtr;
}
rPtr->color = stack[ht - 1]->color;
stack[ht - 1]->color = BLACK;
rPtr->link[1]->color = BLACK;
stack[ht - 1]->link[1] = rPtr->link[0];
rPtr->link[0] = stack[ht - 1];
if (stack[ht - 1] == root) {
root = rPtr;
} else {
stack[ht - 2]->link[dir[ht - 2]] = rPtr;
}
break;
}
} else {
rPtr = stack[ht - 1]->link[0];
if (!rPtr)
break;
if (rPtr->color == RED) {
stack[ht - 1]->color = RED;
rPtr->color = BLACK;
stack[ht - 1]->link[0] = rPtr->link[1];
rPtr->link[1] = stack[ht - 1];
if (stack[ht - 1] == root) {
root = rPtr;
} else {
stack[ht - 2]->link[dir[ht - 2]] = rPtr;
}
dir[ht] = 1;
stack[ht] = stack[ht - 1];
stack[ht - 1] = rPtr;
ht++;
rPtr = stack[ht - 1]->link[0];
}
if ((!rPtr->link[0] || rPtr->link[0]->color == BLACK) &&
(!rPtr->link[1] || rPtr->link[1]->color == BLACK)) {
rPtr->color = RED;
} else {
if (!rPtr->link[0] || rPtr->link[0]->color == BLACK) {
qPtr = rPtr->link[1];
rPtr->color = RED;
qPtr->color = BLACK;
rPtr->link[1] = qPtr->link[0];
qPtr->link[0] = rPtr;
rPtr = stack[ht - 1]->link[0] = qPtr;
}
rPtr->color = stack[ht - 1]->color;
stack[ht - 1]->color = BLACK;
rPtr->link[0]->color = BLACK;
stack[ht - 1]->link[0] = rPtr->link[1];
rPtr->link[1] = stack[ht - 1];
if (stack[ht - 1] == root) {
root = rPtr;
} else {
stack[ht - 2]->link[dir[ht - 2]] = rPtr;
}
break;
}
}
ht--;
}
}
}
// Print the inorder traversal of the tree
void inorderTraversal(struct rbNode *node) {
if (node) {
inorderTraversal(node->link[0]);
printf("%d ", node->data);
inorderTraversal(node->link[1]);
}
return;
}
// Driver code
int main() {
int ch, data;
while (1) {
printf("1. Insertiont2. Deletionn");
printf("3. Traverset4. Exit");
printf("nEnter your choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter the element to insert:");
scanf("%d", &data);
insertion(data);
break;
case 2:
printf("Enter the element to delete:");
scanf("%d", &data);
deletion(data);
break;
case 3:
inorderTraversal(root);
printf("n");
break;
case 4:
exit(0);
default:
printf("Not availablen");
break;
}
printf("n");
}
return 0;
}
Python Example for Beginners
Two Machine Learning Fields
There are two sides to machine learning:
- Practical Machine Learning:This is about querying databases, cleaning data, writing scripts to transform data and gluing algorithm and libraries together and writing custom code to squeeze reliable answers from data to satisfy difficult and ill defined questions. It’s the mess of reality.
- Theoretical Machine Learning: This is about math and abstraction and idealized scenarios and limits and beauty and informing what is possible. It is a whole lot neater and cleaner and removed from the mess of reality.
Data Science Resources: Data Science Recipes and Applied Machine Learning Recipes
Introduction to Applied Machine Learning & Data Science for Beginners, Business Analysts, Students, Researchers and Freelancers with Python & R Codes @ Western Australian Center for Applied Machine Learning & Data Science (WACAMLDS) !!!
Latest end-to-end Learn by Coding Recipes in Project-Based Learning:
Applied Statistics with R for Beginners and Business Professionals
Data Science and Machine Learning Projects in Python: Tabular Data Analytics
Data Science and Machine Learning Projects in R: Tabular Data Analytics
Python Machine Learning & Data Science Recipes: Learn by Coding
R Machine Learning & Data Science Recipes: Learn by Coding
Comparing Different Machine Learning Algorithms in Python for Classification (FREE)
Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause. The information presented here could also be found in public knowledge domains.