RBT

#include <bits/stdc++.h>
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;
}