A RED-BLACK TREE Implementation

red-black-tree.c

/*
 * [PROG]		: Red Black Tree
 * [AUTHOR]		: Ashfaqur Rahman <[email protected]>
 * [PURPOSE]		: Red-Black tree is an algorithm for creating a balanced
 * 			  binary search tree data structure. Implementing a red-balck tree
 * 			  data structure is the purpose of this program.
 * 
 * [DESCRIPTION]	: Its almost like the normal binary search tree data structure. But
 * 			  for keeping the tree balanced an extra color field is introduced to each node.
 *			  This tree will mantain bellow properties.
 *				  1. Nodes can be either RED or BLACK.
 *				  2. ROOT is BLACK.
 *				  3. Leaves of this tree are null nodes. Here null is represented bya special node NILL.
 *				     Each NILL nodes are BLACK. So each leave is BLACK.
 * 				  4. Each RED node's parent is BLACK
 *				  5. Each simple path taken from a node to descendent leaf has same number of black height. 
 *				     That means each path contains same number of BLACK nodes.
 */

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

#define RED 0
#define BLACK 1

struct node{
	int key;
	int color;
	struct node *parent;
	struct node *left;
	struct node *right;
};

/* Global, since all function will access them */
struct node *ROOT;
struct node *NILL;

void left_rotate(struct node *x);
void right_rotate(struct node *x);
void tree_print(struct node *x);
void red_black_insert(int key);
void red_black_insert_fixup(struct node *z);
struct node *tree_search(int key);
struct node *tree_minimum(struct node *x);
void red_black_transplant(struct node *u, struct node *v);
void red_black_delete(struct node *z);
void red_black_delete_fixup(struct node *x);

int main(){
	NILL = malloc(sizeof(struct node));
	NILL->color = BLACK;

	ROOT = NILL;

	printf("### RED-BLACK TREE INSERT ###\n\n");
	
	int tcase, key;
	printf("Number of key: ");
	scanf("%d", &tcase);
	while(tcase--){
		printf("Enter key: ");
		scanf("%d", &key);
		red_black_insert(key);
	}

	printf("### TREE PRINT ###\n\n");
	tree_print(ROOT);
	printf("\n");

	printf("### KEY SEARCH ###\n\n");
	printf("Enter key: ");
	scanf("%d", &key);
	printf((tree_search(key) == NILL) ? "NILL\n" : "%p\n", tree_search(key));

	printf("### MIN TEST ###\n\n");
	printf("MIN: %d\n", (tree_minimum(ROOT))->key);

	printf("### TREE DELETE TEST ###\n\n");
	printf("Enter key to delete: ");
	scanf("%d", &key);
	red_black_delete(tree_search(key));
	
	printf("### TREE PRINT ###\n\n");
	tree_print(ROOT);
	printf("\n");

	return 0;
}

/* Print tree keys by inorder tree walk */

void tree_print(struct node *x){
	if(x != NILL){
		tree_print(x->left);
		printf("%d\t", x->key);
		tree_print(x->right);
	}
}

struct node *tree_search(int key){
	struct node *x;

	x = ROOT;
	while(x != NILL && x->key != key){
		if(key < x->key){
			x = x->left;
		}
		else{
			x = x->right;
		}
	}

	return x;
}

struct node *tree_minimum(struct node *x){
	while(x->left != NILL){
		x = x->left;
	}
	return x;
}

/*
 * Insertion is done by the same procedure for BST Insert. Except new node is colored
 * RED. As it is coloured RED it may violate property 2 or 4. For this reason an
 * auxilary procedure called red_black_insert_fixup is called to fix these violation.
 */

void red_black_insert(int key){
	struct node *z, *x, *y;
	z = malloc(sizeof(struct node));

	z->key = key;
	z->color = RED;
	z->left = NILL;
	z->right = NILL;

	x = ROOT;
	y = NILL;

	/* 
	 * Go through the tree untill a leaf(NILL) is reached. y is used for keeping
	 * track of the last non-NILL node which will be z's parent.
	 */
	while(x != NILL){
		y = x;
		if(z->key <= x->key){
			x = x->left;
		}
		else{
			x = x->right;
		}
	}

	if(y == NILL){
		ROOT = z;
	}
	else if(z->key <= y->key){
		y->left = z;
	}
	else{
		y->right = z;
	}

	z->parent = y;

	red_black_insert_fixup(z);
}

/*
 * Here is the psudocode for fixing violations.
 * 
 * while (z's parent is RED)
 *		if(z's parent is z's grand parent's left child) then
 *			if(z's right uncle or grand parent's right child is RED) then
 *				make z's parent and uncle BLACK
 *				make z's grand parent RED
 *				make z's grand parent new z as it may violate property 2 & 4
 *				(so while loop will contineue)
 *			
 *			else(z's right uncle is not RED)
 *				if(z is z's parents right child) then
 *					make z's parent z
 *					left rotate z
 *				make z's parent's color BLACK
 *				make z's grand parent's color RED
 *				right rotate z's grand parent
 *				( while loop won't pass next iteration as no violation)
 *
 *		else(z's parent is z's grand parent's right child)
 *			do exact same thing above just swap left with right and vice-varsa
 *
 * At this point only property 2 can be violated so make root BLACK
 */

void red_black_insert_fixup(struct node *z){
	while(z->parent->color == RED){

		/* z's parent is left child of z's grand parent*/
		if(z->parent == z->parent->parent->left){

			/* z's grand parent's right child is RED */
			if(z->parent->parent->right->color == RED){
				z->parent->color = BLACK;
				z->parent->parent->right->color = BLACK;
				z->parent->parent->color = RED;
				z = z->parent->parent;
			}

			/* z's grand parent's right child is not RED */
			else{
				
				/* z is z's parent's right child */
				if(z == z->parent->right){
					z = z->parent;
					left_rotate(z);
				}

				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				right_rotate(z->parent->parent);
			}
		}

		/* z's parent is z's grand parent's right child */
		else{
			
			/* z's left uncle or z's grand parent's left child is also RED */
			if(z->parent->parent->left->color == RED){
				z->parent->color = BLACK;
				z->parent->parent->left->color = BLACK;
				z->parent->parent->color = RED;
				z = z->parent->parent;
			}

			/* z's left uncle is not RED */
			else{
				/* z is z's parents left child */
				if(z == z->parent->left){
					z = z->parent;
					right_rotate(z);
				}

				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				left_rotate(z->parent->parent);
			}
		}
	}

	ROOT->color = BLACK;
}

/*
 * Lets say y is x's right child. Left rotate x by making y, x's parent and x, y's
 * left child. y's left child becomes x's right child.
 * 
 * 		x									y
 *	   / \                                 / \
 *  STA   y			----------->		  x   STC
 *		 / \							 / \
 *	  STB   STC						  STA   STB
 */

void left_rotate(struct node *x){
	struct node *y;
	
	/* Make y's left child x's right child */
	y = x->right;
	x->right = y->left;
	if(y->left != NILL){
		y->left->parent = x;
	}

	/* Make x's parent y's parent and y, x's parent's child */
	y->parent = x->parent;
	if(y->parent == NILL){
		ROOT = y;
	}
	else if(x == x->parent->left){
		x->parent->left = y;
	}
	else{
		x->parent->right = y;
	}
	
	/* Make x, y's left child & y, x's parent */
	y->left = x;
	x->parent = y;
}

/*
 * Lets say y is x's left child. Right rotate x by making x, y's right child and y
 * x's parent. y's right child becomes x's left child.
 *
 *			|											|
 *			x											y
 *		   / \										   / \
 *		  y   STA		---------------->			STB	  x
 *		 / \											 / \
 *	  STB   STC										  STC   STA
 */

void right_rotate(struct node *x){
	struct node *y;

	/* Make y's right child x's left child */
	y = x->left;
	x->left = y->right;
	if(y->right != NILL){
		y->right->parent = x;
	}

	/* Make x's parent y's parent and y, x's parent's child */
	y->parent = x->parent;
	if(y->parent == NILL){
		ROOT = y;
	}
	else if(x == x->parent->left){
		x->parent->left = y;	
	}
	else{
		x->parent->right = y;
	}

	/* Make y, x's parent and x, y's child */
	y->right = x;
	x->parent = y;
}

/*
 * Deletion is done by the same mechanism as BST deletion. If z has no child, z is
 * removed. If z has single child, z is replaced by its child. Else z is replaced by
 * its successor. If successor is not z's own child, successor is replaced by its
 * own child first. then z is replaced by the successor.
 *
 * A pointer y is used to keep track. In first two case y is z. 3rd case y is z's
 * successor. So in first two case y is removed. In 3rd case y is moved.
 *
 *Another pointer x is used to keep track of the node which replace y.
 * 
 * As removing or moving y can harm red-black tree properties a variable
 * yOriginalColor is used to keep track of the original colour. If its BLACK then
 * removing or moving y harm red-black tree properties. In that case an auxilary
 * procedure red_black_delete_fixup(x) is called to recover this.
 */

void red_black_delete(struct node *z){
	struct node *y, *x;
	int yOriginalColor;

	y = z;
	yOriginalColor = y->color;

	if(z->left == NILL){
		x = z->right;
		red_black_transplant(z, z->right);
	}
	else if(z->right == NILL){
		x = z->left;
		red_black_transplant(z, z->left);
	}
	else{
		y = tree_minimum(z->right);
		yOriginalColor = y->color;

		x = y->right;

		if(y->parent == z){
			x->parent = y;
		}
		else{
			red_black_transplant(y, y->right);
			y->right = z->right;
			y->right->parent = y;
		}

		red_black_transplant(z, y);
		y->left = z->left;
		y->left->parent = y;
		y->color = z->color;
	}

	if(yOriginalColor == BLACK){
		red_black_delete_fixup(x);
	}
}

/*
 * As y was black and removed x gains y's extra blackness.
 * Move the extra blackness of x until
 *		1. x becomes root. In that case just remove extra blackness
 *		2. x becomes a RED and BLACK node. in that case just make x BLACK
 *
 * First check if x is x's parents left or right child. Say x is left child
 *
 * There are 4 cases.
 *
 * Case 1: x's sibling w is red. transform case 1 into case 2 by recoloring
 * w and x's parent. Then left rotate x's parent.
 *
 * Case 2: x's sibling w is black, w's both children is black. Move x and w's
 * blackness to x's parent by coloring w to RED and x's parent to BLACK.
 * Make x's parent new x.Notice if case 2 come through case 1 x's parent becomes 
 * RED and BLACK as it became RED in case 1. So loop will stop in next iteration.
 *
 * Case 3: w is black, w's left child is red and right child is black. Transform
 * case 3 into case 4 by recoloring w and w's left child, then right rotate w.
 *
 * Case 4: w is black, w's right child is red. recolor w with x's parent's color.
 * make x's parent BLACK, w's right child black. Now left rotate x's parent. Make x
 * point to root. So loop will be stopped in next iteration.
 *
 * If x is right child of it's parent do exact same thing swapping left<->right
 */

void red_black_delete_fixup(struct node *x){
	struct node *w;	

	while(x != ROOT && x->color == BLACK){
		
		if(x == x->parent->left){
			w = x->parent->right;

			if(w->color == RED){
				w->color = BLACK;
				x->parent->color = RED;
				left_rotate(x->parent);
				w = x->parent->right;
			}

			if(w->left->color == BLACK && w->right->color == BLACK){
				w->color = RED;
				x->parent->color = BLACK;
				x = x->parent;
			}
			else{

				if(w->right->color == BLACK){
					w->color = RED;
					w->left->color = BLACK;
					right_rotate(w);
					w = x->parent->right;
				}

				w->color = x->parent->color;
				x->parent->color = BLACK;
				x->right->color = BLACK;
				left_rotate(x->parent);
				x = ROOT;		

			}

		}
		else{
			w = x->parent->left;

			if(w->color == RED){
				w->color = BLACK;
				x->parent->color = BLACK;
				right_rotate(x->parent);
				w = x->parent->left;
			}

			if(w->left->color == BLACK && w->right->color == BLACK){
				w->color = RED;
				x->parent->color = BLACK;
				x = x->parent;
			}
			else{

				if(w->left->color == BLACK){
					w->color = RED;
					w->right->color = BLACK;
					left_rotate(w);
					w = x->parent->left;
				}

				w->color = x->parent->color;
				x->parent->color = BLACK;
				w->left->color = BLACK;
				right_rotate(x->parent);
				x = ROOT;

			}
		}

	}

	x->color = BLACK;
}

/* replace node u with node v */
void red_black_transplant(struct node *u, struct node *v){
	if(u->parent == NILL){
		ROOT = v;
	}
	else if(u == u->parent->left){
		u->parent->left = v;
	}
	else{
		u->parent->right = v;
	}

	v->parent = u->parent;
}

Hi Just been looking at this code and you need to make the following changes. The thing you need to remember is that z->parent->parent->right may be NULL and so you can't ask for its colour. But any Null nodes colour is Black so the following does this in line 203:

		if(z->parent->parent->right->color == RED){

Should be:

		if(z->parent->parent->right != NULL && z->parent->parent->right->color == RED){

Also line 229:

		if(z->parent->parent->left->color == RED){

Should be:

		if(z->parent->parent->left != NULL && z->parent->parent->left->color == RED){

There are lots of bugs in deletion operation. Try giving -> 20,10,30,25,40. It will crash.

// 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);

}