I was implementing a Red-Black Tree (RBT) ( in C) and I would like to implement a function that verifies that my RBT is indeed valid. Just an antagonistic function that gives me a final check everything that indeed everything works as expected. I am trying to implement that but I really can't find any way to implement that. Could you guys help me out?
This is my RBT program:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define RED 'R'
#define BLACK 'B'
//body structure of the RBT tree
typedef struct rbtNode {
int key;
char color;
struct rbtNode *left_Child;
struct rbtNode *right_Child;
struct rbtNode *parent;
} rbtNode;
struct rbtNode T_Nil_Node; // sentinel node
rbtNode* T_Nil = &T_Nil_Node; //defining the T_Nil node
rbtNode* Root = NULL;
//Function that creates a node with the given key
rbtNode* new_Node(int key)
{
rbtNode *temp = (rbtNode*) malloc(sizeof(rbtNode));
temp->key = key;
temp->color = RED;
temp->left_Child = NULL;
temp->right_Child = NULL;
temp->parent = NULL;
return temp;
}
//Function that perform the left rotation which is need in the Fixup function
void RBTreeLeftRotate( rbtNode** T, rbtNode* x)
{
rbtNode* y = x->right_Child;
x->right_Child = y->left_Child;
if (y->left_Child != T_Nil)
y->left_Child->parent = x;
y->parent = x->parent;
if (x->parent == T_Nil)
*T = y;
else if (x == x->parent->left_Child)
x->parent->left_Child = y;
else
x->parent->right_Child = y;
y->left_Child = x;
x->parent = y;
}
//Function that perform the right rotation which is need in the Fixup function
void RBTreeRightRotate(rbtNode** T, rbtNode* y)
{
rbtNode *x = y->left_Child;
y->left_Child = x->right_Child;
if (x->right_Child != T_Nil)
x->right_Child->parent = y;
x->parent = y->parent;
if (y->parent == T_Nil)
*T = x;
else if (y == y->parent->right_Child)
y->parent->right_Child = x;
else
y->parent->left_Child = x;
x->right_Child = y;
y->parent = x;
}
//Function that perform the left Fixup operation which is need in the Insert function
void RBTreeFixUpLeft(rbtNode** root, rbtNode* n){
rbtNode* t;
t = n->parent->parent->right_Child;
if(t->color == RED){
n->parent->color = BLACK;
t->color = BLACK;
n->parent->parent->color = RED;
n = n->parent->parent;
}else{
if(n == n->parent->right_Child){
n = n->parent;
RBTreeLeftRotate(root,n);
}
n->parent->color = BLACK;
n->parent->parent->color = RED;
RBTreeRightRotate(root,n->parent->parent);
}
}
//Function which performs the right Fixup operation which is need in the Insert function
void RBTreeFixUpRight(rbtNode** root, rbtNode* n){
rbtNode* t;
t = n->parent->parent->left_Child;
if(t->color == RED){
n->parent->color = BLACK;
t->color = BLACK;
n->parent->parent->color = RED;
n = n->parent->parent;
}else{
if(n == n->parent->left_Child){
n = n->parent;
RBTreeRightRotate(root,n);
}
n->parent->color = BLACK;
n->parent->parent->color = RED;
RBTreeLeftRotate(root,n->parent->parent);
}
}
//Fix Up function which is need in the Insert function
void RBTreeFixUp(rbtNode** root, rbtNode* new){
rbtNode* temp;
while(new->parent->color == RED){
if(new->parent == new->parent->parent->left_Child){
RBTreeFixUpLeft(root,new);
}else{
RBTreeFixUpRight(root,new);
}
}
root[0]->color = BLACK;
}
//Primary insertion function
void RBTreeInsert(rbtNode** T, rbtNode* z)
{
rbtNode* y = T_Nil;
rbtNode* x = *T;
// Find where to Insert new node Z into the binary search tree
while (x != T_Nil) {
y = x;
if (z->key < x->key)
x = x->left_Child;
else
x = x->right_Child;
}
z->parent = y;
if (y == T_Nil)
*T = z;
else if (z->key < y->key)
y->left_Child = z;
else
y->right_Child = z;
// Init z as a red leaf
z->left_Child = T_Nil;
z->right_Child = T_Nil;
z->color = RED;
// Ensure the Red-Black property is maintained
RBTreeFixUp(T, z);
}
//Function that searches for the given key in the tree
void RBTreeSearch(struct rbtNode* root, int key){
if(root == T_Nil || root->key == key){
return;
}
if(key <= root->key){
RBTreeSearch(root->left_Child,key);
}else{
RBTreeSearch(root->right_Child,key);
}
}
//Function that empties the tree
void RBTreeEmptying(struct rbtNode* root){
if(root == NULL){
return;
}
RBTreeEmptying(root->left_Child);
RBTreeEmptying(root->right_Child);
if(root != T_Nil){
free(root);
}
}
//main experiment of the RBT tree experiment
double RBTSingleExperiment(int max_keys,double max_search,int max_instances){
double t_tot = 0;
int i;
int key;
double search;
int seed = 169704;
for(i = 1; i<=max_instances;i++){
clock_t start_t, end_t;
srand(seed);
rbtNode* root = T_Nil;
start_t = clock();
for(key = 1; key <= max_keys; key++){
RBTreeInsert(&root, new_Node(rand()));
}
for(search =1; search <= max_search; search++){
RBTreeSearch(root,rand());
}
end_t = clock();
double t_elapsed = (double)(end_t - start_t);
t_tot += t_elapsed;
RBTreeEmptying(root);
seed = seed + 1;
}
return t_tot/max_instances;
}
int main(void){
int min_keys = 100000;
int max_keys = 1000000;
int max_instances = 5;
int percentage_search = 60;
int keys;
int seed = 169704;
//Setting up the main paramenters for this experiment
for(keys = min_keys; keys <= max_keys; keys += 100000){
srand(seed);
double max_search = (double)keys * (double)percentage_search /100.0;
double max_delete = keys - max_search;
double timeRBT = RBTSingleExperiment(keys,max_search,max_instances);
printf("Number of keys: %d || timeRBT: %f\n", keys, timeRBT);
seed = seed + 1;
}
}
Thanks in advance!
Here is a function RBTCheck that will check the red-black tree, using an auxiliary recursive function RBTCheck_:
static unsigned int RBTCheck_(struct rbtNode *parent, struct rbtNode *node) {
unsigned int left_black_height = 0;
unsigned int right_black_height = 0;
if (node == NULL) {
printf("Node is NULL instead of T_Nil");
if (parent->left_Child == NULL) {
printf(", maybe left child");
}
if (parent->right_Child == NULL) {
printf(", maybe right child");
}
printf(" of parent %p (key %d)\n", (void *)parent, parent->key);
} else if (node != T_Nil) {
if (node->parent != parent) {
printf("Node %p (key %d) has wrong parent %p, expected %p (key %d)\n",
(void *)node, node->key, (void *)node->parent,
(void *)parent, parent->key);
}
if (node->color == BLACK) {
left_black_height++;
right_black_height++;
} else if (node->color != RED) {
printf("Node %p (key %d) has unknown color\n",
(void *)node, node->key);
}
if (node->color == RED && parent->color == RED) {
printf("Node %p (key %d) and parent %p (key %d) are both RED.\n",
(void *)node, node->key,
(void *)parent, parent->key);
}
left_black_height += RBTCheck_(node, node->left_Child);
right_black_height += RBTCheck_(node, node->right_Child);
}
if (left_black_height != right_black_height) {
printf("Node %p (key %d) unbalanced (%u, %u)\n",
(void *)node, node->key, left_black_height, right_black_height);
}
if (left_black_height > right_black_height) {
return left_black_height;
} else {
return right_black_height;
}
}
void RBTCheck(struct rbtNode *root) {
unsigned int left_black_height = 0;
unsigned int right_black_height = 0;
if (!root) {
printf("Root is NULL instead of T_Nil\n");
} else if (root != T_Nil) {
if (root->color != BLACK) {
printf("Root %p (key %d) color is not BLACK\n",
(void *)root, root->key);
} else {
left_black_height = 1;
right_black_height = 1;
}
left_black_height += RBTCheck_(root, root->left_Child);
right_black_height += RBTCheck_(root, root->right_Child);
}
if (left_black_height != right_black_height) {
printf("Root %p (key %d) unbalanced (%u, %u)\n",
(void *)root, root->key, left_black_height, right_black_height);
}
}
It does basic sanity checks on tree linkage, checks for valid colors, checks that a node and its parent are not both RED, and checks that the left and right sub-trees have balanced BLACK node depth.
As a bonus, here is a function RBTDump to dump the red-black tree (apart from the parent members), using an auxiliary, recursive function RBTDump_:
static void RBTDump_(struct rbtNode *root, unsigned int depth) {
unsigned int i;
for (i = 0; i < depth; i++) {
printf(" ");
}
if (root == NULL) {
printf("NULL\n");
} else if (root == T_Nil) {
printf("T_Nil\n");
} else {
printf("%p (key %d, color %c)\n", (void *)root, root->key, root->color);
RBTDump_(root->left_Child, depth + 1);
RBTDump_(root->right_Child, depth + 1);
}
}
void RBTDump(struct rbtNode *root) {
RBTDump_(root, 0);
}
Adding calls RBTDump(root); and RBTCheck(root); to your RBTSingleExperiment function, after the loop that inserts the nodes shows that it is not passing the checks.