#include 
using namespace std;

enum{
	RED,
	BLACK,
	DOUBLE_BLACK
};

struct Node{
	int data, color;
	Node *left, *right, *parent;
	Node(int data){
		this->data = data;
		this->color = RED;
		left = right = parent = NULL;
	}
};

class RedBlackTree{
	private:
		Node *root;
		void rotateLeft(Node *node){
			Node *right = node->right;
			node->right = right->left;
			if(node->right != NULL)
				node->right->parent = node;
			right->parent = node->parent;
			if(node->parent == NULL)
				root = right;
			else if(node == node->parent->left)
				node->parent->left = right;
			else
				node->parent->right = right;
			right->left = node;
			node->parent = right;
		}
		void rotateRight(Node *node){
			Node *left = node->left;
			node->left = left->right;
			if(node->left != NULL)
				node->left->parent = node;
			left->parent = node->parent;
			if(node->parent == NULL)
				root = left;
			else if(node == node->parent->left)
				node->parent->left = left;
			else
				node->parent->right = left;
			left->right = node;
			node->parent = left;
		}
		void fixInsertion(Node *node){
			if(root == node){
				node->color = BLACK;
				return;
			}
			while(node->color != BLACK && node->parent->color == RED){
				Node *grand_parent = node->parent->parent;
				//When parent of new node is left child of grandparents of new node
				if(grand_parent->left == node->parent){
					Node *temp = grand_parent->right;
					//If new node's grand parent right child is red, recolor
					if(grand_parent->right != NULL && temp->color == RED){
						node->parent->color = temp->color = BLACK;
						grand_parent->color = RED;
						node = grand_parent;
					}else{
						//If node is right child of its parent, left rotate
						if(node->parent->right == node){
							rotateLeft(node->parent);
							node = node->parent;
						}
						//If node is left child of its parent, right rotate
						rotateRight(grand_parent);
						swap(node->parent->color, grand_parent->color);
						node = node->parent;
					}
				//When parent of new node is right child of grandparents of new node
				}else{
					Node *temp = grand_parent->left;
					//If grandparent left child is red, recolor
					if(grand_parent->left != NULL && temp->color == RED){
						node->parent->color = temp->color = BLACK;
						grand_parent->color = RED;
						node = grand_parent;
					}else{
						//If node is left child of its parent, right rotate (Same as right grandparent child case)
						if(node->parent->left == node){
							rotateRight(node);
							node = node->parent;
						}
						//If node is right click of its parent, left rotate
						rotateLeft(node);
						swap(node->parent->color, grand_parent->color);
						node = node->parent;
					}
				}
				root->color = BLACK;
			}
		}
		Node* getSmallestNode(Node *node){
			Node *curr = node;
			while(curr->left != NULL)
				curr = curr->left;
			return curr;
		}
		//Normal BST delete process
		Node* deleteValue(Node *root, int target){
			if(root == NULL)
				return root;
			if(target < root->data)
				return deleteValue(root->left, target);
			if(target > root->data)
				return deleteValue(root->right, target);
			if(root->left == NULL || root->right == NULL)
				return root;
			Node *temp = getSmallestNode(root->right);
			root->data = temp->data;
			return deleteValue(root->right, temp->data);
		}
		int getColor(Node *node){
			if(node == NULL)
				return BLACK;
			return node->color;
		}
		void fixDeletion(Node *node){
			if(node == NULL)
				return;
			if(node == root){
				root = NULL;
				return;
			}
			if(getColor(node) == RED || getColor(node->left) == RED || getColor(node->right) == RED){
				Node *child = node->left != nullptr ? node->left : node->right;
				if(node == node->parent->left){
					node->parent->left = child;
					if(child != NULL){
						child->parent = node->parent;
						child->color = BLACK;
					}
					delete(node);
				}else{
					node->parent->right = child;
					if(child != NULL){
						child->parent = node->parent;
						child->color = BLACK;
					}
					delete(node);
				}
			}else{
				Node *parent, *sibling, *temp;
				parent = sibling = NULL;
				temp = node;
				temp->color = DOUBLE_BLACK;

				while(temp != root && getColor(temp) == DOUBLE_BLACK){
					parent = temp->parent;
					if(temp == parent->left){
						sibling = parent->right;
						if(getColor(sibling) == RED){
							sibling->color = BLACK;
							parent->color = RED;
							rotateLeft(parent);
						}else{
							if(getColor(sibling->left) == BLACK && getColor(sibling->right) == BLACK){
								sibling->color = RED;
								if(getColor(parent) == RED)
									parent->color = BLACK;
								else
									parent->color = DOUBLE_BLACK;
								temp = parent;
							}else{
								if(getColor(sibling->right) == BLACK){
									sibling->left->color = BLACK;
									sibling->color = RED;
									rotateRight(sibling);
									sibling = parent->right;
								}
								sibling->color = parent->color;
								parent->color = sibling->right->color = BLACK;
								rotateLeft(parent);
								break;
							}
						}
					}else{
						sibling = parent->left;
						if(getColor(sibling) == RED){
							sibling->color = BLACK;
							parent->color = RED;
							rotateRight(parent);
						}else{
							if(getColor(sibling->left) == BLACK && getColor(sibling->right) == BLACK){
								sibling->color = RED;
								if(getColor(parent) == RED)
									parent->color = BLACK;
								else
									parent->color = DOUBLE_BLACK;
								temp = parent;
							}else{
								if(getColor(sibling->left) == BLACK){
									sibling->right->color = BLACK;
									sibling->color = RED;
									rotateLeft(sibling);
									sibling = parent->left;
								}
								sibling->color = parent->color;
								parent->color = sibling->left->color = BLACK;
								rotateRight(parent);
								break;
							}
						}
					}
				}
				if(node == node->parent->left)
					node->parent->left = NULL;
				else
					node->parent->right = NULL;
				delete(node);
				root->color = BLACK;
			}
		}
	public:
		RedBlackTree(){
			this->root = NULL;
		}
		void insertNode(int data){
			Node *node = new Node(data);
			if(root == NULL){
				this->root = node;
			}else{
				Node *curr = root, *parent;
				while(curr != NULL){
					parent = curr;
					if(curr->data < data)
						curr = curr->right;
					else
						curr = curr->left;
				}
				node->parent = parent;
				if(parent->data < data)
					parent->right = node;
				else
					parent->left = node;
			}
			fixInsertion(node);
		}
		void deleteNode(int target){
			Node *node = deleteValue(root, target);
			fixDeletion(node);
		}
		void searchNode(int target){
			Node *curr = root;
			while(curr->data != target){
				if(curr->data < target){
					curr = curr->right;
				}else{
					curr = curr->left;
				}
			}
			printf("Color of Node %d : %s\n", target, (curr->color == BLACK ? "BLACK" : "RED"));
		}
};

int main(){
	RedBlackTree tree;
    tree.insertNode(7); 
    tree.insertNode(6); 
    tree.insertNode(5); 
    tree.insertNode(4); 
    tree.insertNode(3); 
    tree.insertNode(2); 
    tree.insertNode(1);

    tree.deleteNode(4);
    tree.deleteNode(3);
    tree.searchNode(6);
	return 0;
}