private void leftFringe ( DeleteStack . Linearizer lxx , DeleteStack . FringeNote xx , InsertStack istack , GBSNode f , GBSNode g , boolean gLeft , int t0_depth ) { GBSNode w = f . rightChild ( ) ; /* The right brother of delete fringe */ GBSNode s = f . leftChild ( ) ; /* t0 fringe from which we deleted */ GBSNode bfather = g ; GBSNode sh = null ; /* The linearized s */ GBSNode p = null ; int fbalance = f . balance ( ) ; f . clearBalance ( ) ; if ( w == null ) /* There is no right brother */ { sh = linearize ( lxx , s ) ; f . setRightChild ( null ) ; combine ( lastInList ( sh ) , f ) ; /* [s, f] */ p = sh ; xx . depthDecrease = true ; } else /* There is a right brother */ { p = linearize ( lxx , s ) ; f . setChildren ( null , null ) ; combine ( lastInList ( p ) , f ) ; /* [s, f] */ sh = p ; /* Assume linear list or single t0 */ GBSNode wh = w . leftMostChild ( istack ) ; int zpoints = istack . index ( ) ; if ( zpoints > 0 ) /* Is a t0 fringe (possibly more */ { /* than one level down) */ zpoints -- ; int ztop = 0 ; /* Assume top of entire tree */ if ( zpoints >= t0_depth ) /* Have more than a whole t0 fringe */ { ztop = zpoints - t0_depth + 1 ; sh = w ; /* We will elevate w */ bfather = istack . node ( ztop - 1 ) ; bfather . setLeftChild ( p ) ; /* Father of left-most fringe */ /* points to linear list */ } /* Linearize left-most fringe */ wh = linearize ( lxx , istack . node ( ztop ) ) ; } combine ( lastInList ( p ) , wh ) ; /* Add w onto f (now [s, f, w]) */ leftDepth ( xx , fbalance ) ; /* Check for depth change */ } if ( gLeft ) { g . setLeftChild ( sh ) ; } else { g . setRightChild ( sh ) ; } boolean bLeft = true ; if ( bfather . rightChild ( ) == p ) { bLeft = false ; } int maxBal = g . kFactor ( ) - 1 ; if ( maxBal < 3 ) { maxBal = 3 ; } istack . start ( bfather , "GBSDeleteFringe.leftFringe" ) ; istack . setNode ( 1 , null ) ; istack . resetBalancePointIndex ( ) ; int fpidx = 1 ; if ( g . kFactor ( ) > 2 ) { GBSInsertFringe . singleInstance ( ) . balance ( g . kFactor ( ) , istack , p , fpidx , maxBal ) ; } xx . newg = bfather ; if ( bLeft ) { xx . newf = bfather . leftChild ( ) ; } else { xx . newf = bfather . rightChild ( ) ; } }
Handle the case where we deleted from a left fringe .