Red-black Tree implementation

red_black.c

/**
 * Implements red-black trees, the exposed functions are the ones with prefix
 * `rd_` but without node i.e. `rd_node_` (these are internal functions)
 */

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

#define RED true
#define BLACK false

typedef bool color;

typedef struct node {
	int value;
	struct node* left;
	struct node* right;
	struct node* parent;
	color color;
} node;

typedef struct {
	node* root;
} rb_tree;

rb_tree* rb_new()
{
	rb_tree* tree = malloc(sizeof(rb_tree));
	tree->root = NULL;
	return tree;
}

node* rb_node_new(int value)
{
	node* ris = malloc(sizeof(node));
	ris->parent = NULL;
	ris->left = NULL;
	ris->right = NULL;
	ris->value = value;
	ris->color = RED;
	return ris;
}

// Returns NULL if there ISN'T a double red violation
node* rb_node_insert(node* root, int value)
{
	if(value < root->value) {
		if(root->left == NULL) {
			root->left = rb_node_new(value);
			root->left->parent = root;
			if(root->color == RED)
				return root->parent;
		} else {
			return rb_node_insert(root->left, value);
		}
	} else if(value > root->value) {
		if(root->right == NULL) {
			root->right = rb_node_new(value);
			root->right->parent = root;
			if(root->color == RED)
				return root->parent;
		} else {
			return rb_node_insert(root->right, value);
		}
	}
	return NULL;
}

// Returns the new root of the rotated sub-tree
node* rb_node_rotate_right(node* root)
{
	node* par = root->parent;
	node* ris = root->left;
	root->left = ris->right;
	ris->right = root;
	root->parent = ris;
	if(par != NULL && par->left == root)
		par->left = ris;
	else if(par != NULL)
		par->right = ris;
	ris->parent = par;
	return ris;
}

// Returns the new root of the rotated sub-tree
node* rb_node_rotate_left(node* root)
{
	node* par = root->parent;
	node* ris = root->right;
	root->right = ris->left;
	ris->left = root;
	root->parent = ris;
	if(par != NULL && par->left == root)
		par->left = ris;
	else if(par != NULL)
		par->right = ris;
	ris->parent = par;
	return ris;
}

void rb_node_recolor(node* root)
{
	root->color = RED;
	root->left->color = BLACK;
	root->right->color = BLACK;
}

void rb_node_fix(node* root, int value, rb_tree* tree)
{
	node* ris;
	if(value < root->value) {
		if(root->right == NULL || root->right->color == BLACK) {
			ris = rb_node_rotate_right(root);
			ris->color = BLACK;
			ris->right->color = RED;
			if(root == tree->root)
				tree->root = ris;
			return;
		} else {
			rb_node_recolor(root);
		}
	} else if(value > root->value) {
		if(root->left == NULL || root->left->color == BLACK) {
			ris = rb_node_rotate_left(root);
			ris->color = BLACK;
			ris->left->color = RED;
			if(root == tree->root)
				tree->root = ris;
			return;
		} else {
			rb_node_recolor(root);
		}
	}

	// Propagation is triggered only upon recoloring
	if(root->parent == NULL) {
		root->color = BLACK;
		return;
	}
	if(root->parent->parent == NULL) {
		root->parent->color = BLACK;
		return;
	}
	rb_node_fix(root->parent->parent, root->value, tree);
}

void rb_insert(rb_tree* tree, int value)
{
	node* violation;
	if(tree->root == NULL) {
		tree->root = rb_node_new(value);
		tree->root->color = BLACK;
		return;
	}

	violation = rb_node_insert(tree->root, value);
	if(violation == NULL)
		return;

	rb_node_fix(violation, value, tree);
}

void rb_node_free(node* root)
{
	if(root->left != NULL)
		rb_node_free(root->left);
	if(root->right != NULL)
		rb_node_free(root->right);
	free(root);
}

void rb_free(rb_tree* tree)
{
	if(tree->root != NULL)
		rb_node_free(tree->root);
	free(tree);
}

// Strinctly for DEBUG
void vfs(node* root)
{
	printf("%d\n", root->value);
	if(root->left != NULL)
		vfs(root->left);
	if(root->right != NULL)
		vfs(root->right);
}

int main()
{
	rb_tree* tree = rb_new();
	rb_insert(tree, 1);
	for(int x = 2; x <= 8; x++) {
		rb_insert(tree, x);
	}
	vfs(tree->root);
	rb_free(tree);
}