Deletion in Red-Black Tree

Last Updated : 29 Dec, 2023

Deletion in a red-black tree is a bit more complicated than insertion. When a node is to be deleted, it can either have no children, one child or two children.

Here are the steps involved in deleting a node in a red-black tree:

If the node to be deleted has no children, simply remove it and update the parent node.
If the node to be deleted has only one child, replace the node with its child.
If the node to be deleted has two children, then replace the node with its in-order successor, which is the leftmost node in the right subtree. Then delete the in-order successor node as if it has at most one child.
After the node is deleted, the red-black properties might be violated. To restore these properties, some color changes and rotations are performed on the nodes in the tree. The changes are similar to those performed during insertion, but with different conditions.
The deletion operation in a red-black tree takes O(log n) time on average, making it a good choice for searching and deleting elements in large data sets.

Reference books for more information on Red-Black Trees and their implementation in various programming languages:

“Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
“The Art of Computer Programming, Volume 3: Sorting and Searching” by Donald E. Knuth
“Algorithms in C, Part 5: Graph Algorithms” by Robert Sedgewick.

We have discussed the following topics on the Red-Black tree in previous posts. We strongly recommend referring following post as a prerequisite of this post.
Red-Black Tree Introduction
Red Black Tree Insert

Insertion Vs Deletion:
Like Insertion, recoloring and rotations are used to maintain the Red-Black properties.
In the insert operation, we check the color of the uncle to decide the appropriate case. In the delete operation, we check the color of the sibling to decide the appropriate case.
The main property that violates after insertion is two consecutive reds. In delete, the main violated property is, change of black height in subtrees as deletion of a black node may cause reduced black height in one root to leaf path.
Deletion is a fairly complex process. To understand deletion, the notion of double black is used. When a black node is deleted and replaced by a black child, the child is marked as double black. The main task now becomes to convert this double black to single black.
Deletion Steps
Following are detailed steps for deletion.
1) Perform standard BST delete. When we perform standard delete operation in BST, we always end up deleting a node which is an either leaf or has only one child (For an internal node, we copy the successor and then recursively call delete for successor, successor is always a leaf node or a node with one child). So we only need to handle cases where a node is leaf or has one child. Let v be the node to be deleted and u be the child that replaces v (Note that u is NULL when v is a leaf and color of NULL is considered as Black).
2) Simple Case: If either u or v is red, we mark the replaced child as black (No change in black height). Note that both u and v cannot be red as v is parent of u and two consecutive reds are not allowed in red-black tree.

rbdelete11

3) If Both u and v are Black.
3.1) Color u as double black. Now our task reduces to convert this double black to single black. Note that If v is leaf, then u is NULL and color of NULL is considered black. So the deletion of a black leaf also causes a double black.

rbdelete12_new

3.2) Do following while the current node u is double black, and it is not the root. Let sibling of node be s.
….(a): If sibling s is black and at least one of sibling’s children is red, perform rotation(s). Let the red child of s be r. This case can be divided in four subcases depending upon positions of s and r.
…………..(i) Left Left Case (s is left child of its parent and r is left child of s or both children of s are red). This is mirror of right right case shown in below diagram.
…………..(ii) Left Right Case (s is left child of its parent and r is right child). This is mirror of right left case shown in below diagram.
…………..(iii) Right Right Case (s is right child of its parent and r is right child of s or both children of s are red)

rbdelete13New

…………..(iv) Right Left Case (s is right child of its parent and r is left child of s)

rbdelete14

…..(b): If sibling is black and its both children are black, perform recoloring, and recur for the parent if parent is black.

rbdelete15

In this case, if parent was red, then we didn’t need to recur for parent, we can simply make it black (red + double black = single black)
…..(c): If sibling is red, perform a rotation to move old sibling up, recolor the old sibling and parent. The new sibling is always black (See the below diagram). This mainly converts the tree to black sibling case (by rotation) and leads to case (a) or (b). This case can be divided in two subcases.
…………..(i) Left Case (s is left child of its parent). This is mirror of right right case shown in below diagram. We right rotate the parent p.
…………..(ii) Right Case (s is right child of its parent). We left rotate the parent p.

rbdelete16

3.3) If u is root, make it single black and return (Black height of complete tree reduces by 1).
below is the C++ implementation of above approach:

CPP

#include <iostream>
#include <queue>
using namespace std;
 
enum COLOR { RED, BLACK };
 
class Node {
public:
  int val;
  COLOR color;
  Node *left, *right, *parent;
 
  Node(int val) : val(val) {
    parent = left = right = NULL;
 
    // Node is created during insertion
    // Node is red at insertion
    color = RED;
  }
 
  // returns pointer to uncle
  Node *uncle() {
    // If no parent or grandparent, then no uncle
    if (parent == NULL or parent->parent == NULL)
      return NULL;
 
    if (parent->isOnLeft())
      // uncle on right
      return parent->parent->right;
    else
      // uncle on left
      return parent->parent->left;
  }
 
  // check if node is left child of parent
  bool isOnLeft() { return this == parent->left; }
 
  // returns pointer to sibling
  Node *sibling() {
    // sibling null if no parent
    if (parent == NULL)
      return NULL;
 
    if (isOnLeft())
      return parent->right;
 
    return parent->left;
  }
 
  // moves node down and moves given node in its place
  void moveDown(Node *nParent) {
    if (parent != NULL) {
      if (isOnLeft()) {
        parent->left = nParent;
      } else {
        parent->right = nParent;
      }
    }
    nParent->parent = parent;
    parent = nParent;
  }
 
  bool hasRedChild() {
    return (left != NULL and left->color == RED) or
           (right != NULL and right->color == RED);
  }
};
 
class RBTree {
  Node *root;
 
  // left rotates the given node
  void leftRotate(Node *x) {
    // new parent will be node's right child
    Node *nParent = x->right;
 
    // update root if current node is root
    if (x == root)
      root = nParent;
 
    x->moveDown(nParent);
 
    // connect x with new parent's left element
    x->right = nParent->left;
    // connect new parent's left element with node
    // if it is not null
    if (nParent->left != NULL)
      nParent->left->parent = x;
 
    // connect new parent with x
    nParent->left = x;
  }
 
  void rightRotate(Node *x) {
    // new parent will be node's left child
    Node *nParent = x->left;
 
    // update root if current node is root
    if (x == root)
      root = nParent;
 
    x->moveDown(nParent);
 
    // connect x with new parent's right element
    x->left = nParent->right;
    // connect new parent's right element with node
    // if it is not null
    if (nParent->right != NULL)
      nParent->right->parent = x;
 
    // connect new parent with x
    nParent->right = x;
  }
 
  void swapColors(Node *x1, Node *x2) {
    COLOR temp;
    temp = x1->color;
    x1->color = x2->color;
    x2->color = temp;
  }
 
  void swapValues(Node *u, Node *v) {
    int temp;
    temp = u->val;
    u->val = v->val;
    v->val = temp;
  }
 
  // fix red red at given node
  void fixRedRed(Node *x) {
    // if x is root color it black and return
    if (x == root) {
      x->color = BLACK;
      return;
    }
 
    // initialize parent, grandparent, uncle
    Node *parent = x->parent, *grandparent = parent->parent,
         *uncle = x->uncle();
 
    if (parent->color != BLACK) {
      if (uncle != NULL && uncle->color == RED) {
        // uncle red, perform recoloring and recurse
        parent->color = BLACK;
        uncle->color = BLACK;
        grandparent->color = RED;
        fixRedRed(grandparent);
      } else {
        // Else perform LR, LL, RL, RR
        if (parent->isOnLeft()) {
          if (x->isOnLeft()) {
            // for left right
            swapColors(parent, grandparent);
          } else {
            leftRotate(parent);
            swapColors(x, grandparent);
          }
          // for left left and left right
          rightRotate(grandparent);
        } else {
          if (x->isOnLeft()) {
            // for right left
            rightRotate(parent);
            swapColors(x, grandparent);
          } else {
            swapColors(parent, grandparent);
          }
 
          // for right right and right left
          leftRotate(grandparent);
        }
      }
    }
  }
 
  // find node that do not have a left child
  // in the subtree of the given node
  Node *successor(Node *x) {
    Node *temp = x;
 
    while (temp->left != NULL)
      temp = temp->left;
 
    return temp;
  }
 
  // find node that replaces a deleted node in BST
  Node *BSTreplace(Node *x) {
    // when node have 2 children
    if (x->left != NULL and x->right != NULL)
      return successor(x->right);
 
    // when leaf
    if (x->left == NULL and x->right == NULL)
      return NULL;
 
    // when single child
    if (x->left != NULL)
      return x->left;
    else
      return x->right;
  }
 
  // deletes the given node
  void deleteNode(Node *v) {
    Node *u = BSTreplace(v);
 
    // True when u and v are both black
    bool uvBlack = ((u == NULL or u->color == BLACK) and (v->color == BLACK));
    Node *parent = v->parent;
 
    if (u == NULL) {
      // u is NULL therefore v is leaf
      if (v == root) {
        // v is root, making root null
        root = NULL;
      } else {
        if (uvBlack) {
          // u and v both black
          // v is leaf, fix double black at v
          fixDoubleBlack(v);
        } else {
          // u or v is red
          if (v->sibling() != NULL)
            // sibling is not null, make it red"
            v->sibling()->color = RED;
        }
 
        // delete v from the tree
        if (v->isOnLeft()) {
          parent->left = NULL;
        } else {
          parent->right = NULL;
        }
      }
      delete v;
      return;
    }
 
    if (v->left == NULL or v->right == NULL) {
      // v has 1 child
      if (v == root) {
        // v is root, assign the value of u to v, and delete u
        v->val = u->val;
        v->left = v->right = NULL;
        delete u;
      } else {
        // Detach v from tree and move u up
        if (v->isOnLeft()) {
          parent->left = u;
        } else {
          parent->right = u;
        }
        delete v;
        u->parent = parent;
        if (uvBlack) {
          // u and v both black, fix double black at u
          fixDoubleBlack(u);
        } else {
          // u or v red, color u black
          u->color = BLACK;
        }
      }
      return;
    }
 
    // v has 2 children, swap values with successor and recurse
    swapValues(u, v);
    deleteNode(u);
  }
 
  void fixDoubleBlack(Node *x) {
    if (x == root)
      // Reached root
      return;
 
    Node *sibling = x->sibling(), *parent = x->parent;
    if (sibling == NULL) {
      // No sibling, double black pushed up
      fixDoubleBlack(parent);
    } else {
      if (sibling->color == RED) {
        // Sibling red
        parent->color = RED;
        sibling->color = BLACK;
        if (sibling->isOnLeft()) {
          // left case
          rightRotate(parent);
        } else {
          // right case
          leftRotate(parent);
        }
        fixDoubleBlack(x);
      } else {
        // Sibling black
        if (sibling->hasRedChild()) {
          // at least 1 red children
          if (sibling->left != NULL and sibling->left->color == RED) {
            if (sibling->isOnLeft()) {
              // left left
              sibling->left->color = sibling->color;
              sibling->color = parent->color;
              rightRotate(parent);
            } else {
              // right left
              sibling->left->color = parent->color;
              rightRotate(sibling);
              leftRotate(parent);
            }
          } else {
            if (sibling->isOnLeft()) {
              // left right
              sibling->right->color = parent->color;
              leftRotate(sibling);
              rightRotate(parent);
            } else {
              // right right
              sibling->right->color = sibling->color;
              sibling->color = parent->color;
              leftRotate(parent);
            }
          }
          parent->color = BLACK;
        } else {
          // 2 black children
          sibling->color = RED;
          if (parent->color == BLACK)
            fixDoubleBlack(parent);
          else
            parent->color = BLACK;
        }
      }
    }
  }
 
  // prints level order for given node
  void levelOrder(Node *x) {
    if (x == NULL)
      // return if node is null
      return;
 
    // queue for level order
    queue<Node *> q;
    Node *curr;
 
    // push x
    q.push(x);
 
    while (!q.empty()) {
      // while q is not empty
      // dequeue
      curr = q.front();
      q.pop();
 
      // print node value
      cout << curr->val << " ";
 
      // push children to queue
      if (curr->left != NULL)
        q.push(curr->left);
      if (curr->right != NULL)
        q.push(curr->right);
    }
  }
 
  // prints inorder recursively
  void inorder(Node *x) {
    if (x == NULL)
      return;
    inorder(x->left);
    cout << x->val << " ";
    inorder(x->right);
  }
 
public:
  // constructor
  // initialize root
  RBTree() { root = NULL; }
 
  Node *getRoot() { return root; }
 
  // searches for given value
  // if found returns the node (used for delete)
  // else returns the last node while traversing (used in insert)
  Node *search(int n) {
    Node *temp = root;
    while (temp != NULL) {
      if (n < temp->val) {
        if (temp->left == NULL)
          break;
        else
          temp = temp->left;
      } else if (n == temp->val) {
        break;
      } else {
        if (temp->right == NULL)
          break;
        else
          temp = temp->right;
      }
    }
 
    return temp;
  }
 
  // inserts the given value to tree
  void insert(int n) {
    Node *newNode = new Node(n);
    if (root == NULL) {
      // when root is null
      // simply insert value at root
      newNode->color = BLACK;
      root = newNode;
    } else {
      Node *temp = search(n);
 
      if (temp->val == n) {
        // return if value already exists
        return;
      }
 
      // if value is not found, search returns the node
      // where the value is to be inserted
 
      // connect new node to correct node
      newNode->parent = temp;
 
      if (n < temp->val)
        temp->left = newNode;
      else
        temp->right = newNode;
 
      // fix red red violation if exists
      fixRedRed(newNode);
    }
  }
 
  // utility function that deletes the node with given value
  void deleteByVal(int n) {
    if (root == NULL)
      // Tree is empty
      return;
 
    Node *v = search(n), *u;
 
    if (v->val != n) {
      cout << "No node found to delete with value:" << n << endl;
      return;
    }
 
    deleteNode(v);
  }
 
  // prints inorder of the tree
  void printInOrder() {
    cout << "Inorder: " << endl;
    if (root == NULL)
      cout << "Tree is empty" << endl;
    else
      inorder(root);
    cout << endl;
  }
 
  // prints level order of the tree
  void printLevelOrder() {
    cout << "Level order: " << endl;
    if (root == NULL)
      cout << "Tree is empty" << endl;
    else
      levelOrder(root);
    cout << endl;
  }
};
 
int main() {
  RBTree tree;
 
  tree.insert(7);
  tree.insert(3);
  tree.insert(18);
  tree.insert(10);
  tree.insert(22);
  tree.insert(8);
  tree.insert(11);
  tree.insert(26);
  tree.insert(2);
  tree.insert(6);
  tree.insert(13);
 
  tree.printInOrder();
  tree.printLevelOrder();
 
  cout<<endl<<"Deleting 18, 11, 3, 10, 22"<<endl;
 
  tree.deleteByVal(18);
  tree.deleteByVal(11);
  tree.deleteByVal(3);
  tree.deleteByVal(10);
  tree.deleteByVal(22);
 
  tree.printInOrder();
  tree.printLevelOrder();
  return 0;
}

Java

// Java Code for the above approach
 
import java.util.LinkedList;
import java.util.Queue;
 
enum COLOR { RED, BLACK }
 
class Node {
    int val;
    COLOR color;
    Node left, right, parent;
 
    Node(int val) {
        this.val = val;
        parent = left = right = null;
         
        // Node is created during insertion
        // Node is red at insertion
        color = COLOR.RED;
    }
     
    // returns pointer to uncle
    Node uncle() {
         
        // If no parent or grandparent, then no uncle
        if (parent == null || parent.parent == null)
            return null;
         
        if (parent.isOnLeft())
            // uncle on right
            return parent.parent.right;
        else
        // uncle on left
            return parent.parent.left;
    }
     
      // check if node is left child of parent
    boolean isOnLeft() {
        return this == parent.left;
    }
     
    // returns pointer to sibling
    Node sibling() {
         
        // sibling null if no parent
        if (parent == null)
            return null;
 
        if (isOnLeft())
            return parent.right;
 
        return parent.left;
    }
     
    // moves node down and moves given node in its place
    void moveDown(Node nParent) {
        if (parent != null) {
            if (isOnLeft())
                parent.left = nParent;
            else
                parent.right = nParent;
        }
        nParent.parent = parent;
        parent = nParent;
    }
 
    boolean hasRedChild() {
        return (left != null && left.color == COLOR.RED) ||
                (right != null && right.color == COLOR.RED);
    }
}
 
class RBTree {
    Node root;
     
    // left rotates the given node
    void leftRotate(Node x) {
        // new parent will be node's right child
        Node nParent = x.right;
         
        // update root if current node is root
        if (x == root)
            root = nParent;
             
        x.moveDown(nParent);
         
        // connect x with new parent's left element
        x.right = nParent.left;
         
        // connect new parent's left element with node
        // if it is not null
        if (nParent.left != null)
            nParent.left.parent = x;
         
        // connect new parent with x
        nParent.left = x;
    }
 
    void rightRotate(Node x) {
         
        // new parent will be node's left child
        Node nParent = x.left;
         
        // update root if current node is root
        if (x == root)
            root = nParent;
 
        x.moveDown(nParent);
         
        // connect x with new parent's right element
        x.left = nParent.right;
         
        // connect new parent's right element with node
        // if it is not null
        if (nParent.right != null)
            nParent.right.parent = x;
         
        // connect new parent with x
        nParent.right = x;
    }
 
    void swapColors(Node x1, Node x2) {
        COLOR temp = x1.color;
        x1.color = x2.color;
        x2.color = temp;
    }
 
    void swapValues(Node u, Node v) {
        int temp = u.val;
        u.val = v.val;
        v.val = temp;
    }
     
    // fix red red at given node
    void fixRedRed(Node x) {
         
         // if x is root color it black and return
        if (x == root) {
            x.color = COLOR.BLACK;
            return;
        }
         
        // initialize parent, grandparent, uncle
        Node parent = x.parent, grandparent = parent.parent, uncle = x.uncle();
 
        if (parent.color != COLOR.BLACK) {
            if (uncle != null && uncle.color == COLOR.RED) {
                 
                // uncle red, perform recoloring and recurse
                parent.color = COLOR.BLACK;
                uncle.color = COLOR.BLACK;
                grandparent.color = COLOR.RED;
                fixRedRed(grandparent);
            } else {
                // Else perform LR, LL, RL, RR
                if (parent.isOnLeft()) {
                    if (x.isOnLeft())
                        // for left right
                        swapColors(parent, grandparent);
                    else {
                        leftRotate(parent);
                        swapColors(x, grandparent);
                    }
                    // for left left and left right
                    rightRotate(grandparent);
                } else {
                    if (x.isOnLeft()) {
                        // for right left
                        rightRotate(parent);
                        swapColors(x, grandparent);
                    } else
                        swapColors(parent, grandparent);
                         
                    // for right right and right left
                    leftRotate(grandparent);
                }
            }
        }
    }
    // find node that do not have a left child
    // in the subtree of the given node
    Node successor(Node x) {
        Node temp = x;
        while (temp.left != null)
            temp = temp.left;
        return temp;
    }
     
    // find node that replaces a deleted node in BST
    Node BSTreplace(Node x) {
        // when node have 2 children
        if (x.left != null && x.right != null)
            return successor(x.right);
             
        // when leaf
        if (x.left == null && x.right == null)
            return null;
             
        // when single child
        if (x.left != null)
            return x.left;
        else
            return x.right;
    }
     
    // deletes the given node
    void deleteNode(Node v) {
        Node u = BSTreplace(v);
        // True when u and v are both black
        boolean uvBlack = ((u == null || u.color == COLOR.BLACK) && (v.color == COLOR.BLACK));
        Node parent = v.parent;
 
        if (u == null) {
            // u is NULL therefore v is leaf
            if (v == root)
             // v is root, making root null
                root = null;
            else {
                if (uvBlack)
                // u and v both black
                // v is leaf, fix double black at v
                    fixDoubleBlack(v);
                     
                // u or v is red
                else if (v.sibling() != null)
                // sibling is not null, make it red
                    v.sibling().color = COLOR.RED;
                 
                // delete v from the tree
                if (v.isOnLeft())
                    parent.left = null;
                else
                    parent.right = null;
            }
            return;
        }
 
        if (v.left == null || v.right == null) {
            // v has 1 child
            if (v == root) {
                // v is root, assign the value of u to v, and delete u
                v.val = u.val;
                v.left = v.right = null;
                // delete u;
            } else {
                // Detach v from tree and move u up
                if (v.isOnLeft())
                    parent.left = u;
                else
                    parent.right = u;
 
                u.parent = parent;
 
                if (uvBlack)
                // u and v both black, fix double black at u
                    fixDoubleBlack(u);
                else
                // u or v red, color u black
                    u.color = COLOR.BLACK;
            }
            return;
        }
         
        // v has 2 children, swap values with successor and recurse
        swapValues(u, v);
        deleteNode(u);
    }
 
    void fixDoubleBlack(Node x) {
        // Reached root
        if (x == root)
            return;
 
        Node sibling = x.sibling(), parent = x.parent;
 
        if (sibling == null)
        // No sibling, double black pushed up
            fixDoubleBlack(parent);
        else {
            if (sibling.color == COLOR.RED) {
                // sibling red
                parent.color = COLOR.RED;
                sibling.color = COLOR.BLACK;
 
                if (sibling.isOnLeft())
                    // right case
                    rightRotate(parent);
                else
                    // right case
                    leftRotate(parent);
 
                fixDoubleBlack(x);
            } else {
                // Sibling black
                if (sibling.hasRedChild()) {
                    // at least 1 red children
                    if (sibling.left != null && sibling.left.color == COLOR.RED) {
                        if (sibling.isOnLeft()) {
                            // left left
                            sibling.left.color = sibling.color;
                            sibling.color = parent.color;
                            rightRotate(parent);
                        } else {
                            // right right
                            sibling.left.color = parent.color;
                            rightRotate(sibling);
                            leftRotate(parent);
                        }
                    } else {
                        if (sibling.isOnLeft()) {
                            // left right
                            sibling.right.color = parent.color;
                            leftRotate(sibling);
                            rightRotate(parent);
                        } else {
                            // right right
                            sibling.right.color = sibling.color;
                            sibling.color = parent.color;
                            leftRotate(parent);
                        }
                    }
                    parent.color = COLOR.BLACK;
                } else {
                    // 2 black children
                    sibling.color = COLOR.RED;
                    if (parent.color == COLOR.BLACK)
                        fixDoubleBlack(parent);
                    else
                        parent.color = COLOR.BLACK;
                }
            }
        }
    }
     
    // prints level order for given node
    void levelOrder(Node x) {
        if (x == null)
            return;
         
        // queue for level order
        Queue<Node> q = new LinkedList<>();
        Node curr;
 
        q.add(x);
 
        while (!q.isEmpty()) {
            curr = q.poll();
            // print node value
            System.out.print(curr.val + " ");
             
            // push children to queue
            if (curr.left != null)
                q.add(curr.left);
            if (curr.right != null)
                q.add(curr.right);
        }
    }
     
    // prints inorder recursively
    void inorder(Node x) {
        if (x == null)
            return;
 
        inorder(x.left);
        System.out.print(x.val + " ");
        inorder(x.right);
    }
     
    // constructor
    // initialize root
    RBTree() {
        root = null;
    }
 
    Node getRoot() {
        return root;
    }
     
    // searches for given value
    // if found returns the node (used for delete)
    // else returns the last node while traversing (used in insert)
    Node search(int n) {
        Node temp = root;
        while (temp != null) {
            if (n < temp.val) {
                if (temp.left == null)
                    break;
                else
                    temp = temp.left;
            } else if (n == temp.val) {
                break;
            } else {
                if (temp.right == null)
                    break;
                else
                    temp = temp.right;
            }
        }
 
        return temp;
    }
     
    // inserts the given value to tree
    void insert(int n) {
        Node newNode = new Node(n);
        if (root == null) {
            // when root is null
            // simply insert value at root
            newNode.color = COLOR.BLACK;
            root = newNode;
        } else {
            Node temp = search(n);
             
            // return if value already exists
            if (temp.val == n)
                return;
                 
            // if value is not found, search returns the node
            // where the value is to be inserted
  
            // connect new node to correct node
            newNode.parent = temp;
 
            if (n < temp.val)
                temp.left = newNode;
            else
                temp.right = newNode;
             
            // fix red red violation if exists
            fixRedRed(newNode);
        }
    }
     
    // utility function that deletes the node with given value
    void deleteByVal(int n) {
        if (root == null)
            return;
 
        Node v = search(n), u;
 
        if (v.val != n) {
            System.out.println("No node found to delete with value: " + n);
            return;
        }
 
        deleteNode(v);
    }
     
    // prints inorder of the tree
    void printInOrder() {
        System.out.println("Inorder: ");
        if (root == null)
            System.out.println("Tree is empty");
        else
            inorder(root);
        System.out.println();
    }
     
    // prints level order of the tree
    void printLevelOrder() {
        System.out.println("Level order: ");
        if (root == null)
            System.out.println("Tree is empty");
        else
            levelOrder(root);
        System.out.println();
    }
}
 
public class Main {
    public static void main(String[] args) {
        RBTree tree = new RBTree();
 
        tree.insert(7);
        tree.insert(3);
        tree.insert(18);
        tree.insert(10);
        tree.insert(22);
        tree.insert(8);
        tree.insert(11);
        tree.insert(26);
        tree.insert(2);
        tree.insert(6);
        tree.insert(13);
 
        tree.printInOrder();
        tree.printLevelOrder();
 
        System.out.println("\nDeleting 18, 11, 3, 10, 22\n");
 
        tree.deleteByVal(18);
        tree.deleteByVal(11);
        tree.deleteByVal(3);
        tree.deleteByVal(10);
        tree.deleteByVal(22);
 
        tree.printInOrder();
        tree.printLevelOrder();
    }
}
 
// This code is contributed by Abhinav Mahajan (abhinav_m22).

Python3

# Python code for the above approach
from queue import Queue
 
# Enumeration for colors
class COLOR:
    RED = 'RED'
    BLACK = 'BLACK'
 
class Node:
    def __init__(self, val):
        # Initialize node attributes
        self.val = val
        self.color = COLOR.RED  # New nodes are always red
        self.left = None
        self.right = None
        self.parent = None
 
    def uncle(self):
        # Returns the uncle of the node
        if self.parent is None or self.parent.parent is None:
            return None
 
        if self.parent.isOnLeft():
            return self.parent.parent.right
        else:
            return self.parent.parent.left
 
    def isOnLeft(self):
        # Checks if the node is the left child of its parent
        return self == self.parent.left
 
    def sibling(self):
        # Returns the sibling of the node
        if self.parent is None:
            return None
 
        if self.isOnLeft():
            return self.parent.right
        else:
            return self.parent.left
 
    def moveDown(self, new_parent):
        # Moves the node down by changing its parent
        if self.parent is not None:
            if self.isOnLeft():
                self.parent.left = new_parent
            else:
                self.parent.right = new_parent
        new_parent.parent = self.parent
        self.parent = new_parent
 
    def hasRedChild(self):
        # Checks if the node has a red child
        return (self.left is not None and self.left.color == COLOR.RED) or \
               (self.right is not None and self.right.color == COLOR.RED)
 
class RBTree:
    def __init__(self):
        # Initialize Red-Black Tree with an empty root
        self.root = None
 
    def leftRotate(self, x):
        # Performs a left rotation around the given node
        new_parent = x.right
 
        if x == self.root:
            self.root = new_parent
 
        x.moveDown(new_parent)
 
        x.right = new_parent.left
        if new_parent.left is not None:
            new_parent.left.parent = x
 
        new_parent.left = x
 
    def rightRotate(self, x):
        # Performs a right rotation around the given node
        new_parent = x.left
 
        if x == self.root:
            self.root = new_parent
 
        x.moveDown(new_parent)
 
        x.left = new_parent.right
        if new_parent.right is not None:
            new_parent.right.parent = x
 
        new_parent.right = x
 
    def swapColors(self, x1, x2):
        # Swaps the colors of two nodes
        temp = x1.color
        x1.color = x2.color
        x2.color = temp
 
    def swapValues(self, u, v):
        # Swaps the values of two nodes
        temp = u.val
        u.val = v.val
        v.val = temp
 
    def fixRedRed(self, x):
        # Fixes the red-red violation in the tree
        if x == self.root:
            x.color = COLOR.BLACK
            return
 
        parent = x.parent
        grandparent = parent.parent
        uncle = x.uncle()
 
        if parent.color != COLOR.BLACK:
            if uncle is not None and uncle.color == COLOR.RED:
                # Uncle is red, perform recoloring and recurse
                parent.color = COLOR.BLACK
                uncle.color = COLOR.BLACK
                grandparent.color = COLOR.RED
                self.fixRedRed(grandparent)
            else:
                # Perform rotations based on the cases
                if parent.isOnLeft():
                    if x.isOnLeft():
                        self.swapColors(parent, grandparent)
                    else:
                        self.leftRotate(parent)
                        self.swapColors(x, grandparent)
                    self.rightRotate(grandparent)
                else:
                    if x.isOnLeft():
                        self.rightRotate(parent)
                        self.swapColors(x, grandparent)
                    else:
                        self.swapColors(parent, grandparent)
                    self.leftRotate(grandparent)
 
    def successor(self, x):
        # Finds the in-order successor of the given node
        temp = x
 
        while temp.left is not None:
            temp = temp.left
 
        return temp
 
    def BSTreplace(self, x):
        # Finds the replacement node in BST for the given node
        if x.left is not None and x.right is not None:
            return self.successor(x.right)
 
        if x.left is None and x.right is None:
            return None
 
        if x.left is not None:
            return x.left
        else:
            return x.right
 
    def deleteNode(self, v):
        # Deletes the given node from the tree
        u = self.BSTreplace(v)
        uvBlack = (u is None or u.color == COLOR.BLACK) and (v.color == COLOR.BLACK)
        parent = v.parent
 
        if u is None:
            # Node to be deleted is a leaf or has only one child
            if v == self.root:
                # If the node is the root
                self.root = None
            else:
                # Detach v from the tree and move u up
                if uvBlack:
                    # u and v both black, fix double black at v
                    self.fixDoubleBlack(v)
                else:
                    # u or v red, color u black
                    if v.sibling() is not None:
                        v.sibling().color = COLOR.RED
 
                if v.isOnLeft():
                    parent.left = None
                else:
                    parent.right = None
 
            del v  # Delete the node
            return
 
        if v.left is None or v.right is None:
            # Node to be deleted has only one child
            if v == self.root:
                # If the node is the root
                v.val = u.val
                v.left = v.right = None
                del u
            else:
                # Detach v from the tree and move u up
                if v.isOnLeft():
                    parent.left = u
                else:
                    parent.right = u
 
                del v
                u.parent = parent
                if uvBlack:
                    # u and v both black, fix double black at u
                    self.fixDoubleBlack(u)
                else:
                    # u or v red, color u black
                    u.color = COLOR.BLACK
        else:
            # Node to be deleted has two children, swap values with successor and recurse
            self.swapValues(u, v)
            self.deleteNode(u)
 
    # Fixes the double black violation in the tree
    def fixDoubleBlack(self, x):
         
        # Reached root
        if x == self.root:
            return
 
        sibling = x.sibling()
        parent = x.parent
 
        # No sibling, double black pushed up
        if sibling is None:
            self.fixDoubleBlack(parent)
        else:
             
            # Sibling red
            if sibling.color == COLOR.RED:
                parent.color = COLOR.RED
                sibling.color = COLOR.BLACK
                 
                # Left case
                if sibling.isOnLeft():
                    self.rightRotate(parent)
                 
                # Right case
                else:
                    self.leftRotate(parent)
                self.fixDoubleBlack(x)
            else:
                 
                # Sibling black
                if sibling.hasRedChild():
                     
                    # At least 1 red child
                    if sibling.left is not None and sibling.left.color == COLOR.RED:
                         
                        # Left Left
                        if sibling.isOnLeft():
                            sibling.left.color = sibling.color
                            sibling.color = parent.color
                            self.rightRotate(parent)
                         
                        # Right Left
                        else:
                            sibling.left.color = parent.color
                            self.rightRotate(sibling)
                            self.leftRotate(parent)
                    else:
                         
                        # Left Right
                        if sibling.isOnLeft():
                            sibling.right.color = parent.color
                            self.leftRotate(sibling)
                            self.rightRotate(parent)
                         
                        # Right Right
                        else:
                            sibling.right.color = sibling.color
                            sibling.color = parent.color
                            self.leftRotate(parent)
                 
                # 2 black children
                else:
                    sibling.color = COLOR.RED
                    if parent.color == COLOR.BLACK:
                        self.fixDoubleBlack(parent)
                    else:
                        parent.color = COLOR.BLACK
     
    # Prints the level order traversal of the tree starting from the given node
    def levelOrder(self, x):
        if x is None:
            return
 
        q = Queue()
        q.put(x)
 
        while not q.empty():
            curr = q.get()
            print(curr.val, end=" ")
 
            if curr.left is not None:
                q.put(curr.left)
            if curr.right is not None:
                q.put(curr.right)
     
    # Prints the in-order traversal of the tree starting from the given node
    def inorder(self, x):
        if x is None:
            return
        self.inorder(x.left)
        print(x.val, end=" ")
        self.inorder(x.right)
 
    def getRoot(self):
        return self.root
     
    # Searches for a given value in the tree and returns the node if found
    # Otherwise, returns the last node encountered while traversing
    def search(self, n):
        temp = self.root
        while temp is not None:
            if n < temp.val:
                if temp.left is None:
                    break
                else:
                    temp = temp.left
            elif n == temp.val:
                break
            else:
                if temp.right is None:
                    break
                else:
                    temp = temp.right
 
        return temp
     
    # Inserts the given value into the tree
    def insert(self, n):
        newNode = Node(n)
         
        # When the tree is empty
        if self.root is None:
            newNode.color = COLOR.BLACK
            self.root = newNode
        else:
            temp = self.search(n)
             
            # Value already exists, return
            if temp.val == n:
                return
             
            # Connect the new node to the correct node
            newNode.parent = temp
 
            if n < temp.val:
                temp.left = newNode
            else:
                temp.right = newNode
             
            # Fix red-red violation if it exists
            self.fixRedRed(newNode)
     
    # Deletes the node with the given value from the tree
    def deleteByVal(self, n):
         
        # Tree is empty
        if self.root is None:
            return
 
        v = self.search(n)
 
        if v.val != n:
            print(f"No node found to delete with value: {n}")
            return
 
        self.deleteNode(v)
     
    # Prints the in-order traversal of the tree
    def printInOrder(self):
        print("Inorder:")
        if self.root is None:
            print("Tree is empty")
        else:
            self.inorder(self.root)
        print()
     
    # Prints the level order traversal of the tree
    def printLevelOrder(self):
        print("Level order:")
        if self.root is None:
            print("Tree is empty")
        else:
            self.levelOrder(self.root)
        print()
 
# Test the RBTree
tree = RBTree()
 
tree.insert(7)
tree.insert(3)
tree.insert(18)
tree.insert(10)
tree.insert(22)
tree.insert(8)
tree.insert(11)
tree.insert(26)
tree.insert(2)
tree.insert(6)
tree.insert(13)
 
tree.printInOrder()
tree.printLevelOrder()
 
print("Deleting 18, 11, 3, 10, 22")
 
tree.deleteByVal(18)
tree.deleteByVal(11)
tree.deleteByVal(3)
tree.deleteByVal(10)
tree.deleteByVal(22)
 
tree.printInOrder()
tree.printLevelOrder()
 
# This code is contributed by Susobhan Akhuli

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
enum COLOR { RED, BLACK }
;
 
class Node {
    public int val;
    public COLOR color;
    public Node left, right, parent;
 
    public Node(int val)
    {
        this.val = val;
        parent = left = right = null;
 
        // Node is created during insertion
        // Node is red at insertion
        color = COLOR.RED;
    }
 
    // Returns pointer to uncle
    public Node Uncle()
    {
        // If no parent or grandparent, then no uncle
        if (parent == null || parent.parent == null)
            return null;
 
        if (parent.IsOnLeft())
            // Uncle on right
            return parent.parent.right;
        else
            // Uncle on left
            return parent.parent.left;
    }
 
    // Check if node is left child of parent
    public bool IsOnLeft() { return this == parent.left; }
 
    // Returns pointer to sibling
    public Node Sibling()
    {
        // Sibling null if no parent
        if (parent == null)
            return null;
 
        if (IsOnLeft())
            return parent.right;
 
        return parent.left;
    }
 
    // Moves node down and moves given node in its place
    public void MoveDown(Node nParent)
    {
        if (parent != null) {
            if (IsOnLeft())
                parent.left = nParent;
            else
                parent.right = nParent;
        }
        nParent.parent = parent;
        parent = nParent;
    }
 
    public bool HasRedChild()
    {
        return (left != null && left.color == COLOR.RED)
            || (right != null && right.color == COLOR.RED);
    }
}
 
class RBTree {
    Node root;
 
    // Left rotates the given node
    void LeftRotate(Node x)
    {
        // New parent will be node's right child
        Node nParent = x.right;
 
        // Update root if current node is root
        if (x == root)
            root = nParent;
 
        x.MoveDown(nParent);
 
        // Connect x with new parent's left element
        x.right = nParent.left;
 
        // Connect new parent's left element with node
        // If it is not null
        if (nParent.left != null)
            nParent.left.parent = x;
 
        // Connect new parent with x
        nParent.left = x;
    }
 
    void RightRotate(Node x)
    {
        // New parent will be node's left child
        Node nParent = x.left;
 
        // Update root if current node is root
        if (x == root)
            root = nParent;
 
        x.MoveDown(nParent);
 
        // Connect x with new parent's right element
        x.left = nParent.right;
 
        // Connect new parent's right element with node
        // If it is not null
        if (nParent.right != null)
            nParent.right.parent = x;
 
        // Connect new parent with x
        nParent.right = x;
    }
 
    void SwapColors(Node x1, Node x2)
    {
        COLOR temp = x1.color;
        x1.color = x2.color;
        x2.color = temp;
    }
 
    void SwapValues(Node u, Node v)
    {
        int temp = u.val;
        u.val = v.val;
        v.val = temp;
    }
 
    // Fix red red at given node
    void FixRedRed(Node x)
    {
        // If x is root, color it black and return
        if (x == root) {
            x.color = COLOR.BLACK;
            return;
        }
 
        // Initialize parent, grandparent, uncle
        Node parent = x.parent, grandparent = parent.parent,
             uncle = x.Uncle();
 
        if (parent.color != COLOR.BLACK) {
            if (uncle != null && uncle.color == COLOR.RED) {
                // Uncle red, perform recoloring and recurse
                parent.color = COLOR.BLACK;
                uncle.color = COLOR.BLACK;
                grandparent.color = COLOR.RED;
                FixRedRed(grandparent);
            }
            else {
                // Else perform LR, LL, RL, RR
                if (parent.IsOnLeft()) {
                    if (x.IsOnLeft()) {
                        // For left right
                        SwapColors(parent, grandparent);
                    }
                    else {
                        LeftRotate(parent);
                        SwapColors(x, grandparent);
                    }
                    // For left left and left right
                    RightRotate(grandparent);
                }
                else {
                    if (x.IsOnLeft()) {
                        // For right left
                        RightRotate(parent);
                        SwapColors(x, grandparent);
                    }
                    else {
                        SwapColors(parent, grandparent);
                    }
 
                    // For right right and right left
                    LeftRotate(grandparent);
                }
            }
        }
    }
 
    // Find node that does not have a left child
    // in the subtree of the given node
    Node Successor(Node x)
    {
        Node temp = x;
        while (temp.left != null)
            temp = temp.left;
        return temp;
    }
 
    // Find node that replaces a deleted node in BST
    Node BSTreplace(Node x)
    {
        // When node has 2 children
        if (x.left != null && x.right != null)
            return Successor(x.right);
 
        // When leaf
        if (x.left == null && x.right == null)
            return null;
 
        // When single child
        return x.left != null ? x.left : x.right;
    }
 
    // Deletes the given node
    void DeleteNode(Node v)
    {
        Node u = BSTreplace(v);
 
        // True when u and v are both black
        bool uvBlack
            = ((u == null || u.color == COLOR.BLACK)
               && (v.color == COLOR.BLACK));
        Node parent = v.parent;
 
        if (u == null) {
            // u is NULL therefore v is leaf
            if (v == root) {
                // v is root, making root null
                root = null;
            }
            else {
                if (uvBlack) {
                    // u and v both black
                    // v is leaf, fix double black at v
                    FixDoubleBlack(v);
                }
                else {
                    // u or v red, color u black
                    if (v.Sibling() != null)
                        // Sibling is not null, make it red
                        v.Sibling().color = COLOR.RED;
                }
 
                // Delete v from the tree
                if (v.IsOnLeft()) {
                    parent.left = null;
                }
                else {
                    parent.right = null;
                }
            }
            return;
        }
 
        if (v.left == null || v.right == null) {
            // v has 1 child
            if (v == root) {
                // v is root, assign the value of u to v,
                // and delete u
                v.val = u.val;
                v.left = v.right = null;
                DeleteNode(u);
            }
            else {
                // Detach v from tree and move u up
                if (v.IsOnLeft()) {
                    parent.left = u;
                }
                else {
                    parent.right = u;
                }
                u.parent = parent;
 
                if (uvBlack) {
                    // u and v both black, fix double black
                    // at u
                    FixDoubleBlack(u);
                }
                else {
                    // u or v red, color u black
                    u.color = COLOR.BLACK;
                }
            }
            return;
        }
 
        // v has 2 children, swap values with successor and
        // recurse
        SwapValues(u, v);
        DeleteNode(u);
    }
 
    void FixDoubleBlack(Node x)
    {
        // Reached root
        if (x == root)
            return;
 
        Node sibling = x.Sibling(), parent = x.parent;
 
        if (sibling == null) {
            // No sibling, double black pushed up
            FixDoubleBlack(parent);
        }
        else {
            if (sibling.color == COLOR.RED) {
                // Sibling red
                parent.color = COLOR.RED;
                sibling.color = COLOR.BLACK;
                if (sibling.IsOnLeft()) {
                    // Left case
                    RightRotate(parent);
                }
                else {
                    // Right case
                    LeftRotate(parent);
                }
                FixDoubleBlack(x);
            }
            else {
                // Sibling black
                if (sibling.HasRedChild()) {
                    // At least 1 red children
                    if (sibling.left != null
                        && sibling.left.color
                               == COLOR.RED) {
                        if (sibling.IsOnLeft()) {
                            // Left left
                            sibling.left.color
                                = sibling.color;
                            sibling.color = parent.color;
                            RightRotate(parent);
                        }
                        else {
                            // Right left
                            sibling.left.color
                                = parent.color;
                            RightRotate(sibling);
                            LeftRotate(parent);
                        }
                    }
                    else {
                        if (sibling.IsOnLeft()) {
                            // Left right
                            sibling.right.color
                                = parent.color;
                            LeftRotate(sibling);
                            RightRotate(parent);
                        }
                        else {
                            // Right right
                            sibling.right.color
                                = sibling.color;
                            sibling.color = parent.color;
                            LeftRotate(parent);
                        }
                    }
                    parent.color = COLOR.BLACK;
                }
                else {
                    // 2 black children
                    sibling.color = COLOR.RED;
                    if (parent.color == COLOR.BLACK)
                        FixDoubleBlack(parent);
                    else
                        parent.color = COLOR.BLACK;
                }
            }
        }
    }
 
    // Prints level order for given node
    void LevelOrder(Node x)
    {
        if (x == null)
            return;
 
        // Queue for level order
        Queue<Node> q = new Queue<Node>();
        Node curr;
 
        // Push x
        q.Enqueue(x);
 
        while (q.Count > 0) {
            // While q is not empty
            // Dequeue
            curr = q.Dequeue();
 
            // Print node value
            Console.Write(curr.val + " ");
 
            // Push children to queue
            if (curr.left != null)
                q.Enqueue(curr.left);
            if (curr.right != null)
                q.Enqueue(curr.right);
        }
    }
 
    // Prints inorder recursively
    void Inorder(Node x)
    {
        if (x == null)
            return;
        Inorder(x.left);
        Console.Write(x.val + " ");
        Inorder(x.right);
    }
 
    public Node GetRoot() { return root; }
 
    // Searches for given value
    // If found, returns the node (used for delete)
    // Else returns the last node while traversing (used in
    // insert)
    Node Search(int n)
    {
        Node temp = root;
        while (temp != null) {
            if (n < temp.val) {
                if (temp.left == null)
                    break;
                else
                    temp = temp.left;
            }
            else if (n == temp.val) {
                break;
            }
            else {
                if (temp.right == null)
                    break;
                else
                    temp = temp.right;
            }
        }
 
        return temp;
    }
 
    // Inserts the given value to tree
    public void Insert(int n)
    {
        Node newNode = new Node(n);
        if (root == null) {
            // When root is null
            // Simply insert value at root
            newNode.color = COLOR.BLACK;
            root = newNode;
        }
        else {
            Node temp = Search(n);
 
            if (temp.val == n) {
                // Return if value already exists
                return;
            }
 
            // If value is not found, search returns the
            // node where the value is to be inserted
 
            // Connect new node to correct node
            newNode.parent = temp;
 
            if (n < temp.val)
                temp.left = newNode;
            else
                temp.right = newNode;
 
            // Fix red-red violation if exists
            FixRedRed(newNode);
        }
    }
 
    // Utility function that deletes the node with given
    // value
    public void DeleteByVal(int n)
    {
        if (root == null)
            // Tree is empty
            return;
 
        Node v = Search(n);
 
        if (v.val != n) {
            Console.WriteLine(
                "No node found to delete with value:" + n);
            return;
        }
 
        DeleteNode(v);
    }
 
    // Prints inorder of the tree
    public void PrintInOrder()
    {
        Console.WriteLine("Inorder: ");
        if (root == null)
            Console.WriteLine("Tree is empty");
        else
            Inorder(root);
        Console.WriteLine();
    }
 
    // Prints level order of the tree
    public void PrintLevelOrder()
    {
        Console.WriteLine("Level order: ");
        if (root == null)
            Console.WriteLine("Tree is empty");
        else
            LevelOrder(root);
        Console.WriteLine();
    }
}
 
public class GFG {
    static void Main()
    {
        RBTree tree = new RBTree();
 
        tree.Insert(7);
        tree.Insert(3);
        tree.Insert(18);
        tree.Insert(10);
        tree.Insert(22);
        tree.Insert(8);
        tree.Insert(11);
        tree.Insert(26);
        tree.Insert(2);
        tree.Insert(6);
        tree.Insert(13);
 
        tree.PrintInOrder();
        tree.PrintLevelOrder();
 
        Console.WriteLine("\nDeleting 18, 11, 3, 10, 22\n");
 
        tree.DeleteByVal(18);
        tree.DeleteByVal(11);
        tree.DeleteByVal(3);
        tree.DeleteByVal(10);
        tree.DeleteByVal(22);
 
        tree.PrintInOrder();
        tree.PrintLevelOrder();
    }
}
 
// This code is contributed by Susobhan Akhuli

Javascript

<script>
// Javascript program for the above approach
 
// Enumeration for color of the node
const COLOR = {
    RED: "RED",
    BLACK: "BLACK",
};
 
// Class representing a Node in the Red-Black Tree
class Node {
    constructor(val) {
        this.val = val;
        this.color = COLOR.RED;
        this.left = this.right = this.parent = null;
    }
 
    // Returns pointer to uncle
    uncle() {
        if (!this.parent || !this.parent.parent)
            return null;
 
        if (this.parent.isOnLeft())
            return this.parent.parent.right;
        else
            return this.parent.parent.left;
    }
 
    // Check if node is left child of parent
    isOnLeft() {
        return this === this.parent.left;
    }
 
    // Returns pointer to sibling
    sibling() {
        if (!this.parent)
            return null;
 
        return this.isOnLeft() ? this.parent.right : this.parent.left;
    }
 
    // Moves node down and moves given node in its place
    moveDown(nParent) {
        if (this.parent) {
            if (this.isOnLeft())
                this.parent.left = nParent;
            else
                this.parent.right = nParent;
        }
        nParent.parent = this.parent;
        this.parent = nParent;
    }
 
    // Checks if the node has a red child
    hasRedChild() {
        return (this.left && this.left.color === COLOR.RED) ||
               (this.right && this.right.color === COLOR.RED);
    }
}
 
// Class representing a Red-Black Tree
class RBTree {
    constructor() {
        this.root = null;
    }
 
    // Left rotates the given node
    leftRotate(x) {
        const nParent = x.right;
 
        if (x === this.root)
            this.root = nParent;
 
        x.moveDown(nParent);
 
        x.right = nParent.left;
 
        if (nParent.left)
            nParent.left.parent = x;
 
        nParent.left = x;
    }
 
    // Right rotates the given node
    rightRotate(x) {
        const nParent = x.left;
 
        if (x === this.root)
            this.root = nParent;
 
        x.moveDown(nParent);
 
        x.left = nParent.right;
 
        if (nParent.right)
            nParent.right.parent = x;
 
        nParent.right = x;
    }
 
    // Swaps colors of two nodes
    swapColors(x1, x2) {
        const temp = x1.color;
        x1.color = x2.color;
        x2.color = temp;
    }
 
    // Swaps values of two nodes
    swapValues(u, v) {
        const temp = u.val;
        u.val = v.val;
        v.val = temp;
    }
 
    // Fixes red-red violation at the given node
    fixRedRed(x) {
        if (x === this.root) {
            x.color = COLOR.BLACK;
            return;
        }
 
        let parent = x.parent,
            grandparent = parent.parent,
            uncle = x.uncle();
 
        if (parent.color !== COLOR.BLACK) {
            if (uncle && uncle.color === COLOR.RED) {
                parent.color = COLOR.BLACK;
                uncle.color = COLOR.BLACK;
                grandparent.color = COLOR.RED;
                this.fixRedRed(grandparent);
            } else {
                if (parent.isOnLeft()) {
                    if (x.isOnLeft()) {
                        this.swapColors(parent, grandparent);
                    } else {
                        this.leftRotate(parent);
                        this.swapColors(x, grandparent);
                    }
                    this.rightRotate(grandparent);
                } else {
                    if (x.isOnLeft()) {
                        this.rightRotate(parent);
                        this.swapColors(x, grandparent);
                    } else {
                        this.swapColors(parent, grandparent);
                    }
                    this.leftRotate(grandparent);
                }
            }
        }
    }
 
    // Finds the node that does not have a left child in the subtree of the given node
    successor(x) {
        let temp = x;
 
        while (temp.left)
            temp = temp.left;
 
        return temp;
    }
 
    // Finds the node that replaces a deleted node in BST
    BSTreplace(x) {
        if (x.left && x.right)
            return this.successor(x.right);
 
        if (!x.left && !x.right)
            return null;
 
        return x.left || x.right;
    }
 
    // Deletes the given node
    deleteNode(v) {
        const u = this.BSTreplace(v);
        const uvBlack = (!u || u.color === COLOR.BLACK) && (v.color === COLOR.BLACK);
        const parent = v.parent;
 
        if (!u) {
            if (v === this.root) {
                this.root = null;
            } else {
                if (uvBlack) {
                    this.fixDoubleBlack(v);
                } else if (v.sibling()) {
                    v.sibling().color = COLOR.RED;
                }
 
                if (v.isOnLeft()) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            }
            return;
        }
 
        if (!v.left || !v.right) {
            if (v === this.root) {
                v.val = u.val;
                v.left = v.right = null;
            } else {
                if (v.isOnLeft()) {
                    parent.left = u;
                } else {
                    parent.right = u;
                }
 
                u.parent = parent;
 
                if (uvBlack) {
                    this.fixDoubleBlack(u);
                } else {
                    u.color = COLOR.BLACK;
                }
            }
            return;
        }
 
        this.swapValues(u, v);
        this.deleteNode(u);
    }
 
    // Fixes double black at the given node
    fixDoubleBlack(x) {
        if (x === this.root)
            return;
 
        const sibling = x.sibling(),
            parent = x.parent;
 
        if (!sibling) {
            this.fixDoubleBlack(parent);
        } else {
            if (sibling.color === COLOR.RED) {
                parent.color = COLOR.RED;
                sibling.color = COLOR.BLACK;
 
                if (sibling.isOnLeft())
                    this.rightRotate(parent);
                else
                    this.leftRotate(parent);
 
                this.fixDoubleBlack(x);
            } else {
                if (sibling.hasRedChild()) {
                    if (sibling.left && sibling.left.color === COLOR.RED) {
                        if (sibling.isOnLeft()) {
                            sibling.left.color = sibling.color;
                            sibling.color = parent.color;
                            this.rightRotate(parent);
                        } else {
                            sibling.left.color = parent.color;
                            this.rightRotate(sibling);
                            this.leftRotate(parent);
                        }
                    } else {
                        if (sibling.isOnLeft()) {
                            sibling.right.color = parent.color;
                            this.leftRotate(sibling);
                            this.rightRotate(parent);
                        } else {
                            sibling.right.color = sibling.color;
                            sibling.color = parent.color;
                            this.leftRotate(parent);
                        }
                    }
                    parent.color = COLOR.BLACK;
                } else {
                    sibling.color = COLOR.RED;
                    if (parent.color === COLOR.BLACK)
                        this.fixDoubleBlack(parent);
                    else
                        parent.color = COLOR.BLACK;
                }
            }
        }
    }
 
    // Prints level order for the given node
    levelOrder(x) {
        if (!x)
            return;
 
        const q = [];
        q.push(x);
 
        while (q.length > 0) {
            const curr = q.shift();
            document.write(curr.val + " ");
 
            if (curr.left)
                q.push(curr.left);
            if (curr.right)
                q.push(curr.right);
        }
    }
 
    // Prints inorder recursively
    inorder(x) {
        if (!x)
            return;
 
        this.inorder(x.left);
        document.write(x.val + " ");
        this.inorder(x.right);
    }
 
    // Searches for the given value
    // If found, returns the node (used for delete)
    // Else returns the last node while traversing (used in insert)
    search(n) {
        let temp = this.root;
        while (temp) {
            if (n < temp.val) {
                if (!temp.left)
                    break;
                else
                    temp = temp.left;
            } else if (n === temp.val) {
                break;
            } else {
                if (!temp.right)
                    break;
                else
                    temp = temp.right;
            }
        }
 
        return temp;
    }
 
    // Inserts the given value into the tree
    insert(n) {
        const newNode = new Node(n);
        if (!this.root) {
            newNode.color = COLOR.BLACK;
            this.root = newNode;
        } else {
            const temp = this.search(n);
            if (temp.val === n)
                return;
 
            newNode.parent = temp;
 
            if (n < temp.val)
                temp.left = newNode;
            else
                temp.right = newNode;
 
            this.fixRedRed(newNode);
        }
    }
 
    // Utility function to delete the node with the given value
    deleteByVal(n) {
        if (!this.root)
            return;
 
        const v = this.search(n);
        if (v.val !== n) {
            document.write("No node found to delete with value: " + n);
            return;
        }
 
        this.deleteNode(v);
    }
 
    // Prints inorder of the tree
    printInOrder() {
     
        document.write("<br>Inorder: <br>");
        if (!this.root)
            document.write("Tree is empty");
        else
            this.inorder(this.root);
    }
 
    // Prints level order of the tree
    printLevelOrder() {
        document.write("<br>Level order: <br>");
        if (!this.root)
            document.write("Tree is empty");
        else
            this.levelOrder(this.root);
        document.write("<br>");
    }
}
 
const tree = new RBTree();
 
tree.insert(7);
tree.insert(3);
tree.insert(18);
tree.insert(10);
tree.insert(22);
tree.insert(8);
tree.insert(11);
tree.insert(26);
tree.insert(2);
tree.insert(6);
tree.insert(13);
 
tree.printInOrder();
tree.printLevelOrder();
document.write("Deleting 18, 11, 3, 10, 22");
tree.deleteByVal(18);
tree.deleteByVal(11);
tree.deleteByVal(3);
tree.deleteByVal(10);
tree.deleteByVal(22);
 
tree.printInOrder();
tree.printLevelOrder();
 
// This code is contributed by Susobhan Akhuli
</script>

Output:

Inorder: 
2 3 6 7 8 10 11 13 18 22 26 
Level order: 
10 7 18 3 8 11 22 2 6 13 26 
Deleting 18, 11, 3, 10, 22
Inorder: 
2 6 7 8 13 26 
Level order: 
13 7 26 6 8 2