private void balance6 ( 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 = 6, 2k-1 = 11, k-1 = 5 [A-B-C-D-E] [5 children] becomes: *--C--* | | *-B D-* | | A E ------------------------------- *--C--* | | [8 children] *-B D-* | | A E - F - G - H - I - J - K becomes: *-------F-------* | | *--C--* *--I--* | | | | *-B D-* *-H J-* | | | | A E G K */ if ( maxBal == 5 ) { GBSNode a = fpoint ; GBSNode b = a . rightChild ( ) ; GBSNode c = b . rightChild ( ) ; if ( bparent . rightChild ( ) == a ) bparent . setRightChild ( c ) ; else bparent . setLeftChild ( c ) ; c . setLeftChild ( b ) ; b . setChildren ( a , null ) ; a . clearRightChild ( ) ; } else { if ( maxBal != 8 ) error ( "fringeBalance6: maxBal != 8, maxBal = " + maxBal ) ; GBSNode t0_top = stack . node ( fpidx - 2 ) ; GBSNode c = bparent ; GBSNode d = fpoint ; GBSNode e = d . rightChild ( ) ; GBSNode f = e . rightChild ( ) ; GBSNode g = f . rightChild ( ) ; GBSNode h = g . rightChild ( ) ; GBSNode i = h . rightChild ( ) ; f . setChildren ( c , i ) ; i . setLeftChild ( h ) ; h . setChildren ( g , null ) ; g . clearRightChild ( ) ; e . clearRightChild ( ) ; if ( t0_top . rightChild ( ) == c ) t0_top . setRightChild ( f ) ; else t0_top . setLeftChild ( f ) ; if ( ( fpidx > 2 ) && ( stack . balancePointIndex ( ) > - 1 ) ) { GBSNode qpoint = f ; stack . setNode ( fpidx - 1 , qpoint ) ; GBSInsertHeight . singleInstance ( ) . balance ( stack , qpoint ) ; } } }
Balance a fringe with a K factor of six .