Implementing a Red-Black Tree in C: A Comprehensive Guide

A red-black tree is a self-balancing binary search tree that has a number of properties, ensuring that the operations (insert, delete, etc.) remain efficient. This article will guide you through the implementation of a red-black tree in the C programming language, covering key operations and maintaining the tree's properties.

Understanding Red-Black Trees

A red-black tree is a self-balancing binary search tree which has the following properties:

Each node is either red or black. The root is always black. No red node can have a red child. Every path from a node to its descendant NULL nodes has the same number of black nodes.

Red-Black Tree Implementation in C

Below is a concise implementation of a red-black tree in C, including key operations such as insertion, rotations, and maintaining the tree's properties.

Structure Definition

The first step is to define the structure of the tree nodes:

include stdio.hinclude  enum { RED, BLACK } Color;typedef struct Node {    int data;    Color color;    struct Node *left;    struct Node *right;    struct Node *parent;} Node;typedef struct RedBlackTree {    Node *root;    Node *TNULL;  // Sentinel node} RedBlackTree;

Function Prototypes

The essential functions for operating on the red-black tree are:

createTree() createNode(int data) leftRotate(RedBlackTree tree, Node *x) rightRotate(RedBlackTree tree, Node *y) insertFix(RedBlackTree tree, Node *k) insert(RedBlackTree tree, int data) printHelper(Node *root, int space) printTree(RedBlackTree tree)

Tree Initialization

The createTree() function initializes the tree with a sentinel node:

RedBlackTree *createTree() {    RedBlackTree *tree  (RedBlackTree*)malloc(sizeof(RedBlackTree));    tree-TNULL  createNode(0); // Sentinel node    tree-TNULL-color  BLACK;    tree-root  tree-TNULL;    return tree;}

The createNode(int data) function creates a new node with the specified data, and by default, it is colored red:

Node *createNode(int data) {    Node *newNode  (Node*)malloc(sizeof(Node));    newNode-data  data;    newNode-parent  newNode-left  newNode-right  NULL;    newNode-color  RED; // New node must be red    return newNode;}

Rotations

To maintain the tree's balance, rotations are performed around nodes:

void leftRotate(RedBlackTree *tree, Node *x) {    Node *y  x-right;    x-right  y-left;    if (y-left ! tree-TNULL) {        y-left-parent  x;    }    y-parent  x-parent;    if (x-parent  NULL) {        tree-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(RedBlackTree *tree, Node *y) {    Node *x  y-left;    y-left  x-right;    if (x-right ! tree-TNULL) {        x-right-parent  y;    }    x-parent  y-parent;    if (y-parent  NULL) {        tree-root  x;    } else if (y  y-parent-right) {        y-parent-right  x;    } else {        y-parent-left  x;    }    x-right  y;    y-parent  x;}

Insertion and Fixing the Tree

Insertion involves multiple steps to ensure the tree remains balanced:

void insertFix(RedBlackTree *tree, Node *k) {    Node *u;  // Uncle    while (k-parent-color  RED) {        if (k-parent  k-parent-parent-left) {            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(tree, k);                }                k-parent-color  BLACK;                k-parent-parent-color  RED;                rightRotate(tree, k-parent-parent);            }        } else {            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(tree, k);                }                k-parent-color  BLACK;                k-parent-parent-color  RED;                leftRotate(tree, k-parent-parent);            }        }    }    tree-root-color  BLACK;}void insert(RedBlackTree *tree, int data) {    Node *node  createNode(data);    node-parent  NULL;    node-left  tree-TNULL;    node-right  tree-TNULL;    Node *y  NULL;    Node *x  tree-root;    while (x ! tree-TNULL) {        y  x;        if (node-data  x-data) {            x  x-left;        } else {            x  x-right;        }    }    node-parent  y;    if (y  NULL) {        tree-root  node;    } else if (node-data  y-data) {        y-left  node;    } else {        y-right  node;    }    if (node-parent  NULL) {        node-parent-color  BLACK;        return;    }    if (node-parent-parent  NULL) {        return;    }    insertFix(tree, node);}

Tree Printing

The tree can be printed using a helper function:

void printHelper(Node *root, int space) {    if (root  NULL || root  tree-TNULL) {        return;    }    space  10;    printHelper(root-right, space);    printf    for (int i  10; i  space; i  ) {        printf    }    printf    printHelper(root-left, space);}void printTree(RedBlackTree *tree) {    printHelper(tree-root, 0);}

Main Function

The main function demonstrates inserting data into the tree and printing the tree structure:

int main() {    RedBlackTree *tree  createTree();    insert(tree, 55);    insert(tree, 40);    insert(tree, 65);    insert(tree, 30);    insert(tree, 50);    insert(tree, 60);    insert(tree, 70);    printTree(tree);    return 0;}

Summary

This implementation covers the basic structure and functionalities of a red-black tree including insertion and maintaining balance. It does not include deletion, but the principles of fixing the tree after deletion are similar to insertion. You can expand this implementation by adding deletion and additional utility functions as needed.