TreeNode<T> rbTreeFix(TreeNode<T> root,TreeNode<T> x)
//return new root; x is a node with the black token
{
  while (x != root && x.getColor() == black) // not case (1)
    if (x == x.getParent().getLeft()) { // x is left child
      y = x.getParent().getRight(); // y is x’s sibling 
      if (y.getColor() == red) { // case (2)
        y.setColor(black);
        x.getParent().setColor(red); // p was black
        root = left_rotate(root,x.getParent());
        y = x.getParent().getRight(); // new sibling
      }
      if (y.getLeft().getColor() == black && 
          y.getRight().getColor() == black) { 
        // nephews are black - case (3)
        y.setColor(red);
        x = x.getParent();
      } else { // case (4)
        if (y.getRight().getColor() == black) {
          // subcase (i)
          y.getLeft().setColor(black);
          y.setColor(red);
          root = right_rotate(root,y);
          y = x.getParent().getRight();
        }
        // subcase (ii)
        y.setColor(x.getParent().getColor());
        x.getParent().setColor(black);
        y.getRight().setColor(black);
        root = left_rotate(root, x.getParent());
        x = root; // we can finish
      }
    } else {
      … // x is right child - symmetric
    }
  // end while loop
  x.setColor(black);
  return root;
}