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 ; }
Internal method to remove from a subtree .