private void deleteCheckFringeBalance ( DeleteStack stack , GBSNode endp , int endIndex , int maxBal ) { int fDepth = 0 ; /* Fringe balance depth */ fDepth = 0 ; if ( endp . leftChild ( ) == null ) { fDepth = 1 ; /* Last node counts as one */ for ( int j = endIndex ; j > 0 ; j -- ) { GBSNode q = stack . node ( j ) ; if ( q . leftChild ( ) == null ) /* Have not found end yet */ fDepth ++ ; else /* Found the top of the fringe */ break ; } } int t0_depth = tZeroDepth ( ) ; int t = t0_depth ; if ( t < 1 ) t = 1 ; if ( ( stack . maxDepth ( ) >= t ) && /* Deep enough for a t0 and */ ( endp . population ( ) == ( endp . width ( ) - 1 ) ) ) /* Last node was full */ { /* Check for a possible t0 tree */ int j = 1 ; if ( ( kFactor ( ) % 3 ) == 0 ) j = 2 ; if ( fDepth == j ) { _xno ++ ; GBSDeleteFringe . singleInstance ( ) . balance ( tZeroDepth ( ) , stack ) ; } } else /* Not a t0 fringe */ { /* Check for empty node */ if ( endp . population ( ) != 0 ) endp . adjustMedian ( ) ; else { _xno ++ ; GBSNode p = stack . node ( endIndex ) ; if ( p . leftChild ( ) == endp ) p . setLeftChild ( null ) ; else p . setRightChild ( null ) ; } } }
Check to see if fringe balancing is required following a delete and do the fringe rebalancing if needed .