Red and Black Tree in C++

RED AND BLACK TREE:

All the case's of Insertion Deletion , Searching and Display " 
Using typedef and Structure user define data types.
Code in C++

↓↓↓↓↓↓↓
Code is Bellow ☺ ☻ ↓↓↓↓↓↓
↓↓↓↓↓↓

Source code:
Programming Seekerz :  ☺


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

enum rbtree_node_color { RED, BLACK };

typedef struct rbtree_node_t {
    void* key;
    void* value;
    struct rbtree_node_t* left;
    struct rbtree_node_t* right;
    struct rbtree_node_t* parent;
    enum rbtree_node_color color;
} *rbtree_node;

typedef struct rbtree_t {
    rbtree_node root;
} *rbtree;

typedef int (*compare_func)(void* left, void* right);

rbtree rbtree_create();

void* rbtree_lookup(rbtree t, void* key, compare_func compare);
void rbtree_insert(rbtree t, void* key, void* value, compare_func compare);
void rbtree_delete(rbtree t, void* key, compare_func compare);

typedef rbtree_node node;
typedef enum rbtree_node_color color;

static node grandparent(node n);
static node sibling(node n);
static node uncle(node n);
static void verify_properties(rbtree t);
static void verify_property_1(node root);
static void verify_property_2(node root);
static color node_color(node n);
static void verify_property_4(node root);
static void verify_property_5(node root);
static void verify_property_5_helper(node n, int black_count, int* black_count_path);

static node new_node(void* key, void* value, color node_color, node left, node right);
static node lookup_node(rbtree t, void* key, compare_func compare);
static void rotate_left(rbtree t, node n);
static void rotate_right(rbtree t, node n);

static void replace_node(rbtree t, node oldn, node newn);
static void insert_case1(rbtree t, node n);
static void insert_case2(rbtree t, node n);
static void insert_case3(rbtree t, node n);
static void insert_case4(rbtree t, node n);
static void insert_case5(rbtree t, node n);
static node maximum_node(node root);
static void delete_case1(rbtree t, node n);
static void delete_case2(rbtree t, node n);
static void delete_case3(rbtree t, node n);
static void delete_case4(rbtree t, node n);
static void delete_case5(rbtree t, node n);
static void delete_case6(rbtree t, node n);

node grandparent(node n) {
    //assert (n != NULL);
    //assert (n->parent != NULL); /* Not the root node */
    //assert (n->parent->parent != NULL); /* Not child of root */
    return n->parent->parent;
}
node sibling(node n) {
    //assert (n != NULL);
    //assert (n->parent != NULL); /* Root node has no sibling */
    if (n == n->parent->left)
        return n->parent->right;
    else
        return n->parent->left;
}
node uncle(node n) {
    //assert (n != NULL);
    //assert (n->parent != NULL); /* Root node has no uncle */
    //assert (n->parent->parent != NULL); /* Children of root have no uncle */
    return sibling(n->parent);
}
void verify_properties(rbtree t) {

    verify_property_1(t->root);
    verify_property_2(t->root);
    /* Property 3 is implicit */
    verify_property_4(t->root);
    verify_property_5(t->root);
t;
}
void verify_property_1(node n) {
    //assert(node_color(n) == RED || node_color(n) == BLACK);
    if (n == NULL) return;
    verify_property_1(n->left);
    verify_property_1(n->right);
}
void verify_property_2(node root) {
root;    //assert(node_color(root) == BLACK);
}
color node_color(node n) {
    return n == NULL ? BLACK : n->color;
}
void verify_property_4(node n) {
    if (node_color(n) == RED) {
//assert (node_color(n->left)   == BLACK);
//assert (node_color(n->right)  == BLACK);
//assert (node_color(n->parent) == BLACK);
    }
    if (n == NULL) return;
    verify_property_4(n->left);
    verify_property_4(n->right);
}
void verify_property_5(node root) {
    int black_count_path = -1;
    verify_property_5_helper(root, 0, &black_count_path);
}

void verify_property_5_helper(node n, int black_count, int* path_black_count) {
    if (node_color(n) == BLACK) {
        black_count++;
    }
    if (n == NULL) {
        if (*path_black_count == -1) {
            *path_black_count = black_count;
        } else {
   //assert (black_count == *path_black_count);
        }
        return;
    }
    verify_property_5_helper(n->left,  black_count, path_black_count);
    verify_property_5_helper(n->right, black_count, path_black_count);
}
rbtree rbtree_create() {
    rbtree t= new rbtree_t();
    t->root = NULL;
    verify_properties(t);
    return t;
}
node new_node(void* key, void* value, color node_color, node left, node right) {
    node newnode=new rbtree_node_t();
    newnode->key = key;
    newnode->value = value;
    newnode->color = node_color;
    newnode->left = left;
    newnode->right = right;
    if (left  != NULL)  left->parent = newnode;
    if (right != NULL) right->parent = newnode;
    newnode->parent = NULL;
    return newnode;
}
node lookup_node(rbtree t, void* key, compare_func compare) {
    node n = t->root;
    while (n != NULL) {
int comp_newnode = compare(key, n->key);
if (comp_newnode == 0) {
            return n;
} else if (comp_newnode < 0) {
            n = n->left;
        } else {
   //assert(comp_newnode > 0);
            n = n->right;
        }
    }
    return n;
}
void* rbtree_lookup(rbtree t, void* key, compare_func compare) {
    node n = lookup_node(t, key, compare);
    return n == NULL ? NULL : n->value;
}
void rotate_left(rbtree t, node n) {
    node r = n->right;
    replace_node(t, n, r);
    n->right = r->left;
    if (r->left != NULL) {
        r->left->parent = n;
    }
    r->left = n;
    n->parent = r;
}

void rotate_right(rbtree t, node n) {
    node L = n->left;
    replace_node(t, n, L);
    n->left = L->right;
    if (L->right != NULL) {
        L->right->parent = n;
    }
    L->right = n;
    n->parent = L;
}
void replace_node(rbtree t, node oldn, node newn) {
    if (oldn->parent == NULL) {
        t->root = newn;
    } else {
        if (oldn == oldn->parent->left)
            oldn->parent->left = newn;
        else
            oldn->parent->right = newn;
    }
    if (newn != NULL) {
        newn->parent = oldn->parent;
    }
}
void rbtree_insert(rbtree t, void* key, void* value, compare_func compare) {
    node inserted_node = new_node(key, value, RED, NULL, NULL);
    if (t->root == NULL) {
        t->root = inserted_node;
    } else {
        node n = t->root;
        while (1) {
   int comp_newnode = compare(key, n->key);
   if (comp_newnode == 0) {
                n->value = value;
                return;
   } else if (comp_newnode < 0) {
                if (n->left == NULL) {
                    n->left = inserted_node;
                    break;
                } else {
                    n = n->left;
}
            } else {
//assert (comp_newnode > 0);
                if (n->right == NULL) {
                    n->right = inserted_node;
                    break;
                } else {
                    n = n->right;
                }
            }
        }
        inserted_node->parent = n;
    }
    insert_case1(t, inserted_node);
    verify_properties(t);
}
void insert_case1(rbtree t, node n) {
    if (n->parent == NULL)
        n->color = BLACK;
    else
        insert_case2(t, n);
}
void insert_case2(rbtree t, node n) {
    if (node_color(n->parent) == BLACK)
        return; /* Tree is still valid */
    else
        insert_case3(t, n);
}
void insert_case3(rbtree t, node n) {
    if (node_color(uncle(n)) == RED) {
        n->parent->color = BLACK;
        uncle(n)->color = BLACK;
        grandparent(n)->color = RED;
        insert_case1(t, grandparent(n));
    } else {
        insert_case4(t, n);
    }
}
void insert_case4(rbtree t, node n) {
    if (n == n->parent->right && n->parent == grandparent(n)->left) {
        rotate_left(t, n->parent);
        n = n->left;
    } else if (n == n->parent->left && n->parent == grandparent(n)->right)
{
        rotate_right(t, n->parent);
        n = n->right;
    }
    insert_case5(t, n);
}
void insert_case5(rbtree t, node n) {
    n->parent->color = BLACK;
    grandparent(n)->color = RED;
    if (n == n->parent->left && n->parent == grandparent(n)->left)
 {
        rotate_right(t, grandparent(n));
    } else {
//assert (n == n->parent->right && n->parent == grandparent(n)->right);
        rotate_left(t, grandparent(n));
    }
}
void rbtree_delete(rbtree t, void* key, compare_func compare) {
    node child;
    node n = lookup_node(t, key, compare);
    if (n == NULL) return;  /* Key not found, do nothing */
    if (n->left != NULL && n->right != NULL) {
        /* Copy key/value from predecessor and then delete it instead */
        node pred = maximum_node(n->left);
        n->key   = pred->key;
        n->value = pred->value;
        n = pred;
    }

    //assert(n->left == NULL || n->right == NULL);
    child = n->right == NULL ? n->left  : n->right;
    if (node_color(n) == BLACK) {
        n->color = node_color(child);
        delete_case1(t, n);
    }
    replace_node(t, n, child);
    if (n->parent == NULL && child != NULL) // root should be black
        child->color = BLACK;
//    free(n);

    verify_properties(t);
}
static node maximum_node(node n) {
    //assert (n != NULL);
    while (n->right != NULL) {
        n = n->right;
    }
    return n;
}
void delete_case1(rbtree t, node n) {
    if (n->parent == NULL)
        return;
    else
        delete_case2(t, n);
}
void delete_case2(rbtree t, node n) {
    if (node_color(sibling(n)) == RED) {
        n->parent->color = RED;
        sibling(n)->color = BLACK;
        if (n == n->parent->left)
            rotate_left(t, n->parent);
        else
            rotate_right(t, n->parent);
    }
    delete_case3(t, n);
}
void delete_case3(rbtree t, node n) {
    if (node_color(n->parent) == BLACK &&
        node_color(sibling(n)) == BLACK &&
        node_color(sibling(n)->left) == BLACK &&
        node_color(sibling(n)->right) == BLACK)
    {
        sibling(n)->color = RED;
        delete_case1(t, n->parent);
    }
    else
        delete_case4(t, n);
}
void delete_case4(rbtree t, node n) {
    if (node_color(n->parent) == RED &&
        node_color(sibling(n)) == BLACK &&
        node_color(sibling(n)->left) == BLACK &&
        node_color(sibling(n)->right) == BLACK)
    {
        sibling(n)->color = RED;
        n->parent->color = BLACK;
    }
    else
        delete_case5(t, n);
}
void delete_case5(rbtree t, node n) {
    if (n == n->parent->left &&
        node_color(sibling(n)) == BLACK &&
        node_color(sibling(n)->left) == RED &&
        node_color(sibling(n)->right) == BLACK)
    {
        sibling(n)->color = RED;
        sibling(n)->left->color = BLACK;
        rotate_right(t, sibling(n));
    }
    else if (n == n->parent->right &&
             node_color(sibling(n)) == BLACK &&
             node_color(sibling(n)->right) == RED &&
             node_color(sibling(n)->left) == BLACK)
    {
        sibling(n)->color = RED;
        sibling(n)->right->color = BLACK;
        rotate_left(t, sibling(n));
    }
    delete_case6(t, n);
}
void delete_case6(rbtree t, node n) {
    sibling(n)->color = node_color(n->parent);
    n->parent->color = BLACK;
    if (n == n->parent->left) {
//assert (node_color(sibling(n)->right) == RED);
        sibling(n)->right->color = BLACK;
        rotate_left(t, n->parent);
    }
    else
    {
//assert (node_color(sibling(n)->left) == RED);
        sibling(n)->left->color = BLACK;
        rotate_right(t, n->parent);
    }
}

static int compare_int(void* left, void* right);
static void print_tree(rbtree t);
static void print_tree_helper(rbtree_node n, int indent);

int compare_int(void* leftp, void* rightp) {
    int left = (int)leftp;
    int right = (int)rightp;
    if (left < right)
        return -1;
    else if (left > right)
        return 1;
    else {
//assert (left == right);
        return 0;
    }
}

#define INDENT_STEP  4

void print_tree_helper(rbtree_node n, int indent);

void print_tree(rbtree t) {
    print_tree_helper(t->root, 0);
    puts(" ");
}

void print_tree_helper(rbtree_node n, int indent) {
    int i;
    if (n == NULL) {
cout<<"\n\n \t\t --< Empty tree >--\n\n ";
return;
    }
    if (n->right != NULL) {
print_tree_helper(n->right, indent + INDENT_STEP);
    }
    for(i=0; i<indent; i++)
      cout<<" ";
    if (n->color == BLACK)
printf(" Black: %d\n", (int)n->key);
    else
printf(" Red= %d\n", (int)n->key);
    if (n->left != NULL) {
print_tree_helper(n->left, indent + INDENT_STEP);
    }
}
static int x=0;
int search1(rbtree_node n,int value) {
    int i;
    if (n == NULL) {
cout<<"\n\n \t\t --< Empty tree >--\n\n ";
return 0;
    }
    if (n->right != NULL) {
search1(n->right,value);
    }
if(value==(int)n->key){
    cout<<" \n Node is Found \n";
    if (n->color == BLACK)
printf("\nColor:: Black= %d\n", (int)n->key);
    else
printf("\nColor:: Red= %d\n", (int)n->key);
x=32;
return 0; }
    if (n->left != NULL) {
search1(n->left,value);
    }
return 0;
      }

    void search(rbtree t,int v) {
    search1(t->root, v);if( x != 32 )cout<<"\n\nNot Found...\n";
x=0;    }

void main() {

    int i,x,y,c=0;
    rbtree tree = rbtree_create();
while(!0){
    cout<<"\n============================================\n";
    cout<<"\n\nChoose Any Of Following Option:\n\n\n\t\t[ 1 for Insertion]\n\t\t";
cout<<"[ 2 for Deletion ]\n\t\t[ 3 for Display  ]\n\t\t[ 4 For Searching]\n\t\t[ 5 For Exit     ]\n\n";
    cin>>c;
    cout<<"\n============================================\n";
    switch(c){
    case 1:{
    cout<<"\n\nHow Many Values You Want To Insert: ";
    cin>>y;
    for(i=0; i<y; i++) {
    cout<<"\n Insert Value For insertion: ";
    cin>>x;
int y = rand() % 10000;
printf("\nInserting value is=  %d \n\n", x);
rbtree_insert(tree, (void*)x, (void*)y, compare_int);
}      break;    }
    case 2:{
cout<<" \n Enter Value For Deletion: ";
cin>>x;
printf("Deleting key %d\n\n", x);
rbtree_delete(tree, (void*)x, compare_int);
      break; }
    case 3:{
    print_tree(tree);
    break;
    }
    case 4:{
    cout<<"\n\nEnter A value for search: ";
    cin>>x;
    search(tree,x);
    break;}
    case 5:{
    exit(0);
    }
    default:{break;}
    }

}
}