void balance ( NodeStack stack , GBSNode q ) { GBSNode p ; int bpidx = stack . balancePointIndex ( ) ; int x = bpidx ; GBSNode bpoint = stack . node ( x ) ; GBSNode bfather = stack . node ( x - 1 ) ; /* Adjust balance factors in intervening nodes */ if ( bpoint . leftChild ( ) == stack . node ( x + 1 ) ) p = bpoint . leftChild ( ) ; else p = bpoint . rightChild ( ) ; x ++ ; while ( p != q ) { if ( p . leftChild ( ) == stack . node ( x + 1 ) ) { /* We followed and added to left path */ p . setBalance ( - 1 ) ; /* It is now left heavy */ p = p . leftChild ( ) ; } else /* We followed and added to right path */ { p . setBalance ( 1 ) ; /* It is now right heavy */ p = p . rightChild ( ) ; } x ++ ; } /* Adjust the balance factor at the balance point. */ /* Re-balance if necessary. */ if ( bpoint . leftChild ( ) == stack . node ( bpidx + 1 ) ) { /* Added to left side */ int bpb = bpoint . balance ( ) ; switch ( bpb ) { case 0 : bpoint . setBalance ( - 1 ) ; break ; case 1 : bpoint . clearBalance ( ) ; break ; case - 1 : rotateLeft ( bfather , bpoint ) ; break ; default : String zzz1 = "Help1 !, bpb = " + bpb ; throw new RuntimeException ( zzz1 ) ; } } else /* Added to right side */ { int bpb = bpoint . balance ( ) ; switch ( bpb ) { case 0 : bpoint . setBalance ( 1 ) ; break ; case - 1 : bpoint . clearBalance ( ) ; break ; case 1 : rotateRight ( bfather , bpoint ) ; break ; default : String zzz2 = "Help2 !, bpb = " + bpb ; throw new RuntimeException ( zzz2 ) ; } } }
Restore the height balance of a tree following an insert .