Package com.zybooks.dsaj.searchtree

Class SplayTreeMap<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.SplayTreeMap<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 SplayTreeMap<K,V> extends TreeMap<K,V>
An implementation of a sorted map using a splay tree.

  • Constructor Details

    • SplayTreeMap

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

    • SplayTreeMap

      public SplayTreeMap(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

    • rebalanceAccess

      protected void rebalanceAccess(Position<Entry<K,V>> p)
      Overrides the TreeMap rebalancing hook that is called after a node access.
      Overrides:
      rebalanceAccess in class TreeMap<K,V>
      Parameters:
      p - the Position which was recently accessed (possibly a leaf)

    • 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