Package com.zybooks.dsaj.searchtree

Class TreeMap<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>
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>
Direct Known Subclasses:
AVLTreeMap, RBTreeMap, SplayTreeMap
public class TreeMap<K,V> extends AbstractSortedMap<K,V>
An implementation of a sorted map using a binary search tree.

  • Field Details

  • Constructor Details

    • TreeMap

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

    • TreeMap

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

    • size

      public int size()
      Returns the number of entries in the map.
      Returns:
      number of entries in the map

    • root

      protected Position<Entry<K,V>> root()

    • parent

      protected Position<Entry<K,V>> parent(Position<Entry<K,V>> p)

    • left

      protected Position<Entry<K,V>> left(Position<Entry<K,V>> p)

    • right

      protected Position<Entry<K,V>> right(Position<Entry<K,V>> p)

    • sibling

      protected Position<Entry<K,V>> sibling(Position<Entry<K,V>> p)

    • isRoot

      protected boolean isRoot(Position<Entry<K,V>> p)

    • isExternal

      protected boolean isExternal(Position<Entry<K,V>> p)

    • isInternal

      protected boolean isInternal(Position<Entry<K,V>> p)

    • set

      protected void set(Position<Entry<K,V>> p, Entry<K,V> e)

    • rotate

      protected void rotate(Position<Entry<K,V>> p)

    • restructure

      protected Position<Entry<K,V>> restructure(Position<Entry<K,V>> x)

    • treeMin

      protected Position<Entry<K,V>> treeMin(Position<Entry<K,V>> p)
      Returns position with the minimal key in the subtree rooted at Position p.
      Parameters:
      p - a Position of the tree serving as root of a subtree
      Returns:
      Position with minimal key in subtree

    • treeMax

      protected Position<Entry<K,V>> treeMax(Position<Entry<K,V>> p)
      Returns the position with the maximum key in the subtree rooted at p.
      Parameters:
      p - a Position of the tree serving as root of a subtree
      Returns:
      Position with maximum key in subtree

    • oneSidedAncestor

      protected Entry<K,V> oneSidedAncestor(Position<Entry<K,V>> p, boolean smaller)
      Returns entry of p's nearest ancestor with key that is smaller/larger than p. Returns null if no such ancestor exists.

    • get

      public V get(K key)
      Returns the value associated with the specified key, or null if no such entry exists.
      Parameters:
      key - the key whose associated value is to be returned
      Returns:
      the associated value, or null if no such entry exists

    • put

      public V put(K key, V value)
      Associates the given value with the given key. If an entry with the key was already in the map, this replaces the previous value with the new one and returns the old value. Otherwise, a new entry is added and null is returned.
      Parameters:
      key - key with which the specified value is to be associated
      value - value to be associated with the specified key
      Returns:
      the previous value associated with the key (or null, if no such entry)

    • remove

      public V remove(K key)
      Removes the entry with the specified key, if present, and returns its associated value. Otherwise does nothing and returns null.
      Parameters:
      key - the key whose entry is to be removed from the map
      Returns:
      the previous value associated with the removed key, or null if no such entry exists

    • firstEntry

      public Entry<K,V> firstEntry()
      Returns the entry having the least key (or null if map is empty).
      Returns:
      entry with least key (or null if map is empty)

    • lastEntry

      public Entry<K,V> lastEntry()
      Returns the entry having the greatest key (or null if map is empty).
      Returns:
      entry with greatest key (or null if map is empty)

    • ceilingEntry

      public Entry<K,V> ceilingEntry(K key)
      Returns the entry with least key greater than or equal to given key (or null if no such key exists).
      Parameters:
      key - the target key
      Returns:
      entry with least key greater than or equal to given (or null if no such entry)

    • floorEntry

      public Entry<K,V> floorEntry(K key)
      Returns the entry with greatest key less than or equal to given key (or null if no such key exists).
      Parameters:
      key - the target key
      Returns:
      entry with greatest key less than or equal to given (or null if no such entry)

    • lowerEntry

      public Entry<K,V> lowerEntry(K key)
      Returns the entry with greatest key strictly less than given key (or null if no such key exists).
      Parameters:
      key - the target key
      Returns:
      entry with greatest key strictly less than given (or null if no such entry)

    • higherEntry

      public Entry<K,V> higherEntry(K key)
      Returns the entry with least key strictly greater than given key (or null if no such key exists).
      Parameters:
      key - the target key
      Returns:
      entry with least key strictly greater than given (or null if no such entry)

    • entrySet

      public Iterable<Entry<K,V>> entrySet()
      Returns an iterable collection of all key-value entries of the map.
      Returns:
      iterable collection of the map's entries

    • subMap

      public Iterable<Entry<K,V>> subMap(K fromKey, K toKey)
      Returns an iterable containing all entries with keys in the range from fromKey inclusive to toKey exclusive.
      Parameters:
      fromKey - the lowest key allowed in the desired range
      toKey - the highest key allowed in the desired range
      Returns:
      iterable with keys in desired range

    • rebalanceInsert

      protected void rebalanceInsert(Position<Entry<K,V>> p)
      Rebalances the tree after an insertion of specified position. This version of the method does not do anything, but it can be overridden by subclasses.
      Parameters:
      p - the position which was recently inserted

    • rebalanceDelete

      protected void rebalanceDelete(Position<Entry<K,V>> p)
      Rebalances the tree after a child of specified position has been removed. This version of the method does not do anything, but it can be overridden by subclasses.
      Parameters:
      p - the position of the sibling of the removed leaf

    • rebalanceAccess

      protected void rebalanceAccess(Position<Entry<K,V>> p)
      Rebalances the tree after an access of specified position. This version of the method does not do anything, but it can be overridden by a subclasses.
      Parameters:
      p - the Position which was recently accessed (possibly a leaf)

    • dump

      protected void dump()
      Prints textual representation of tree structure (for debug purpose only).