red-black-tree.c

// C program for Red-Black Tree insertion
#include<stdio.h>
#include<stdlib.h>
 
//A Red-Black tree node structure
struct node
{
    int data;     // for data part
    char color;  // for color property
 
    //links for left, right children and parent
    struct node *left, *right, *parent;
};
 
 
// Left Rotation
void LeftRotate(struct node **root,struct node *x)
{
    //y stored pointer of right child of x
    struct node *y = x->right;
 
    //store y's left subtree's pointer as x's right child
    x->right = y->left;
 
    //update parent pointer of x's right
    if (x->right != NULL)
        x->right->parent = x;
 
    //update y's parent pointer
    y->parent = x->parent;
 
    // if x's parent is null make y as root of tree
    if (x->parent == NULL)
        (*root) = y;
 
    // store y at the place of x
    else if (x == x->parent->left)
        x->parent->left = y;
    else    x->parent->right = y;
 
    // make x as left child of y
    y->left = x;
 
    //update parent pointer of x
    x->parent = y;
}
 
 
// Right Rotation (Similar to LeftRotate)
void rightRotate(struct node **root,struct node *y)
{
    struct node *x = y->left;
    y->left = x->right;
    if (x->right != NULL)
        x->right->parent = y;
    x->parent =y->parent;
    if (x->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;
}
 
// Utility function to fixup the Red-Black tree after standard BST insertion
void insertFixUp(struct node **root,struct node *z)
{
    // iterate until z is not the root and z's parent color is red
    while (z != *root && z->parent->color == 'R')
    {
        struct node *y;
 
        // Find uncle and store uncle in y
        if (z->parent == z->parent->parent->left)
            y = z->parent->parent->right;
        else
            y = z->parent->parent->left;
 
        // If uncle is RED, do following
        // (i)  Change color of parent and uncle as BLACK
        // (ii) Change color of grandparent as RED
        // (iii) Move z to grandparent
        if (y->color == 'R')
        {
            y->color = 'B';
            z->parent->color = 'B';
            z->parent->parent->color = 'R';
            z = z->parent->parent;
        }
 
        // Uncle is BLACK, there are four cases (LL, LR, RL and RR)
        else
        {
            // Left-Left (LL) case, do following
            // (i)  Swap color of parent and grandparent
            // (ii) Right Rotate Grandparent
            if (z->parent == z->parent->parent->left &&
                z == z->parent->left)
            {
                char ch = z->parent->color ;
                z->parent->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                rightRotate(root,z->parent->parent);
            }
 
            // Left-Right (LR) case, do following
            // (i)  Swap color of current node  and grandparent
            // (ii) Left Rotate Parent
            // (iii) Right Rotate Grand Parent
            if (z->parent == z->parent->parent->left &&
                z == z->parent->right)
            {
                char ch = z->color ;
                z->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                LeftRotate(root,z->parent);
                rightRotate(root,z->parent->parent);
            }
 
            // Right-Right (RR) case, do following
            // (i)  Swap color of parent and grandparent
            // (ii) Left Rotate Grandparent
            if (z->parent == z->parent->parent->right &&
                z == z->parent->right)
            {
                char ch = z->parent->color ;
                z->parent->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                LeftRotate(root,z->parent->parent);
            }
 
            // Right-Left (RL) case, do following
            // (i)  Swap color of current node  and grandparent
            // (ii) Right Rotate Parent
            // (iii) Left Rotate Grand Parent
            if (z->parent == z->parent->parent->right &&
                z == z->parent->left)
            {
                char ch = z->color ;
                z->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                rightRotate(root,z->parent);
                LeftRotate(root,z->parent->parent);
            }
        }
    }
    (*root)->color = 'B'; //keep root always black
}
 
// Utility function to insert newly node in RedBlack tree
void insert(struct node **root, int data)
{
    // Allocate memory for new node
    struct node *z = (struct node*)malloc(sizeof(struct node));
    z->data = data;
    z->left = z->right = z->parent = NULL;
 
     //if root is null make z as root
    if (*root == NULL)
    {
        z->color = 'B';
        (*root) = z;
    }
    else
    {
        struct node *y = NULL;
        struct node *x = (*root);
 
        // Follow standard BST insert steps to first insert the node
        while (x != NULL)
        {
            y = x;
            if (z->data < x->data)
                x = x->left;
            else
                x = x->right;
        }
        z->parent = y;
        if (z->data > y->data)
            y->right = z;
        else
            y->left = z;
        z->color = 'R';
 
        // call insertFixUp to fix reb-black tree's property if it
        // is voilated due to insertion.
        insertFixUp(root,z);
    }
}
 
// A utility function to traverse Red-Black tree in inorder fashion
void inorder(struct node *root)
{
    if (root == NULL)
        return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}
 
/* Drier program to test above function*/
int main()
{
    struct node *root = NULL;
    insert(&root,10);
    insert(&root,20);
    insert(&root,40);
    insert(&root,30);
    insert(&root,50);
    insert(&root,35);
    insert(&root,25);
    insert(&root,37);
    printf("inorder Traversal Is : ");
    inorder(root);
 
    return 0;
}

Thank you :)

Thank you so much, it's help me a lot to understand!

// THIS IS JUST IMPLIMENTATION OF MAP DATA_STRUCTURE USING RED_BLACK_TREE IN C LANGUAGE

// please to get the concept watch videos recommended ( Jenney's Lectures youtube channel )
// link to the videos https://youtu.be/3RQtq7PDHog?si=9h-NhxC3turaT36h
// IF YOU THINK THE CODE CAN BE OPTMIZED PLEASE FELL FREE TO DO IT

/*
** red_black_tree is a self balancing tree
** it is not perfectly balanced like AVL tree
**

A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color (red or black). These colors are used to ensure that the tree remains balanced during insertions and deletions. Although the balance of the tree is not perfect, it is good enough to reduce the searching time and maintain it around O(log n) time, where n is the total number of elements in the tree. This tree was invented in 1972 by Rudolf Bayer. It must be noted that as each node requires only 1 bit of space to store the color information, these types of trees show identical memory footprints to the classic (uncolored) binary search tree.

5 rules in RBT

1. Every node has a color either red or black

2. The root of the tree is always black

3. There are no two adjacent red nodes (Ared node cannot have a red parent or red child)

4. Every path from a node (including root) to any of its descendants NULL nodes has the same number of black nodes.

5. All leaf nodes are black nodes

Algorithm Time Complexity
Search O(log n)
Insert O(log n)
Delete O(log n)

*/

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

// typedefs
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned int u32;
typedef unsigned long long u64;

typedef signed char i8;
typedef signed short i16;
typedef signed int i32;
typedef signed long long i64;

typedef float f32;
typedef double f64;

typedef bool b8;

// to track allocated memory
static u64 total_allocated_memory;

void* memory_allocate(u64 size) {
void* block = malloc(size);
total_allocated_memory += size;
return block;
}

void memory_free(void* block, u64 size) {
total_allocated_memory -= size;
free(block);
}

// function used to compare nodes and build BST
typedef b8 (PFN_map_cmp)(const void root_key, const void* node_key);

// map_node structure
typedef struct map_node {
void* key; // the provided key is copied in this memory location , (key is a pointer which stores the address of memory location)
void data; // the provided data is copied in this memory location , (data is a pointer which stores the address of memory location)
struct map_node left; // left stores starting byte addr of left map_node
struct map_node* right; // right stores starting byte addr of right map_node
struct map_node* parent; // parent stores starting byte addr of parent map_node
char is_red; // if red then 1 else 0
} map_node;

// map structure
typedef struct map {
map_node* root; // the root of the red black tree
u64 size; // no of nodes
u64 key_stride; // size of key in bytes
u64 data_stride; // size of data in bytes
PFN_map_cmp cmp_func; // function used to compare the nodes
} map;

// to create a map_node
map_node* create_map_node(const void* key, const void* data, u64 key_stride, u64 data_stride);

// to destroy a map_node (before destroying set left_ptr and right_ptr to zero)
void destroy_map_node(map_node* node, u64 key_stride, u64 data_stride);

// the parameter node will become left child of node's right child ,
void left_rotate_map_node(map* mp, map_node* node);

// the parameter node will become right child of node's left child ,
void right_rotate_map_node(map* mp, map_node* node);

// this function is used to recolor the tree after
void insert_fix_up_map_node(map* mp, map_node* node);

void remove_fix_up_map_node(map* mp, map_node* node);

// use this macro to create map
#define map_create(key_type, data_type, PFN_map_cmp) _map_create(sizeof(key_type), sizeof(data_type), PFN_map_cmp)

map* _map_create(u64 key_stride, u64 data_stride, PFN_map_cmp cmp_func) {

map* temp = memory_allocate(sizeof(map));
temp->root = 0;
temp->size = 0;
temp->key_stride = key_stride;
temp->data_stride = data_stride;
temp->cmp_func = cmp_func;

return temp;

}

void map_destroy(map* mp) {
if (mp->root) {

    destroy_map_node(mp->root, mp->key_stride, mp->data_stride);
}
memory_free(mp, sizeof(map));

}

void map_insert(map* mp, const void* key, const void* data) {
map_node* node = create_map_node(key, data, mp->key_stride, mp->data_stride);

if (mp->root == 0) {
    mp->root = node;
    mp->root->is_red = 0;
} else {
    map_node* temp = mp->root;

    while (temp) {

        if (memcmp(temp->key, key, mp->key_stride) == 0) {
            memcpy(temp->data, data, mp->data_stride);
            destroy_map_node(node, mp->key_stride, mp->data_stride);
            return;
        }

        if (mp->cmp_func(temp->key, key)) {
            if (temp->left == 0) {
                temp->left = node;
                break;
            }
            temp = temp->left;
        } else {
            if (temp->right == 0) {
                temp->right = node;
                break;
            }
            temp = temp->right;
        }
    }
    node->parent = temp;

    insert_fix_up_map_node(mp, node);
}
mp->size += 1;

}

void map_remove(map* mp, const void* key) {

if (mp->root == 0) {
    printf("map_remove : map has zero nodes \n");
    return;
}

map_node* node = mp->root;

void* k = memory_allocate(mp->key_stride);
memcpy(k, key, mp->key_stride);

while (node) {

    if (memcmp(node->key, k, mp->key_stride) == 0) {

        if (node->left == 0 && node->right == 0) {

            if (node->is_red == 0) {
                remove_fix_up_map_node(mp, node);
            }

            if (node->parent) {

                if (node->parent->left == node) {
                    node->parent->left = 0;
                } else {
                    node->parent->right = 0;
                }
            } else {
                mp->root = 0;
            }

            destroy_map_node(node, mp->key_stride, mp->data_stride);

            mp->size -= 1;

            memory_free(k, mp->key_stride);

            return;

        } else if (node->right == 0) {

            map_node* prev = node->left;
            while (prev->right) {
                prev = prev->right;
            }

            memcpy(node->key, prev->key, mp->key_stride);
            memcpy(node->data, prev->data, mp->data_stride);

            memcpy(k, prev->key, mp->key_stride);

            node = node->left;

        } else {

            map_node* next = node->right;
            while (next->left) {
                next = next->left;
            }

            memcpy(node->key, next->key, mp->key_stride);
            memcpy(node->data, next->data, mp->data_stride);

            memcpy(k, next->key, mp->key_stride);
            node = node->right;
        }

    } else {

        if (mp->cmp_func(node->key, k)) {
            node = node->left;
        } else {
            node = node->right;
        }
    }
}

printf("map_remove : invalid key\n");

memory_free(k, mp->key_stride);

return;

}

u64 map_size(map* mp) {
return mp->size;
}

void* map_data(map* mp, const void* key) {

if (mp->root == 0) {
    printf("map_remove : map has zero nodes \n");
    return 0;
}

map_node* temp = mp->root;

while (temp) {

    if (memcmp(temp->key, key, mp->key_stride) == 0) {
        return temp->data;
    }

    if (mp->cmp_func(temp->key, key)) {

        temp = temp->left;
    } else {

        temp = temp->right;
    }
}

printf("map_data : invalid key\n");

return 0;

}

map_node* map_begin(map* mp) {
map_node* temp = mp->root;
while (temp->left) {
temp = temp->left;
}
return temp;
}

map_node* map_next(map* mp, map_node* node) {
if (node->right) {
map_node* temp = node->right;
while (temp->left) {
temp = temp->left;
}
return temp;
}

map_node* temp = mp->root;
map_node* next;

while (temp) {

    if (memcmp(temp->key, node->key, mp->key_stride) == 0) {
        break;
    }

    if (mp->cmp_func(temp->key, node->key)) {
        next = temp;
        temp = temp->left;
    } else {
        temp = temp->right;
    }
}
return next;

}

map_node* map_end(map* mp) {
map_node* temp = mp->root;
while (temp->right) {
temp = temp->right;
}
return temp;
}

////////////////////////////////////////////////////////////////////////////////////////////////////

map_node* create_map_node(const void* key, const void* data, u64 key_stride, u64 data_stride) {
map_node* temp = memory_allocate(sizeof(map_node));

temp->key = memory_allocate(key_stride);
memcpy(temp->key, key, key_stride);

temp->data = memory_allocate(data_stride);
memcpy(temp->data, data, data_stride);

temp->left = 0;
temp->right = 0;
temp->parent = 0;
temp->is_red = 1;

return temp;

}

void destroy_map_node(map_node* node, u64 key_stride, u64 data_stride) {
if (node == 0) {
return;
}

destroy_map_node(node->left, key_stride, data_stride);
destroy_map_node(node->right, key_stride, data_stride);

memory_free(node->key, key_stride);
memory_free(node->data, data_stride);
memory_free(node, sizeof(map_node));

}

// parameter node will become left child of node's right child ,
void left_rotate_map_node(map* mp, map_node* node) {

if (!node || !node->right)
    return; // Safety check

map_node* parent = node->parent;
map_node* child = node->right;

if (parent) {
    if (parent->left == node) {
        parent->left = child;
    } else {
        parent->right = child;
    }
}
child->parent = parent;

node->right = child->left;
if (node->right) {
    node->right->parent = node;
}

child->left = node;
node->parent = child;

if (child->parent == 0) {
    mp->root = child;
}

}

// parameter node will become right child of node's left child ,
void right_rotate_map_node(map* mp, map_node* node) {

if (!node || !node->left)
    return; // Safety check

map_node* parent = node->parent;
map_node* child = node->left;

if (parent) {
    if (parent->left == node) {
        parent->left = child;
    } else {
        parent->right = child;
    }
}
child->parent = parent;

node->left = child->right;
if (node->left) {
    node->left->parent = node;
}

child->right = node;
node->parent = child;

if (child->parent == 0) {
    mp->root = child;
}

}

void insert_fix_up_map_node(map* mp, map_node* node) {

while (node->parent && node->parent->is_red) {

    if (node->parent->parent) {

        map_node* uncle;
        if (node->parent->parent->left == node->parent) {
            uncle = node->parent->parent->right;

        } else {
            uncle = node->parent->parent->left;
        }

        if (uncle && uncle->is_red) {
            uncle->is_red = 0;
            node->parent->is_red = 0;
            node->parent->parent->is_red = 1;

            node = node->parent->parent;
        } else {

            if (node->parent->parent->left == node->parent) {

                if (node->parent->right == node) {
                    node = node->parent;
                    left_rotate_map_node(mp, node);
                }
                right_rotate_map_node(mp, node->parent->parent);
                node->parent->is_red = 0;
                node->parent->right->is_red = 1;

            } else {
                if (node->parent->left == node) {
                    node = node->parent;
                    right_rotate_map_node(mp, node);
                }
                left_rotate_map_node(mp, node->parent->parent);
                node->parent->is_red = 0;
                node->parent->left->is_red = 1;
            }
            break;
        }
    } else {
        node->parent->is_red = 0;
    }
}

// if node is root make sure it is colored black
if (node->parent == 0) {
    node->is_red = 0;
}

}

void remove_fix_up_map_node(map* mp, map_node* node) {

if (node->parent == 0) {
    return;
}

map_node* sibling;

if (node->parent->left == node) {
    sibling = node->parent->right;
} else {
    sibling = node->parent->left;
}

while (1) {

    if (sibling && sibling->is_red) {

        sibling->is_red = 0;
        sibling->parent->is_red = 1;

        if (node->parent->left == sibling) {
            right_rotate_map_node(mp, node->parent);
            sibling = node->parent->left;
        } else {
            left_rotate_map_node(mp, node->parent);
            sibling = node->parent->right;
        }
        continue;
    }

    if (sibling == 0 || (sibling->left == 0 || sibling->left->is_red == 0) && (sibling->right == 0 || sibling->right->is_red == 0)) {

        if (node->parent->is_red) {
            node->parent->is_red = 0;

            if (sibling) {
                sibling->is_red = 1;
            }

            break;
        } else {

            if (sibling) {
                sibling->is_red = 1;
            }

            node = node->parent;

            if (node->parent == 0) {
                node->is_red = 0;
                break;
            }

            if (node->parent->left == node) {
                sibling = node->parent->right;
            } else {
                sibling = node->parent->left;
            }
        }
    } else {
        map_node *far, *near;

        if (node->parent->left == node) {
            far = sibling->right;
            near = sibling->left;
        } else {
            far = sibling->left;
            near = sibling->right;
        }

        if (near && near->is_red && (far == 0 || far->is_red == 0)) {
            sibling->is_red = 1;
            near->is_red = 0;

            if (near == sibling->left) {
                right_rotate_map_node(mp, sibling);
            } else {
                left_rotate_map_node(mp, sibling);
            }

            if (node->parent->left == node) {
                sibling = node->parent->right;
            } else {
                sibling = node->parent->left;
            }
        }

        if (node == node->parent->right) {
            right_rotate_map_node(mp, sibling->parent);
            if (node->parent->is_red == 0) {
                sibling->left->is_red = 0;
            }

        } else {
            left_rotate_map_node(mp, sibling->parent);
            if (node->parent->is_red == 0) {
                sibling->right->is_red = 0;
            }
        }

        break;
    }
}

}

/*
//
//
//
//
*/

// TESTING THE DATA_STRUCTURE

// printing of tree
void printRBT(map_node* node, int level, int node_type) {

int x = level;
while (x--) {
    if (x == 0) {
        printf("|--");
        break;
    }

    printf("|  ");
}

char const* str = ((node_type == 0) ? "ROOT" : (node_type == 1) ? "L"
                                                                : "R");

if (node == 0) {
    printf("%s_NULL\n", str);
    return;
}

int k = *(int*)node->key;
const char* color = (node->is_red == 0) ? "BLACK" : "RED";

printf("%s_%d_%s\n", str, k, color);

printRBT(node->right, level + 1, 2);
printRBT(node->left, level + 1, 1);

}

// inorder of tree
void print_inorder(map_node* node) {
if (node == 0) {
return;
}

print_inorder(node->left);
printf("%d,", *(int*)node->key);
print_inorder(node->right);

}

// this function will print no of black nodes in path from root to all leaf nodes
// all paths must have equal black nodes which ensures the tree is balanced
void print_no_black_nodes(map_node* node, int count) {
if (node == 0) {
return;
}

if (node->left == NULL && node->right == NULL) {
    int x = (node->is_red == 1 ? 0 : 1);
    printf("%d,", count + x);
    return;
}

count += (node->is_red == 1 ? 0 : 1);

print_no_black_nodes(node->left, count);
print_no_black_nodes(node->right, count);

count -= (node->is_red == 1 ? 0 : 1);

}

b8 cmp_func(const void* root_key, const void* node_key) {
return (int)root_key > (int)node_key;
}

int main() {

printf("sizeof(map_node) = %llu\n", sizeof(map_node));
printf("sizeof(map) = %llu\n\n", sizeof(map));

srand(42);
const int n = 100;
int arr[n];

map* mp = map_create(int, float, cmp_func);

// inserting random numbers
for (int i = 0; i < n; i++) {

    int k = rand() % 1000;
    arr[i] = k;
    float d = k + 0.5f;

    printf("inserted %d\n", k);
    map_insert(mp, &k, &d);

    printRBT(mp->root, 0, 0);

    printf("black nodes in each root to leaf path = ");
    print_no_black_nodes(mp->root, 0);
    printf("\n");

    printf("in_order = ");
    print_inorder(mp->root);
    printf("\n\n");
}

// removing inserted numbers
for (int i = 0; i < n; i++) {

    printf("removed %d\n", arr[i]);
    map_remove(mp, &arr[i]);

    printRBT(mp->root, 0, 0);

    printf("black nodes in each root to leaf path = ");
    print_no_black_nodes(mp->root, 0);
    printf("\n");

    printf("in_order = ");
    print_inorder(mp->root);
    printf("\n\n");
}

// for (int i = n - 1; i >= 0; i--) {

//     float data = *(float*)map_data(mp, &arr[i]);
//     printf("key %d , data %f\n", arr[i], data);
// }

// map_node* begin = map_begin(mp);
// map_node* end = map_end(mp);

// int x = 30;

// while (begin != end) {
//     printf("key %d , data %f\n", *(int*)begin->key, *(float*)begin->data);

//     begin = map_next(mp, begin);
// }
// printf("key %d , data %f\n", *(int*)begin->key, *(float*)begin->data);
map_destroy(mp);

printf("memory leak = %llu\n", total_allocated_memory);

}