Red-Black Tree Implementation in C

A Red-Black Tree is a self-balancing binary search tree where each node has an extra bit for denoting the color of the node, either red or black. This ensures that the tree remains balanced during insertions and deletions, resulting in efficient search, insert, and delete operations.

Program Structure

This implementation of a Red-Black Tree in C will include the following components:

1. Struct definitions for the Red-Black Tree node and the tree itself.
2. Functions for rotating the tree left and right.
3. Functions to handle insertion, including the re-balancing of the tree.
4. A main function to demonstrate the usage of the Red-Black Tree with insertion operations.

Code Implementation

#include <stdio.h>
#include <stdlib.h>

typedef enum { RED, BLACK } NodeColor;

typedef struct RBTreeNode {
    int data;
    NodeColor color;
    struct RBTreeNode *left, *right, *parent;
} RBTreeNode;

typedef struct RBTree {
    RBTreeNode *root;
    RBTreeNode *nil; // Sentinel node for null leaves
} RBTree;

// Function prototypes
RBTreeNode* createNode(RBTree *tree, int data);
RBTree* createRBTree();
void leftRotate(RBTree *tree, RBTreeNode *x);
void rightRotate(RBTree *tree, RBTreeNode *y);
void insertFixup(RBTree *tree, RBTreeNode *z);
void insert(RBTree *tree, int data);
void inorderTraversal(RBTreeNode *node, RBTreeNode *nil);
void printTree(RBTree *tree);

// Function to create a new node
RBTreeNode* createNode(RBTree *tree, int data) {
    RBTreeNode *newNode = (RBTreeNode*)malloc(sizeof(RBTreeNode));
    newNode->data = data;
    newNode->color = RED; // New nodes are always red initially
    newNode->left = tree->nil;
    newNode->right = tree->nil;
    newNode->parent = tree->nil;
    return newNode;
}

// Function to create a new Red-Black Tree
RBTree* createRBTree() {
    RBTree *tree = (RBTree*)malloc(sizeof(RBTree));
    tree->nil = (RBTreeNode*)malloc(sizeof(RBTreeNode));
    tree->nil->color = BLACK;
    tree->root = tree->nil;
    return tree;
}

// Left rotate function
void leftRotate(RBTree *tree, RBTreeNode *x) {
    RBTreeNode *y = x->right;
    x->right = y->left;
    if (y->left != tree->nil) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == tree->nil) {
        tree->root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

// Right rotate function
void rightRotate(RBTree *tree, RBTreeNode *y) {
    RBTreeNode *x = y->left;
    y->left = x->right;
    if (x->right != tree->nil) {
        x->right->parent = y;
    }
    x->parent = y->parent;
    if (y->parent == tree->nil) {
        tree->root = x;
    } else if (y == y->parent->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }
    x->right = y;
    y->parent = x;
}

// Fixup function to maintain Red-Black properties after insertion
void insertFixup(RBTree *tree, RBTreeNode *z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBTreeNode *y = z->parent->parent->right; // Uncle of z
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(tree, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(tree, z->parent->parent);
            }
        } else {
            RBTreeNode *y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(tree, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(tree, z->parent->parent);
            }
        }
    }
    tree->root->color = BLACK;
}

// Function to insert a new node into the Red-Black Tree
void insert(RBTree *tree, int data) {
    RBTreeNode *z = createNode(tree, data);
    RBTreeNode *y = tree->nil;
    RBTreeNode *x = tree->root;

    while (x != tree->nil) {
        y = x;
        if (z->data < x->data) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    z->parent = y;
    if (y == tree->nil) {
        tree->root = z;
    } else if (z->data < y->data) {
        y->left = z;
    } else {
        y->right = z;
    }

    insertFixup(tree, z);
}

// Function for in-order traversal of the Red-Black Tree
void inorderTraversal(RBTreeNode *node, RBTreeNode *nil) {
    if (node != nil) {
        inorderTraversal(node->left, nil);
        printf("%d (%s)\n", node->data, node->color == RED ? "Red" : "Black");
        inorderTraversal(node->right, nil);
    }
}

// Function to print the Red-Black Tree
void printTree(RBTree *tree) {
    inorderTraversal(tree->root, tree->nil);
}

// Main function to demonstrate the usage of the Red-Black Tree
int main() {
    RBTree *tree = createRBTree();

    // Insert keys into the Red-Black Tree
    insert(tree, 10);
    insert(tree, 20);
    insert(tree, 30);
    insert(tree, 15);
    insert(tree, 25);
    insert(tree, 5);
    insert(tree, 1);

    // Print the Red-Black Tree
    printf("In-order Traversal of Red-Black Tree:\n");
    printTree(tree);

    return 0;
}

Explanation

The program implements a Red-Black Tree in C, a type of self-balancing binary search tree. The Red-Black Tree maintains its balance through a set of properties:

• Each node is either red or black.
• The root is always black.
• All leaves (NIL nodes) are black.
• If a node is red, then both its children must be black.
• Every path from a node to its descendant NIL nodes must have the same number of black nodes.

The key components of this implementation are as follows:

The RBTreeNode struct represents a node in the Red-Black Tree, with fields for storing the node’s data, color, and pointers to its left child, right child, and parent.

The RBTree struct represents the Red-Black Tree itself, with a pointer to the root node and a sentinel node nil used to represent null leaves.

The createNode() function creates a new Red-Black Tree node, initializing it as a red node with its children set to the sentinel nil node.

The createRBTree() function initializes an empty Red-Black Tree by creating a sentinel nil node and setting the root to this nil node.

The leftRotate() and rightRotate() functions are used to maintain the balance of the tree. These functions perform the necessary rotations when inserting nodes.

The insertFixup() function is responsible for maintaining the Red-Black Tree properties after inserting a new node. It corrects any violations by adjusting node colors and performing rotations as needed.

The insert() function inserts a new node into the Red-Black Tree, placing it in the appropriate position and then calling insertFixup() to ensure the tree remains balanced.

The inorderTraversal() and printTree() functions are used for in-order traversal of the tree, printing out the keys along with their colors.

In the main() function, we demonstrate the Red-Black Tree’s functionality by inserting several keys and printing the tree using an in-order traversal.