Package com.zybooks.dsaj.searchtree

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

  • Constructor Details

    • RBTreeMap

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

    • RBTreeMap

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

    • 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