- Because they ensure balanced binary search trees, red-black trees are an essential component of computer science.
- We provide a thorough understanding of this crucial data structure by going over all of its aspects, such as color coding, rotations, and the methodical procedure to keep the balance during insertion.
Understanding Red-Black Trees
Understanding the properties and rules of Red-Black Trees is crucial before delving into the implementation details.
1. Binary Search Tree (BST) Property:
Functioning as a binary search tree, the Red-Black Tree adheres to the characteristics of a binary tree where every node can have up to two children. Within the tree, all nodes in the left subtree contain values that are less than the node's value, whereas all nodes in the right subtree contain values that are greater.
2. Coloring Scheme
Every node in a red-black tree is given one of two colors: either black or red. A node's color denotes specific characteristics that guarantee the balance of the tree. These attributes are:
- Each node has two colors: red and black.
- The tree's roots are always black.
- All of the leaf nodes (NIL) are dark.
- There cannot be any consecutive red nodes along any path if a node's children are red.
- There must be an equal number of black nodes on any simple path that leads from a node to any of its child leaf nodes.
To uphold the equilibrium of the tree, these traits are implemented to guarantee that the maximum distance from the root to any leaf is never more than double the length of the shortest path.
3. Rotations
Red-Black Trees utilize both left- and right-rotations to maintain their properties when adding or removing nodes. These rotations are essential for restructuring the tree while keeping intact the color distinctions and Binary Search Tree rules.
Let's delve into the comprehensive explanation of the Red-Black Tree insertion procedure in the C programming language.
Red-Black Tree Insertion Algorithm
The procedures below will be used to put the Red-Black Tree insertion method into practice:
- Insert a binary search tree (BST) conventionally.
- The newly inserted node should be colored red.
- To preserve the Red-Black Tree's characteristics, make the required rotations and recolors of the nodes.
Here's the C code for the Red-Black Tree algorithm:
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a Red-Black Tree node
struct Node {
int data;
struct Node* parent;
struct Node* left;
struct Node* right;
int color; // 0 for black, 1 for red
};
// Global pointers for the root and NIL (sentinel) nodes
struct Node* root = NULL;
struct Node* NIL = NULL;
// Function to perform left rotation
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;
}
// Function to perform right rotation
void right rotate(struct Node* y) {
struct Node* x = y->left;
y->left = x->right;
if (x->right != NIL) {
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;
}
// Function to fix the Red-Black Tree properties after insertion
void insertFixUp(struct Node* z) {
while (z->parent != NULL && z->parent->color == 1) {
if (z->parent == z->parent->parent->left) {
struct Node* y = z->parent->parent->right; // Uncle of z
if (y->color == 1) {
// Case 1: z's uncle is red
z->parent->color = 0; // Set parent to black
y->color = 0; // Set uncle to black
z->parent->parent->color = 1; // Set grandparent to red
z = z->parent->parent; // Move to the grandparent
} else {
if (z == z->parent->right) {
// Case 2: z's uncle is black, and z is a right child
z = z->parent;
leftRotate(z); // Transform into Case 3
}
// Case 3: z's uncle is black, and z is a left child
z->parent->color = 0; // Set parent to black
z->parent->parent->color = 1; // Set grandparent to red
rightRotate(z->parent->parent);
}
} else {
// Symmetric cases with left and right swapped
struct Node* y = z->parent->parent->left;
if (y->color == 1) {
z->parent->color = 0;
y->color = 0;
z->parent->parent->color = 1;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
rightRotate(z);
}
z->parent->color = 0;
z->parent->parent->color = 1;
leftRotate(z->parent->parent);
}
}
}
root->color = 0; // Ensure that the root is black
}
// Function to insert a value into the Red-Black Tree
void insert(int data) {
// Allocate memory for the new node
struct Node* z = (struct Node*)malloc(sizeof(struct Node));
z->data = data;
struct Node* y = NULL;
struct Node* x = root;
// Perform standard BST insertion
while (x != NIL) {
y = x;
if (z->data < x->data) {
x = x->left;
} else {
x = x->right;
}
}
z->parent = y;
if (y == NULL) {
root = z; // Tree was empty, so z becomes the root
} else if (z->data < y->data) {
y->left = z;
} else {
y->right = z;
}
z->left = NIL;
z->right = NIL;
z->color = 1; // Color the new node as red
// Fix any violations of the Red-Black Tree properties
insertFixUp(z);
}
// Function to perform an in-order traversal and print the tree
void inOrderTraversal(struct Node* x) {
if (x != NIL) {
inOrderTraversal(x->left);
printf("%d %s ", x->data, (x->color == 0) ? "Black" : "Red");
inOrderTraversal(x->right);
}
}
// Main function to test the Red-Black Tree insertion
int main() {
// Initialize NIL node
NIL = (struct Node*)malloc(sizeof(struct Node));
NIL->color = 0; // NIL is black
int values[] = {10, 20, 30, 15, 5};
int n = sizeof(values) / sizeof(values[0]);
for (int i = 0; i < n; i++) {
insert(values[i]);
}
printf("In-Order Traversal of the Red-Black Tree:\n");
inOrderTraversal(root);
return 0;
}
Output:
5 Black 10 Black 15 Red 20 Black 30 Black
An illustration of a C Red-Black Tree insertion procedure is demonstrated in the code provided. Initially, the program defines global pointers for the root node and the NIL (sentinel) node, as well as the structure of a node in a Red-Black Tree. The insertFixUp method ensures the maintenance of Red-Black Tree properties following an insertion, with the leftRotate and rightRotate functions serving to perform left and right rotations accordingly.
The recently inserted node is displayed in red following a standard BST insertion by the insert function. Subsequently, adjustments in color and rotation are executed using the insertFixUp function.
The Red-Black Tree undergoes testing and visualization through the inOrderTraversal function, which also displays node colors and performs an in-order traversal of the tree.
The NIL leaf is instantiated, a collection of elements is added to the Red-Black Tree, and the result of a traversal in in-order sequence is displayed, presenting the values along with their associated colors. This entire process takes place within the primary function.
Running the Red-Black Tree Insertion Algorithm
You have the flexibility to select any C compiler for compiling the C code and verifying the functionality of the Red-Black Tree insertion algorithm. For example, you can run the command below in your command line to compile the code when utilizing GCC:
gcc red_black_tree_insertion.c -o red_black_tree_insertion
An executable file named redblacktree_insertion will be generated. This program can subsequently be utilized in the following manner:
./red_black_tree_insertion
Once the values {10, 20, 30, 15, 5} are added to the Red-Black Tree data structure, the software will display the numeric values along with their respective colors by performing an in-order traversal.
Conclusion
Red-black trees serve as a powerful data structure for maintaining balance in binary search trees and find wide application in various scenarios such as self-balancing data structures and database indexing. This post extensively explores the characteristics of Red-Black Trees and provides a detailed guide on implementing the insertion algorithm in C language. Understanding and leveraging Red-Black Trees can greatly enhance the data handling capabilities of computer scientists and developers across a range of applications.