static <V> TreeNode<V> balanceDeletion(TreeNode<V> root,
                                                 TreeNode<V> x) {
          for (TreeNode<V> xp, xpl, xpr;;) {
              if (x == null || x == root)
                  return root;
              else if ((xp = x.parent) == null) {
                  x.red = false;
                  return x;
              }
              else if (x.red) {
                  x.red = false;
                  return root;
              }
              else if ((xpl = xp.left) == x) {
                  if ((xpr = xp.right) != null && xpr.red) {
                      xpr.red = false;
                      xp.red = true;
                      root = rotateLeft(root, xp);
                      xpr = (xp = x.parent) == null ? null : xp.right;
                  }
                  if (xpr == null)
                      x = xp;
                  else {
                      TreeNode<V> sl = xpr.left, sr = xpr.right;
                      if ((sr == null || !sr.red) &&
                          (sl == null || !sl.red)) {
                          xpr.red = true;
                          x = xp;
                      }
                      else {
                          if (sr == null || !sr.red) {
                              if (sl != null)
                                  sl.red = false;
                              xpr.red = true;
                              root = rotateRight(root, xpr);
                              xpr = (xp = x.parent) == null ?
                                  null : xp.right;
                          }
                          if (xpr != null) {
                              xpr.red = (xp == null) ? false : xp.red;
                              if ((sr = xpr.right) != null)
                                  sr.red = false;
                          }
                          if (xp != null) {
                              xp.red = false;
                              root = rotateLeft(root, xp);
                          }
                          x = root;
                      }
                  }
              }
              else { // symmetric
                  if (xpl != null && xpl.red) {
                      xpl.red = false;
                      xp.red = true;
                      root = rotateRight(root, xp);
                      xpl = (xp = x.parent) == null ? null : xp.left;
                  }
                  if (xpl == null)
                      x = xp;
                  else {
                      TreeNode<V> sl = xpl.left, sr = xpl.right;
                      if ((sl == null || !sl.red) &&
                          (sr == null || !sr.red)) {
                          xpl.red = true;
                          x = xp;
                      }
                      else {
                          if (sl == null || !sl.red) {
                              if (sr != null)
                                  sr.red = false;
                              xpl.red = true;
                              root = rotateLeft(root, xpl);
                              xpl = (xp = x.parent) == null ?
                                  null : xp.left;
                          }
                          if (xpl != null) {
                              xpl.red = (xp == null) ? false : xp.red;
                              if ((sl = xpl.left) != null)
                                  sl.red = false;
                          }
                          if (xp != null) {
                              xp.red = false;
                              root = rotateRight(root, xp);
                          }
                          x = root;
                      }
                  }
              }
          }
      }
static <V> TreeNode<V> balanceDeletion(TreeNode<V> root,
                                                 TreeNode<V> x)