// returns true is Node's color is true or NULL

bool Node::isBlack() {
    return (this == NULL || this->black == true);
}

Node* Node::succ(Node* x){
    if (x->right != NULL) return Min(x->right);
    Node* pt = x->parent;
    while (pt != NULL && x == pt->right){
        x = pt;
        pt = pt->parent;
    }
    return pt;
}

// removal method
Node* Node::RBRemove(Node* root, string key) {
    Node* node = search(root, key);
    Node* y = NULL;
    Node* x = NULL;
    Node* z = NULL;
    if (node->left != NULL && node->right != NULL) {
        y = succ(node);
    }
    else{
        y = node;
    }

    if (y->getLeft() != NULL) {
        x = y->getLeft();
    }
    else {
        x = y->getRight();
    }
    if(x) x->parent = y->parent;
    if (y->getParent() == NULL) {
        root = x;
    }
    else {
        if (y == y->getParent()->getLeft())
            y->getParent()->left = x;
        else
            y->getParent()->right = x;
    }
    if (y != node) {
        node->key = y->getKey();
    }
    if (y->isBlack()) {
        delProcess(root, x, y->parent);
    }
    return root;
}

// rotation method (just a single rotation)

void Node::Rotate(Node* &root, bool recolor) {
    Node* x = this;
    Node* parent = x->parent;
    Node* gp = getGP(x);
    x->parent = gp; // x's parent points to grandparent
    if (gp != NULL) {
        if (r(gp) == parent) { // if p is right child of gp
            gp->right = x; // gp right points to x
        }
        else {
            gp->left = x; // gp left points to x
        }
    }
    else {
        root = x;
    }


    if (x == r(parent)) {
        Node* left = x->left;
        x->left = parent;
        parent->parent = x;
        parent->right = left;
        if (left != NULL) {
            left->parent = parent;
        }
    }
    else if (x == l(parent)){
        Node* right = x->right;
        x->right = parent;
        parent->parent = x;
        parent->left = right;
        if (right != NULL) {
            right->parent = parent;
        }
    }

    if (recolor) {
        bool xc = x->black;
        bool pc = NULL;
        if(parent->black) pc = parent->black;
        x->black = pc;
        parent->black = xc;
    }
}


// method where I fix up the tree after removal

bool isBlack(Node* n) {
    if (n == NULL || n->isBlack() == true) return true;
    else return false;
}

void delProcess(Node* &root, Node* x, Node* p) {
    if (!isBlack(x)) {
        x->setColor(true);
        return;
    }
    if (p == NULL) {
        return;
    }
    else {
        Node* w = NULL;
        if (x == p->getRight()) {
            w = p->getLeft();
        }
        else {
            w = p->getRight();
        }
        if (!isBlack(w)) { // handles the case where sibling node is red
            bool temp = isBlack(w);
            w->Rotate(root, true);
            delProcess(root, x, p, z);
        }
        else if (isBlack(w->getLeft()) && isBlack(w->getRight())) { // handles case where siblings left and right children are black (or NULL)
            w->setColor(false);
            x = p;
            p = p->getParent();
            delProcess(root, x, p, z);
        }

        else if (!isBlack(w->getDirect(w))) { // handles case where siblings direct child is red
                Node* direct = w->getDirect(w);
                direct->setColor(true);
                w->Rotate(root, true);
        }
        else { // the case where there is a zig-zag child is present and double rotation is required
                Node* zz = x == w->getRight() ? zz = w->getLeft() : zz = w->getRight();
                zz->Rotate(root, true);
                zz->Rotate(root, true);
                w->setColor(true);
        }
    }
}