TreeNode<T> rbDelete(TreeNode<T> root,TreeNode<T> z)
//return new root, z contains item to be deleted
{
  TreeNode<T> x,y;
  // find node y, which is going to be removed
  if (z.getLeft() == null || z.getRight() == null)
    y = z;
  else { 
    y = successor(z); // or predecessor
    z.setItem(y.getItem); // move data from y to z
  }
  
  // find child x of y
  if (y.getRight() != null)
    x = y.getRight();
  else
    x = y.getLeft();
  
  // Note x might be null; create a pretend node
  if (x == null) {
    x = new TreeNode<T>(null);
    x.setColor(black);
  }
  
  x.setParent(y.getParent()); // detach x from y
  if (y.getParent() == null) 
    // if y was the root, x is a new root
    root = x;
  else
    // Atttach x to y’s parent
    if (y == y.getParent().getLeft()) // left child
      y.getParent().setLeft(x);
    else
      y.getParent().setRight(x);
  
  if (y.getColor() == black)
    root=rbTreeFix(root,x);
  
  if (x.getItem() == null) // x is a pretend node
    if (x==x.getParent().getLeft())
      x.getParent().setLeft(null);
    else
      x.getParent().setRight(null);
  
  return root;
}