private void lastFringe ( DeleteStack . FringeNote xx , GBSNode g , boolean gLeft , DeleteStack stack , int ntop , InsertStack istack ) { if ( gLeft ) { /* Original father was left child */ stack . setNode ( ntop , g . leftChild ( ) ) ; /* Put new left parent on stack */ } else { /* Original parent was right child */ stack . setNode ( ntop , g . rightChild ( ) ) ; /* Put new right parent on stack */ } GBSNode p = xx . newf ; GBSNode q = null ; istack . start ( xx . newg , "GBSDeleteFringe.lastFringe" ) ; istack . resetBalancePointIndex ( ) ; GBSNode fpoint = null ; int fdepth = 0 ; int fpidx = 0 ; while ( p != null ) { fdepth ++ ; istack . push ( p ) ; if ( fpoint == null ) { if ( p . leftChild ( ) == null ) /* First right-heavy half leaf */ { fdepth = 1 ; /* Reset fringe depth */ fpoint = p ; /* Remember fringe balance point */ fpidx = istack . index ( ) ; /* Remember index to fringe balance pt. */ } } q = p ; p = p . rightChild ( ) ; } int maxBal = g . kFactor ( ) + 1 ; if ( ( g . kFactor ( ) % 3 ) == 0 ) { maxBal = g . kFactor ( ) + 2 ; } if ( ( fdepth > maxBal ) || ( ( fdepth >= maxBal ) && ( q . isFull ( ) ) ) ) { GBSInsertFringe . singleInstance ( ) . balance ( g . kFactor ( ) , istack , fpoint , fpidx , maxBal ) ; if ( xx . conditionalDecrease ) { stack . node ( ntop ) . setBalance ( xx . conditionalBalance ) ; } xx . conditionalDecrease = false ; } if ( xx . conditionalDecrease ) { xx . depthDecrease = true ; } if ( xx . depthDecrease ) { GBSDeleteHeight . singleInstance ( ) . balance ( stack , ntop ) ; } }
Examine the final fringe and re - balance if necessary .