mirror of https://github.com/TheAlgorithms/C
798 lines
21 KiB
C
798 lines
21 KiB
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
|