Source of 28.11.java

Structures and functions

  1: // @author Frank M. Carrano, Timothy M. Henry
  2: // @version 5.0
  3: private BinaryNode<T> rebalance(BinaryNode<T> nodeN)
  4: {
  5:    int heightDifference = getHeightDifference(nodeN);

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

 31:    return nodeN;
 32: } // end rebalance