red_black_tree.c

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

typedef struct node
{
    int val;
    struct node *par;
    struct node *left;
    struct node *right;
    int color;
} Node;

// Create a new node
Node *newNode(int val, Node *par)
{
    Node *create = (Node *)(malloc(sizeof(Node)));
    create->val = val;
    create->par = par;
    create->left = NULL;
    create->right = NULL;
    create->color = 1;
}

// Check if the node is the leaf
int isLeaf(Node *n)
{
    if (n->left == NULL && n->right == NULL)
    {
        return 1;
    }
    return 0;
}

// Left Rotate
Node *leftRotate(Node *node)
{
    Node *parent = node->par;
    Node *grandParent = parent->par;

    parent->right = node->left;
    if (node->left != NULL)
    {
        node->left->par = parent;
    }
    node->par = grandParent;
    parent->par = node;
    node->left = parent;
    if (grandParent != NULL)
    {
        if (grandParent->right == parent)
        {
            grandParent->right = node;
        }
        else
        {
            grandParent->left = node;
        }
    }
    return node;
}

// Right Rotate
Node *rightRotate(Node *node)
{
    Node *parent = node->par;
    Node *grandParent = parent->par;

    parent->left = node->right;
    if (node->right != NULL)
    {
        node->right->par = parent;
    }
    node->par = grandParent;
    parent->par = node;
    node->right = parent;
    if (grandParent != NULL)
    {
        if (grandParent->right == parent)
        {
            grandParent->right = node;
        }
        else
        {
            grandParent->left = node;
        }
    }
    return node;
}

// Check the node after the insertion step
void checkNode(Node *node)
{
    // If the node is the root
    if (node == NULL || node->par == NULL)
    {
        return;
    }
    Node *child = node;
    // If it is a black node or its parent is a black node
    if (node->color == 0 || (node->par)->color == 0)
    {
        // Dont Do Anything
        return;
    }

    // Both parent and child are red
    // Check For Uncle
    Node *parent = node->par;
    Node *grandParent = parent->par;

    // If grandParent is NULL, then parent is the root.
    // Just make the root black.
    if (grandParent == NULL)
    {
        parent->color = 0;
        return;
    }

    // If both the children of the grandParent are red
    if (grandParent->right != NULL && (grandParent->right)->color == 1 &&
        grandParent->left != NULL && (grandParent->left)->color == 1)
    {
        // Make the grandParent red and both of its children black
        (grandParent->right)->color = 0;
        (grandParent->left)->color = 0;
        grandParent->color = 1;
        return;
    }
    else
    {
        // The only option left is rotation.
        Node *greatGrandParent = grandParent->par;
        // Right Case
        if (grandParent->right == parent)
        {
            // Right Right Case
            if (parent->right == node)
            {
                grandParent->right = parent->left;
                if (parent->left != NULL)
                {
                    (parent->left)->par = grandParent;
                }
                parent->left = grandParent;
                grandParent->par = parent;

                // Attach to existing Tree;
                parent->par = greatGrandParent;
                if (greatGrandParent != NULL)
                {
                    if (greatGrandParent->left != NULL &&
                        greatGrandParent->left == grandParent)
                    {
                        greatGrandParent->left = parent;
                    }
                    else
                    {
                        greatGrandParent->right = parent;
                    }
                }

                // Change the colors
                parent->color = 0;
                grandParent->color = 1;
            }
            else
            {  // Right Left Case
                // First step -> Parent Child Rotation
                parent->left = child->right;
                if (child->right != NULL)
                {
                    (child->right)->par = parent;
                }
                child->right = parent;
                parent->par = child;

                // Second step -> Child and GrandParent Rotation
                grandParent->right = child->left;
                if (child->left != NULL)
                {
                    (child->left)->par = grandParent;
                }
                child->left = grandParent;
                grandParent->par = child;

                // Attach to the existing tree
                child->par = greatGrandParent;
                if (greatGrandParent != NULL)
                {
                    if (greatGrandParent->left != NULL &&
                        greatGrandParent->left == grandParent)
                    {
                        greatGrandParent->left = child;
                    }
                    else
                    {
                        greatGrandParent->right = child;
                    }
                }

                // Change The Colors
                child->color = 0;
                grandParent->color = 1;
            }
        }
        else
        {  // Left Case
            // Left Left Case
            if (parent->left == node)
            {
                grandParent->left = parent->right;
                if (parent->right != NULL)
                {
                    (parent->right)->par = grandParent;
                }
                parent->right = grandParent;
                grandParent->par = parent;

                // Attach to existing Tree;
                parent->par = greatGrandParent;
                if (greatGrandParent != NULL)
                {
                    if (greatGrandParent->left != NULL &&
                        greatGrandParent->left == grandParent)
                    {
                        greatGrandParent->left = parent;
                    }
                    else
                    {
                        greatGrandParent->right = parent;
                    }
                }

                // Change the colors
                parent->color = 0;
                grandParent->color = 1;
            }
            else
            {  // Left Right Case

                // First step -> Parent Child Rotation
                parent->right = child->left;
                if (child->left != NULL)
                {
                    (child->left)->par = parent;
                }
                child->left = parent;
                parent->par = child;

                // Second step -> Child and GrandParent Rotation
                grandParent->left = child->right;
                if (child->right != NULL)
                {
                    (child->right)->par = grandParent;
                }
                child->right = grandParent;
                grandParent->par = child;

                // Attach to the existing tree
                child->par = greatGrandParent;
                if (greatGrandParent != NULL)
                {
                    if (greatGrandParent->left != NULL &&
                        greatGrandParent->left == grandParent)
                    {
                        greatGrandParent->left = child;
                    }
                    else
                    {
                        greatGrandParent->right = child;
                    }
                }

                // Change The Colors
                child->color = 0;
                grandParent->color = 1;
            }
        }
    }
}

// To insert a node in the existing tree
void insertNode(int val, Node **root)
{
    Node *buffRoot = *root;
    while (buffRoot)
    {
        if (buffRoot->val > val)
        {
            // Go left
            if (buffRoot->left != NULL)
            {
                buffRoot = buffRoot->left;
            }
            else
            {
                // Insert The Node
                Node *toInsert = newNode(val, buffRoot);
                buffRoot->left = toInsert;
                buffRoot = toInsert;

                // Check For Double Red Problems
                break;
            }
        }
        else
        {
            // Go right
            if (buffRoot->right != NULL)
            {
                buffRoot = buffRoot->right;
            }
            else
            {
                // Insert The Node
                Node *toInsert = newNode(val, buffRoot);
                buffRoot->right = toInsert;
                buffRoot = toInsert;

                // Check For Double Red Problems
                break;
            }
        }
    }

    while (buffRoot != *root)
    {
        checkNode(buffRoot);
        if (buffRoot->par == NULL)
        {
            *root = buffRoot;
            break;
        }
        buffRoot = buffRoot->par;
        if (buffRoot == *root)
        {
            buffRoot->color = 0;
        }
    }
}

void checkForCase2(Node *toDelete, int delete, int fromDirection, Node **root)
{
    if (toDelete == (*root))
    {
        (*root)->color = 0;
        return;
    }

    if (!delete &&toDelete->color == 1)
    {
        if (!fromDirection)
        {
            if (toDelete->right != NULL)
            {
                toDelete->right->color = 1;
            }
        }
        else
        {
            if (toDelete->left != NULL)
            {
                toDelete->left->color = 1;
            }
        }
        toDelete->color = 0;
        return;
    }

    // Get the sibling for further inspection
    Node *sibling;
    Node *parent = toDelete->par;
    int locateChild = 0;  // 0 if toDeleted is left of its parent else 1
    if (parent->right == toDelete)
    {
        sibling = parent->left;
        locateChild = 1;
    }
    else
    {
        sibling = parent->right;
    }

    // Case 2.1. i.e. if the any children of the sibling is red
    if ((sibling->right != NULL && sibling->right->color == 1) ||
        (sibling->left != NULL && sibling->left->color == 1))
    {
        if (sibling->right != NULL && sibling->right->color == 1)
        {
            // Sibling is left and child is right. i.e. LEFT RIGHT ROTATION
            if (locateChild == 1)
            {
                int parColor = parent->color;

                // Step 1: Left rotate sibling
                sibling = leftRotate(sibling->right);

                // Step 2: Right rotate updated sibling
                parent = rightRotate(sibling);

                // Check if the root is rotated
                if (parent->par == NULL)
                {
                    *root = parent;
                }

                // Step 3: Update the colors
                parent->color = parColor;
                parent->left->color = 0;
                parent->right->color = 0;

                // Delete the node (present at parent->right->right)
                if (delete)
                {
                    if (toDelete->left != NULL)
                    {
                        toDelete->left->par = parent->right;
                    }
                    parent->right->right = toDelete->left;
                    free(toDelete);
                }
            }
            else
            {  // Sibling is right and child is also right. i.e. LEFT LEFT
               // ROTATION

                int parColor = parent->color;

                // Left Rotate the sibling
                parent = leftRotate(sibling);

                // Check if the root is rotated
                if (parent->par == NULL)
                {
                    *root = parent;
                }

                // Update Colors
                parent->color = parColor;
                parent->left->color = 0;
                parent->right->color = 0;

                // Delete the node (present at parent->left->left)
                if (delete)
                {
                    if (toDelete->right != NULL)
                    {
                        toDelete->right->par = parent->left;
                    }
                    parent->left->left = toDelete->left;
                    free(toDelete);
                }
            }
        }
        else
        {
            // Sibling is right and child is left. i.e. RIGHT LEFT ROTATION
            if (locateChild == 0)
            {
                int parColor = parent->color;

                // Step 1: Right rotate sibling
                sibling = rightRotate(sibling->left);

                // printf("%d - reached\n", sibling->val);
                // return;

                // Step 2: Left rotate updated sibling
                parent = leftRotate(sibling);

                // Check if the root is rotated
                if (parent->par == NULL)
                {
                    *root = parent;
                }

                // Step 3: Update the colors
                parent->color = parColor;
                parent->left->color = 0;
                parent->right->color = 0;

                // Delete the node (present at parent->left->left)
                if (delete)
                {
                    if (toDelete->right != NULL)
                    {
                        toDelete->right->par = parent->left;
                    }
                    parent->left->left = toDelete->right;
                    free(toDelete);
                }
            }
            else
            {  // Sibling is left and child is also left. i.e. RIGHT RIGHT
               // ROTATION

                int parColor = parent->color;

                // Right Rotate the sibling
                parent = rightRotate(sibling);

                // Check if the root is rotated
                if (parent->par == NULL)
                {
                    *root = parent;
                }

                // Update Colors
                parent->color = parColor;
                parent->left->color = 0;
                parent->right->color = 0;

                // Delete the node (present at parent->right->right)
                if (delete)
                {
                    if (toDelete->left != NULL)
                    {
                        toDelete->left->par = parent->right;
                    }
                    parent->right->right = toDelete->left;
                    free(toDelete);
                }
            }
        }
    }
    else if (sibling->color == 0)
    {  // Make the sibling red and recur for its parent

        // Recolor the sibling
        sibling->color = 1;

        // Delete if necessary
        if (delete)
        {
            if (locateChild)
            {
                toDelete->par->right = toDelete->left;
                if (toDelete->left != NULL)
                {
                    toDelete->left->par = toDelete->par;
                }
            }
            else
            {
                toDelete->par->left = toDelete->right;
                if (toDelete->right != NULL)
                {
                    toDelete->right->par = toDelete->par;
                }
            }
        }

        checkForCase2(parent, 0, locateChild, root);
    }
    else
    {  // Bring the sibling on top and apply 2.1 or 2.2 accordingly
        if (locateChild)
        {  // Right Rotate

            toDelete->par->right = toDelete->left;
            if (toDelete->left != NULL)
            {
                toDelete->left->par = toDelete->par;
            }

            parent = rightRotate(sibling);

            // Check if the root is rotated
            if (parent->par == NULL)
            {
                *root = parent;
            }

            parent->color = 0;
            parent->right->color = 1;
            checkForCase2(parent->right, 0, 1, root);
        }
        else
        {  // Left Rotate

            toDelete->par->left = toDelete->right;
            if (toDelete->right != NULL)
            {
                toDelete->right->par = toDelete->par;
            }
            parent = leftRotate(sibling);

            // Check if the root is rotated
            if (parent->par == NULL)
            {
                *root = parent;
            }

            printf("\nroot - %d - %d\n", parent->val, parent->left->val);

            parent->color = 0;
            parent->left->color = 1;
            checkForCase2(parent->left, 0, 0, root);
        }
    }
}

// To delete a node from the tree
void deleteNode(int val, Node **root)
{
    Node *buffRoot = *root;

    // Search for the element in the tree
    while (1)
    {
        if (val == buffRoot->val)
        {
            // Node Found
            break;
        }

        if (val > buffRoot->val)
        {
            if (buffRoot->right != NULL)
            {
                buffRoot = buffRoot->right;
            }
            else
            {
                printf("Node Not Found!!!");
                return;
            }
        }
        else
        {
            if (buffRoot->left != NULL)
            {
                buffRoot = buffRoot->left;
            }
            else
            {
                printf("Node Not Found!!!");
                return;
            }
        }
    }

    Node *toDelete = buffRoot;

    // Look for the leftmost of right node or right most of left node
    if (toDelete->left != NULL)
    {
        toDelete = toDelete->left;
        while (toDelete->right != NULL)
        {
            toDelete = toDelete->right;
        }
    }
    else if (toDelete->right != NULL)
    {
        toDelete = toDelete->right;
        while (toDelete->left != NULL)
        {
            toDelete = toDelete->left;
        }
    }

    if (toDelete == *root)
    {
        *root = NULL;
        return;
    }

    // Swap the values
    buffRoot->val = toDelete->val;
    toDelete->val = val;

    // Checking for case 1
    if (toDelete->color == 1 ||
        (toDelete->left != NULL && toDelete->left->color == 1) ||
        (toDelete->right != NULL && toDelete->right->color == 1))
    {
        // if it is a leaf
        if (toDelete->left == NULL && toDelete->right == NULL)
        {
            // Delete instantly
            if (toDelete->par->left == toDelete)
            {
                toDelete->par->left = NULL;
            }
            else
            {
                toDelete->par->right = NULL;
            }
        }
        else
        {  // else its child should be red

            // Check for the exitstence of left node
            if (toDelete->left != NULL)
            {
                // The node should be right to its parent
                toDelete->par->right = toDelete->left;
                toDelete->left->par = toDelete->par;
                toDelete->left->color = 1;
            }
            else
            {  // else the right node should be red
                toDelete->par->left = toDelete->right;
                toDelete->right->par = toDelete->par;
                toDelete->right->color = 1;
            }
        }

        // Remove the node from memory
        free(toDelete);
    }
    else
    {  // Case 2
        checkForCase2(toDelete, 1, ((toDelete->par->right == toDelete)), root);
    }
}

void printInorder(Node *root)
{
    if (root != NULL)
    {
        printInorder(root->left);
        printf("%d c-%d ", root->val, root->color);
        printInorder(root->right);
    }
}

void checkBlack(Node *temp, int c)
{
    if (temp == NULL)
    {
        printf("%d ", c);
        return;
    }
    if (temp->color == 0)
    {
        c++;
    }
    checkBlack(temp->left, c);
    checkBlack(temp->right, c);
}

int main()
{
    Node *root = NULL;
    int scanValue, choice = 1;
    printf(
        "1 - Input\n2 - Delete\n3 - Inorder Traversel\n0 - Quit\n\nPlease "
        "Enter the Choice - ");
    scanf("%d", &choice);
    while (choice)
    {
        switch (choice)
        {
        case 1:
            printf("\n\nPlease Enter A Value to insert - ");
            scanf("%d", &scanValue);
            if (root == NULL)
            {
                root = newNode(scanValue, NULL);
                root->color = 0;
            }
            else
            {
                insertNode(scanValue, &root);
            }
            printf("\nSuccessfully Inserted %d in the tree\n\n", scanValue);
            break;
        case 2:
            printf("\n\nPlease Enter A Value to Delete - ");
            scanf("%d", &scanValue);
            deleteNode(scanValue, &root);
            printf("\nSuccessfully Inserted %d in the tree\n\n", scanValue);
            break;
        case 3:
            printf("\nInorder Traversel - ");
            printInorder(root);
            printf("\n\n");
            // checkBlack(root,0);
            // printf("\n");
            break;
        default:
            if (root != NULL)
            {
                printf("Root - %d\n", root->val);
            }
        }
        printf(
            "1 - Input\n2 - Delete\n3 - Inorder Traversel\n0 - "
            "Quit\n\nPlease Enter the Choice - ");
        scanf("%d", &choice);
    }
}

// 32 12 50 53 1 2 3 4 5 6 7 8 9