Set and Map

The TreeSet class

The TreeSet class is a template class like the ArrayList class. A set acts as a container for a set of elements, and supports rapid searches via its contains() method. The key methods of the TreeSet<E> class are

boolean add(E item)
boolean contains(E item)
void remove(E item)

One important note about the add() method: if the set already contains an element equal to item, item is not added to the set, and add() returns false.

How a TreeSet works

A TreeSet stores its data in the form of a special structure called a binary search tree. A tree is a data structure composed of nodes, with each node being connected to other nodes, called child nodes. In a binary search tree, each node contains a data item, and the data items in parent nodes and child nodes obey a special ordering rule. If a parent node contains a particular data value, the left child of that parent (and all of the descendents of that left child) will contain smaller data values. Likewise, the right child and all of its descendents will contain larger data values.

Searching for items and inserting new items can both be implemented efficiently in binary search trees. To search for an item, we start at the top of the tree and compare the data value in that top node with the value we are searching for. That comparison will tell us where to look: if the item we are searching for is smaller than the data value, we know that the item we are searching for will be found in the left sub-tree. To insert a new item, we simply do a search for that item and let the search run until it falls off the end of the tree. At the point where the search exits the tree we attach a new node and place the data item in it.

Iterating over a TreeSet

Since a TreeSet is a container, it is natural to want to set up a loop to iterate over its contents. Unlike arrays or ArrayLists, the TreeSet class does not support array notation and does not have a get() method. Instead, the TreeSet class has an iterator() method that returns a special object called an iterator. The iterator class has hasNext() and next() methods that make it possible to iterate over the contents of the original TreeSet.

Here is an example to demonstrate how this works.

// Create a TreeSet to hold integers and fill it with
// some random integers
TreeSet<Integer> T = new TreeSet<Integer>();
Random rnd = new Random();
for(int n = 0;n < 100;n++)
  T.add(rnd.nextInt(1000)));

// Now use an iterator to print the list of integers
// stored in T
Iterator<Integer> I = T.iterator();
while(I.hasNext())
  System.out.println(I.next());

As an added bonus, the iterator will visit the items in T in sorted order, from smallest to largest.

The enhanced for loop

As an alternative to using an iterator, Java also offers a variant of the for loop, called an enhanced for loop that makes it easy to iterate over the elements in a TreeSet. Here is the last example rewritten with an enhanced for loop.

// Create a TreeSet to hold integers and fill it with
// some random integers
TreeSet<Integer> T = new TreeSet<Integer>();
Random rnd = new Random();
for(int n = 0;n < 100;n++)
  T.add(rnd.nextInt(1000));

// Now use an enhanced for loop to print the list of
// integers stored in T
for(Integer n : T)
  System.out.println(n);

Enhanced for loops can be used with ArrayLists and arrays, as well.

The TreeMap class

A TreeMap is a data structure that is used to store and retrieve data efficiently. Each item stored in a TreeMap is stored as a combination of a key and a value. Items are looked up by their keys.

Here are the main methods of the TreeMap<K,V> class.

V put(K key,V value)
boolean containsKey(K key)
V get(K key)

put() places a new key/value combination in the structure. If some other value was previously stored in the map under this key, put() will return that old value; otherwise, put will return null.

To iterate over the values stored in a map you use this syntax:

TreeMap<String,Integer> example = new TreeMap<String,Integer>();
example.add("one",1);
example.add("thirteen",13);

Iterator<Integer> iter = example.values().iterator();
while(iter.hasNext())
  System.out.println(iter.next());

Example programs

At the top of these notes you will find a button to download a NetBeans project containing some example code. This project contains three separate programs that demonstrate uses of some of the classes I have covered here. Here is an overview of what each of these programs do.

One of the example programs redoes the produce tracker example. A significant change this time around is in the Inventory class. The original version of the Inventory class used an ArrayList of Item objects. The find() and exists() methods had to do linear searches through the ArrayList. In this version of the program, we will replace the ArrayList with a TreeMap that maps item names to the Item objects. This will make finding things much easier.

Another example program updates the "are these lists of numbers the same" problem from a previous lab. For this version of the problem we will solve the problem by putting each of the lists of numbers into a TreeSet. By using the contains() method we can quickly search a set and see whether or not it contains a given number.

A final example program solves a completely new problem: given two lists of integers, find the numbers those lists have in common. Once again this solution takes advantage of the handy contains() method in the TreeSet class to quickly determine whether or not a given set contains a given number.

More information about the TreeSet and TreeMap classes

The home page for this course contains a link to the online documentation for the Java Class Library. If you click that link it will take you to the top level page for information about the core classes in the Java Class Library. There are a lot of classes in the class library, so the classes are organized into packages. The ArrayList, TreeSet, and TreeMap classes are located in the java.util package. Clicking on the link for java.util takes you to the information page for that package. There you will see a list of classes in the package. Clicking on the link for any one of those classes takes you to the documentation page for that class. The documentation page for each class contains a brief overview of the class and a list of the methods in the class. Clicking on the link for any one of the methods takes you to the documentation for that method.