Function that verifies the validity of the Red-Black Tree-CodePudding

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!

CodePudding user response：

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.