Source of 27.11.java

Structures and functions

  1: private BinaryNode<T> rebalance(BinaryNode<T> nodeN)
  2: {
  3:    int heightDifference = getHeightDifference(nodeN);
  4: 
  5:    if (heightDifference > 1)
  6:    {
  7:       // Left subtree is taller by more than 1,
  8:       // so addition was in left subtree
  9:       if (getHeightDifference(nodeN.getLeftChild()) > 0)
 10:          // Addition was in left subtree of left child
 11:          nodeN = rotateRight(nodeN);
 12:       else
 13:          // Addition was in right subtree of left child
 14:          nodeN = rotateLeftRight(nodeN);
 15:    }
 16:    else if (heightDifference < -1)
 17:    {
 18:       // Right subtree is taller by more than 1,
 19:       // so addition was in right subtree
 20:       if (getHeightDifference(nodeN.getRightChild()) < 0)
 21:          // Addition was in right subtree of right child
 22:          nodeN = rotateLeft(nodeN);
 23:       else
 24:          // Addition was in left subtree of right child
 25:          nodeN = rotateRightLeft(nodeN);
 26:    } // end if
 27:    // Else nodeN is balanced
 28: 
 29:    return nodeN;
 30: } // end rebalance
 31: // Version 4.0