Package algs35

Class ST<K extends Comparable<? super K>,V>

java.lang.Object
algs35.ST<K,V>
All Implemented Interfaces:
Iterable<K>

public class ST<K extends Comparable<? super K>,V> extends Object implements Iterable<K>
This class represents an ordered symbol table. It assumes that the keys are Comparable. It supports the usual put, get, contains, and remove methods. It also provides ordered methods for finding the minimum, maximum, floor, and ceiling.

The class implements the associative array abstraction: when associating a value with a key that is already in the table, the convention is to replace the old value with the new value. The class also uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to removing the key.

This class implements the Iterable interface for compatiblity with the version from Introduction to Programming in Java: An Interdisciplinary Approach.

This implementation uses a balanced binary search tree. The put, contains, remove, minimum, maximum, ceiling, and floor methods take logarithmic time.

For additional documentation, see Section 4.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

  • Field Summary Link icon

    Fields
    Modifier and Type
    Field
    Description
    private final TreeMap<K,V>
     
  • Constructor Summary Link icon

    Constructors
    Constructor
    Description
    ST()
    Create an empty symbol table.
  • Method Summary Link icon

    Modifier and Type
    Method
    Description
    ceil(K k)
    Return the smallest key in the table >= k.
    boolean
    contains(K key)
    Is the key in the table?
    delete(K key)
    Delete the key (and paired value) from table.
    floor(K k)
    Return the largest key in the table <= k.
    get(K key)
    Return the value paired with given key; null if key is not in table.
    Return an Iterator for the keys in the table.
    Return an Iterable for the keys in the table.
    static void
    main(String[] args)
     
    max()
    Return the largest key in the table.
    min()
    Return the smallest key in the table.
    void
    put(K key, V val)
    Put key-value pair into the symbol table.
    int
    How many keys are in the table?

    Methods inherited from class java.lang.Object Link icon

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface java.lang.Iterable Link icon

    forEach, spliterator
  • Field Details Link icon

  • Constructor Details Link icon

    • ST Link icon

      public ST()
      Create an empty symbol table.
  • Method Details Link icon

    • put Link icon

      public void put(K key, V val)
      Put key-value pair into the symbol table. Remove key from table if value is null.
    • get Link icon

      public V get(K key)
      Return the value paired with given key; null if key is not in table.
    • delete Link icon

      public V delete(K key)
      Delete the key (and paired value) from table. Return the value paired with given key; null if key is not in table.
    • contains Link icon

      public boolean contains(K key)
      Is the key in the table?
    • size Link icon

      public int size()
      How many keys are in the table?
    • keys Link icon

      public Iterable<K> keys()
      Return an Iterable for the keys in the table. To iterate over all of the keys in the symbol table st, use the foreach notation: for (K key : st.keys()).
    • iterator Link icon

      public Iterator<K> iterator()
      Return an Iterator for the keys in the table. To iterate over all of the keys in the symbol table st, use the foreach notation: for (K key : st). This method is for backward compatibility with the version from Introduction to Programming in Java: An Interdisciplinary Approach.
      Specified by:
      iterator in interface Iterable<K extends Comparable<? super K>>
    • min Link icon

      public K min()
      Return the smallest key in the table.
    • max Link icon

      public K max()
      Return the largest key in the table.
    • ceil Link icon

      public K ceil(K k)
      Return the smallest key in the table >= k.
    • floor Link icon

      public K floor(K k)
      Return the largest key in the table <= k.
    • main Link icon

      public static void main(String[] args)