In our AVL implementation, each node stores the height of its subtree, which is an arbitrarily large integer. The space usage for an AVL tree can be reduced by instead storing the balance factor of a node, which is defined as the height of its left subtree minus the height of its right subtree. Thus, the balance factor of a node is always equal to ?1, 0, or 1, except during an insertion or removal, when it may become temporarily equal to ?2 or +2. Reimplement the AVLTreeMap class storing balance factors rather than subtree heights.

1*An implementation of a sorted map using an AVL tree. * 2 public class AVLTreeMap extends TreeMap 3 Constructs an empty map using the natural ordering of keys. 4 public AVLTreeMapsuper) 5 * Constructs an empty map using the given comparator to order keys./ 6 public AVLTreeMap(ComparatorK> comp) { super(comp); } 7Returns the height of the given tree position. 8 protected int height(Position>p) f 9return tree.getAux(p); 10 1 Recomputes the height of the given position based on its children's heights./ 12 protected void recomputeHeight(Position> p) { 13 e.setAux(p, 1 Math.max(height(left(p)), height(right(p)))); 15 Returns whether a position has balance factor between -1 and 1 inclusive. 16 protected boolean isBalanced(Position>p) { 17 return Math.abs(height(left(p)) - height(right(p))) extends TreeMap 3 Constructs an empty map using the natural ordering of keys. 4 public AVLTreeMapsuper) 5 * Constructs an empty map using the given comparator to order keys./ 6 public AVLTreeMap(ComparatorK> comp) { super(comp); } 7Returns the height of the given tree position. 8 protected int height(Position>p) f 9return tree.getAux(p); 10 1 Recomputes the height of the given position based on its children's heights./ 12 protected void recomputeHeight(Position> p) { 13 e.setAux(p, 1 Math.max(height(left(p)), height(right(p)))); 15 Returns whether a position has balance factor between -1 and 1 inclusive. 16 protected boolean isBalanced(Position>p) { 17 return Math.abs(height(left(p)) - height(right(p)))