Package com.zybooks.dsaj.searchtree

Class AVLTreeMap<K,V>

java.lang.Object
com.zybooks.dsaj.map.AbstractMap<K,V>
com.zybooks.dsaj.map.AbstractSortedMap<K,V>
com.zybooks.dsaj.searchtree.TreeMap<K,V>
com.zybooks.dsaj.searchtree.AVLTreeMap<K,V>
Type Parameters:
K - The key type (keys must be unique and comparable)
V - The value type
All Implemented Interfaces:
Map<K,V>, SortedMap<K,V>
public class AVLTreeMap<K,V> extends TreeMap<K,V>
An implementation of a sorted map using an AVL tree.

  • Constructor Details

    • AVLTreeMap

      public AVLTreeMap()
      Constructs an empty map using the natural ordering of keys.

    • AVLTreeMap

      public AVLTreeMap(Comparator<K> comp)
      Constructs an empty map using the given comparator to order keys.
      Parameters:
      comp - comparator defining the order of keys in the map

  • Method Details

    • height

      protected int height(Position<Entry<K,V>> p)
      Returns the height of the given tree position.

    • recomputeHeight

      protected void recomputeHeight(Position<Entry<K,V>> p)
      Recomputes the height of the given position based on its children's heights.

    • isBalanced

      protected boolean isBalanced(Position<Entry<K,V>> p)
      Returns whether a position has balance factor between -1 and 1 inclusive.

    • tallerChild

      protected Position<Entry<K,V>> tallerChild(Position<Entry<K,V>> p)
      Returns a child of p with height no smaller than that of the other child.

    • rebalance

      protected void rebalance(Position<Entry<K,V>> p)
      Utility used to rebalance after an insert or removal operation. This traverses the path upward from p, performing a trinode restructuring when imbalance is found, continuing until balance is restored.

    • rebalanceInsert

      protected void rebalanceInsert(Position<Entry<K,V>> p)
      Overrides the TreeMap rebalancing hook that is called after an insertion.
      Overrides:
      rebalanceInsert in class TreeMap<K,V>
      Parameters:
      p - the position which was recently inserted

    • rebalanceDelete

      protected void rebalanceDelete(Position<Entry<K,V>> p)
      Overrides the TreeMap rebalancing hook that is called after a deletion.
      Overrides:
      rebalanceDelete in class TreeMap<K,V>
      Parameters:
      p - the position of the sibling of the removed leaf