private Node balance ( Node node ) { if ( node == null ) { return null ; } int imbalance = getHeight ( node . left ) - getHeight ( node . right ) ; if ( imbalance > MAX_IMBALANCE ) { // Left subtree has higher height than right subtree. if ( getHeight ( node . left . left ) < getHeight ( node . left . right ) ) { // Double rotate binary tree node: first left child with its right child; then the node with new left child. node . left = rotateRight ( node . left ) ; } return rotateLeft ( node ) ; } else if ( - imbalance > MAX_IMBALANCE ) { // Right subtree has higher height than left subtree. if ( getHeight ( node . right . right ) < getHeight ( node . right . left ) ) { // Double rotate binary tree node: first right child with its left child; then the node with new right child. node . right = rotateLeft ( node . right ) ; } return rotateRight ( node ) ; } else { // No rotation needed, just update current node's height, as an update may have changed it. node . height = calculateHeight ( getHeight ( node . left ) , getHeight ( node . right ) ) ; return node ; } }
Rebalances the subtree with given root node if necessary .