private void balance8 ( 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 = 8, 2k-1 = 15, k-1 = 7 [A-B-C-D-E-F-G] [7 children] becomes: *------D------* | | *--B--* *--F--* | | | | A C E G ------------------------------------------- *------D------* | | *--B--* *--F--* [9 children] | | | | A C E G - H - I - J - K - L - M - N - O becomes: *--------H--------* | | *---D---* *---L---* | | | | *-B-* *-F-* *-J-* *-N-* | | | | | | | | A C E G I K M O */ if ( maxBal == 7 ) { GBSNode a = fpoint ; GBSNode b = a . rightChild ( ) ; GBSNode c = b . rightChild ( ) ; GBSNode d = c . rightChild ( ) ; GBSNode e = d . rightChild ( ) ; GBSNode f = e . rightChild ( ) ; d . setLeftChild ( b ) ; d . setRightChild ( f ) ; b . setLeftChild ( a ) ; a . clearRightChild ( ) ; c . clearRightChild ( ) ; f . setLeftChild ( e ) ; e . clearRightChild ( ) ; if ( bparent . rightChild ( ) == a ) bparent . setRightChild ( d ) ; else bparent . setLeftChild ( d ) ; } else { if ( maxBal != 9 ) error ( "fringeBalance8: maxBal != 9, maxBal = " + maxBal ) ; GBSNode t0_top = stack . node ( fpidx - 3 ) ; GBSNode d = stack . node ( fpidx - 2 ) ; GBSNode g = fpoint ; GBSNode h = g . rightChild ( ) ; GBSNode i = h . rightChild ( ) ; GBSNode j = i . rightChild ( ) ; GBSNode k = j . rightChild ( ) ; GBSNode l = k . rightChild ( ) ; GBSNode m = l . rightChild ( ) ; GBSNode n = m . rightChild ( ) ; h . setLeftChild ( d ) ; h . setRightChild ( l ) ; l . setLeftChild ( j ) ; l . setRightChild ( n ) ; j . setLeftChild ( i ) ; i . clearRightChild ( ) ; k . clearRightChild ( ) ; n . setLeftChild ( m ) ; m . clearRightChild ( ) ; g . clearRightChild ( ) ; if ( t0_top . rightChild ( ) == d ) t0_top . setRightChild ( h ) ; else t0_top . setLeftChild ( h ) ; if ( ( fpidx > 3 ) && ( stack . balancePointIndex ( ) > - 1 ) ) { GBSNode qpoint = h ; stack . setNode ( fpidx - 2 , qpoint ) ; GBSInsertHeight . singleInstance ( ) . balance ( stack , qpoint ) ; } } }
Balance a fringe with a K factor of eight .