Package algs35

Class SET<K extends Comparable<? super K>>

java.lang.Object
algs35.SET<K>
All Implemented Interfaces:
Iterable<K>

public class SET<K extends Comparable<? super K>> extends Object implements Iterable<K>
The SET class represents an ordered set. It assumes that the elements are Comparable. It supports the usual add, contains, and delete methods. It also provides ordered methods for finding the minimum, maximum, floor, and ceiling.

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

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

  • Constructor Summary

    Constructors
    Constructor
    Description
    SET()
    Create an empty set.
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(K key)
    Add the key to this set.
    ceil(K k)
    Return the smallest key in this set >= k.
    boolean
    contains(K key)
    Does this set contain the given key?
    void
    delete(K key)
    Delete the given key from this set.
    boolean
    Does this SET equal that set.
    floor(K k)
    Return the largest key in this set <= k.
    int
     
    intersects(SET<K> that)
    Return the intersection of this set with that set.
    boolean
    Is this set empty?
    Return an Iterator for this set.
    static void
    main(String[] args)
     
    max()
    Return the key in this set with the maximum value.
    min()
    Return the key in this set with the minimum value.
    int
    Return the number of keys in this set.
    String represenation of this set.
    union(SET<K> that)
    Return the union of this set with that set.

    Methods inherited from class java.lang.Object

    getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator
  • Constructor Details

    • SET

      public SET()
      Create an empty set.
  • Method Details

    • isEmpty

      public boolean isEmpty()
      Is this set empty?
    • add

      public void add(K key)
      Add the key to this set.
    • contains

      public boolean contains(K key)
      Does this set contain the given key?
    • delete

      public void delete(K key)
      Delete the given key from this set.
    • size

      public int size()
      Return the number of keys in this set.
    • iterator

      public Iterator<K> iterator()
      Return an Iterator for this set.
      Specified by:
      iterator in interface Iterable<K extends Comparable<? super K>>
    • max

      public K max()
      Return the key in this set with the maximum value.
    • min

      public K min()
      Return the key in this set with the minimum value.
    • ceil

      public K ceil(K k)
      Return the smallest key in this set >= k.
    • floor

      public K floor(K k)
      Return the largest key in this set <= k.
    • union

      public SET<K> union(SET<K> that)
      Return the union of this set with that set.
    • intersects

      public SET<K> intersects(SET<K> that)
      Return the intersection of this set with that set.
    • equals

      public boolean equals(Object y)
      Does this SET equal that set.
      Overrides:
      equals in class Object
    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object
    • toString

      public String toString()
      String represenation of this set.
      Overrides:
      toString in class Object
    • main

      public static void main(String[] args)