private Region remove(Region x, Region t) {
    if (t != NULL_NODE) {
      // Step 1: Search down the tree and set lastNode and deletedNode
      this.lastNode = t;
      if (x.orderRelativeTo(t) < 0) {
        t.left(remove(x, t.left));
      } else {
        this.deletedNode = t;
        t.right(remove(x, t.right));
      }
      // Step 2: If at the bottom of the tree and
      // x is present, we remove it
      if (t == this.lastNode) {
        if (this.deletedNode != NULL_NODE && x.orderRelativeTo(this.deletedNode) == 0) {
          this.deletedNode.swap(t);
          this.deletedElement = t;
          t = t.right;
        }
      } else if (t.left.level < t.level - 1 || t.right.level < t.level - 1) {
        // Step 3: Otherwise, we are not at the bottom; re-balance
        if (t.right.level > --t.level) {
          t.right.level = t.level;
        }
        t = skew(t);
        t.right(skew(t.right));
        t.right.right(skew(t.right.right));
        t = split(t);
        t.right(split(t.right));
      }
    }
    return t;
  }
private Region remove ( Region x , Region t ) { if ( t != NULL_NODE ) { this . lastNode = t ; if ( x . orderRelativeTo ( t ) < 0 ) { t . left ( remove ( x , t . left ) ) ; } else { this . deletedNode = t ; t . right ( remove ( x , t . right ) ) ; } if ( t == this . lastNode ) { if ( this . deletedNode != NULL_NODE && x . orderRelativeTo ( this . deletedNode ) == 0 ) { this . deletedNode . swap ( t ) ; this . deletedElement = t ; t = t . right ; } } else if ( t . left . level < t . level - 1 || t . right . level < t . level - 1 ) { if ( t . right . level > -- t . level ) { t . right . level = t . level ; } t = skew ( t ) ; t . right ( skew ( t . right ) ) ; t . right . right ( skew ( t . right . right ) ) ; t = split ( t ) ; t . right ( split ( t . right ) ) ; } } return t ; }
Internal method to remove from a subtree.

@param x
the item to remove.
@param t
the node that roots the tree.
@return the new root.