Java Collections – TreeSet Example – Developers Corner

A Red-Black tree based TreeMap implementation. The TreeSet is sorted according to the natural ordering, or by a Comparator provided at TreeSet creation time, depending on which constructor is used. In my example, we will be ordering the collection using the compareTo() method in Car class.

Big-O Notation

According to the Javadocs, this implementation provides guaranteed O(log n) time cost for the get, add and remove operations.

Creating a TreeSet

This was the old-way prior to Generics.

Set cars = new TreeSet();

Generics

If you look closely, you will notice that I am using Generics to limit the type to String for the Key, and Integer for the Value in the Map. Generics add stability to your code, by having the computer detect type incompatibilities during compile-time. These runtime bugs would be more difficult to debug if left unchecked.

Set<Car> cars = new TreeSet<Car>();

Adding elements

Adding elements to the car Set is done by using the add(Object obj) method.

Auto-Boxing and Unboxing

Autoboxing is the automatic conversion that the Java compiler makes between the primitive types and their corresponding object wrapper classes. For example, converting an int to an Integer and vice-versa without the need to cast. In this case, Java is performing the boxing when we put elements into the set (converting int to Integer wrapper class) and unboxing when we get() elements from the Set (converting Integer to int primitive). In our example, we are using the Car class.

System.out.println("nAdding 4 elements to cars TreeSet()...");
cars.add(prius);
cars.add(pinto);
cars.add(taurus);
cars.add(maxima);

Removing elements

You may remove elements by calling the remove(Object obj) method.

cars.remove(taurus);
cars.remove(camarro);

Size of Collection

Returning the number of elements in a HashMap is as easy as calling the size() method.

cars.size();

Iterating through the Collection

Java 1.5 and above provides a foreach loop, which makes it much easier to iterate over the entire collection. This is my preferred way of doing it.

// Loop through the collection of cars using foreach
for (Car c : cars) {
   System.out.format("%s (%s)n", c.getName(), c.getManufacturer());
}

Iterating through the Collection

// Loop through the collection of cars using iterator
Iterator<Car> iter = cars.iterator();
while (iter.hasNext()) {
  Car c = iter.next();
  System.out.format("%s (%s)n", c.getName(), c.getManufacturer());
}

Implementing Comparable interface

Since we are using the Car class, we needed modify it to implement Comparable interface in order for it to work in the TreeSet class. We therefore also needed to override the compareTo(Object obj). See following changes below.

public class Car implements Comparable<Car> {
  ...
  ...

  @Override
  public int compareTo(Car car) {
    return name.compareTo(car.getName());
  }
}

Full Program Listing

package com.avaldes.tutorials;

import java.util.Iterator;
import java.util.TreeSet;

public class TreeSetExample {

  public static void main(String[] args) {
    Set<Car> cars = new TreeSet<Car>(); 
    System.out.println("Initial cars size: " + cars.size()); 
    
    Car prius = new Car("Toyota", "Prius");
    Car pinto = new Car("Ford", "Pinto");
    Car taurus = new Car("Ford", "Taurus");
    Car maxima = new Car("Nissan", "Maxima");
    Car towncar= new Car("Lincoln", "Town Car");
    Car camaro = new Car("Chevrolet", "Carmaro");
    Car etzel = new Car("Ford", "Etzel");
    Car carrera = new Car("Porsche", "Carrera");
    Car grandprix = new Car("Pontiac", "Grand Prix");
    Car pilot = new Car("Honda", "Pilot");
    
    System.out.println("nAdding 4 elements to cars TreeSet()...");
    cars.add(prius);
    cars.add(pinto);
    cars.add(taurus);
    cars.add(maxima);
    
    System.out.println("Check #1 cars size: " + cars.size()); 
    
    System.out.println("nAdding 2 more elements to cars TreeSet()...");
    cars.add(towncar);
    cars.add(camaro);

    System.out.println("Check #2 cars size: " + cars.size()); 

    System.out.println("nAdding 4 more elements to cars TreeSet()...");
    cars.add(etzel);
    cars.add(carrera);
    cars.add(grandprix);
    cars.add(pilot);
    System.out.println("Check #3 cars size: " + cars.size());
    
    System.out.println("nRemove etzel and pinto from cars TreeSet()");
    cars.remove(etzel);
    cars.remove(pinto);

    System.out.println("Check #4 cars size: " + cars.size()); 
    
    System.out.println("nDisplaying the full list of cars...");
    for (Car c : cars) {
      System.out.format("%s (%s)n", c.getName(), c.getManufacturer());
    }
  }
}

Full Program Listing (Car.java)

package com.avaldes.tutorials;

public class Car implements Comparable<Car> {
  private String Manufacturer;
  private String name;
  
  public Car(String manufacturer, String name) {
    setManufacturer(manufacturer);
    setName(name);
  }

  public String getManufacturer() {
    return Manufacturer;
  }

  public void setManufacturer(String manufacturer) {
    Manufacturer = manufacturer;
  }

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  @Override
  public int compareTo(Car car) {
    return name.compareTo(car.getName());
  }
}

Output

Initial cars size: 0

Adding 4 elements to cars TreeSet()...
Check #1 cars size: 4

Adding 2 more elements to cars TreeSet()...
Check #2 cars size: 6

Adding 4 more elements to cars TreeSet()...
Check #3 cars size: 10

Remove etzel and pinto from cars TreeSet()
Check #4 cars size: 8

Displaying the full list of cars...
Carmaro (Chevrolet)
Carrera (Porsche)
Grand Prix (Pontiac)
Maxima (Nissan)
Pilot (Honda)
Prius (Toyota)
Taurus (Ford)
Town Car (Lincoln)