private void balance4 ( NodeStack stack , GBSNode bparent , /* Parent of fringe balance point */ GBSNode fpoint , /* Fringe balance point */ int fpidx , /* Index within stack of fpoint */ int maxBal ) /* Maximum allowed fringe imbalance */ { /* k = 4, 2k-1 = 7, k-1 = 3 [A-B-C] [3 children] becomes: *----B----* | | A C ------------------------------- *----B----* | | A C - D - E - F - G [5 children] becomes: *------D------* | | *--B--* *--F--* | | | | A C E G */ if ( maxBal == 3 ) { GBSNode a = fpoint ; GBSNode b = a . rightChild ( ) ; if ( bparent . rightChild ( ) == a ) bparent . setRightChild ( b ) ; else bparent . setLeftChild ( b ) ; b . setLeftChild ( a ) ; a . clearRightChild ( ) ; } else { if ( maxBal != 5 ) error ( "fringeBalance4: maxBal != 5, maxBal = " + maxBal ) ; GBSNode t0_top = stack . node ( fpidx - 2 ) ; GBSNode c = fpoint ; GBSNode d = c . rightChild ( ) ; GBSNode e = d . rightChild ( ) ; GBSNode f = e . rightChild ( ) ; d . setChildren ( bparent , f ) ; c . clearRightChild ( ) ; f . setLeftChild ( e ) ; e . clearRightChild ( ) ; if ( t0_top . rightChild ( ) == bparent ) t0_top . setRightChild ( d ) ; else t0_top . setLeftChild ( d ) ; if ( ( fpidx > 2 ) && ( stack . balancePointIndex ( ) > - 1 ) ) { GBSNode qpoint = d ; stack . setNode ( fpidx - 1 , qpoint ) ; GBSInsertHeight . singleInstance ( ) . balance ( stack , qpoint ) ; } } }
Balance a fringe with a K factor of four .