private void balance ( PersistentStore store , NodeAVL x , boolean isleft ) { while ( true ) { int sign = isleft ? 1 : - 1 ; switch ( x . getBalance ( ) * sign ) { case 1 : x = x . setBalance ( store , 0 ) ; return ; case 0 : x = x . setBalance ( store , - sign ) ; break ; case - 1 : NodeAVL l = child ( store , x , isleft ) ; if ( l . getBalance ( ) == - sign ) { replace ( store , x , l ) ; x = set ( store , x , isleft , child ( store , l , ! isleft ) ) ; l = set ( store , l , ! isleft , x ) ; x = x . setBalance ( store , 0 ) ; l = l . setBalance ( store , 0 ) ; } else { NodeAVL r = child ( store , l , ! isleft ) ; replace ( store , x , r ) ; l = set ( store , l , ! isleft , child ( store , r , isleft ) ) ; r = set ( store , r , isleft , l ) ; x = set ( store , x , isleft , child ( store , r , ! isleft ) ) ; r = set ( store , r , ! isleft , x ) ; int rb = r . getBalance ( ) ; x = x . setBalance ( store , ( rb == - sign ) ? sign : 0 ) ; l = l . setBalance ( store , ( rb == sign ) ? - sign : 0 ) ; r = r . setBalance ( store , 0 ) ; } return ; } if ( x . isRoot ( ) ) { return ; } isleft = x . isFromLeft ( store ) ; x = x . getParent ( store ) ; } }
Balances part of the tree after an alteration to the index .