TreeSet in Java

A TreeSet is a data structure in Java , in which objects can be stored  in a specified order .The order depends on the Comparator or Comparable implementations.TreeSet implements from Set interface.Set avoids duplication of elements.This discussion gives an idea about TreeSet in Java

Let us discuss this topic with examples.

case1 :TreeSet in natural order(With String objects)

In this case we store  a number of String objects in a TreeSet object. String class already  implements the Comparable interface.If we put  the String objects in a TreeSet , by default the strings are in ascending order.

import java.util.Set;
import java.util.TreeSet;
public class TreeSetSample {
Set set = null;
public TreeSetSample() {
set = new TreeSet();
}
public void addItemsToSet() {
String[] listItems = {"dog", "cat", "cow", "elephant", "sheep"};
for (int i = 0; i < listItems.length; i++) {
set.add(listItems[i]);
}
}
public void displaySet() {
System.out.println("Displaying contents of set");
for (Object item : set) {
System.out.println("Item = " + item.toString());
}
}
public void removeItems() {
System.out.println("Removing contents of set");
set.remove("dog");
set.remove("cat");
set.remove("cow");
set.remove("elephant");
set.remove("sheep");
System.out.println("Contents removed ,now size of set = " + set.size());
}
public static void main(String[] args) {
TreeSetSample sample = new TreeSetSample();
sample.addItemsToSet();
sample.displaySet();
sample.removeItems();
}
}

In this case items are adding to TreeSet in the order ‘dog’ then ‘cat’ then ‘cow’ then ‘elephant’ and  then ‘sheep’  in our program. In case of TreeSet   , if we are reading the Set , these items are getting in an ascending order.Let us verify the output.

Output

Displaying contents of set

Item = cat

Item = cow

Item = dog

Item = elephant

Item = sheep

Removing contents of set

Contents removed  ,now size of set = 0

So items were sorted.This makes our understanding clear.So by default a TreeSet arranges items in an ascending order .

Case 2:TreeSet in descending order(With String objects)

For getting a TreeSet with a  descending order , we should have a Comparator instance. The compare() method in Comparator instance should   do the comparison to make the order as descending.Then the Comparator instance must pass as an argument while initializing TreeSet object.

In the example given below , we are using String objects to store in TreeSet.And we  are trying to get all these strings sorted in descending order.Now let us see the Comparator implementation first.

import java.util.Comparator;
public class SetComparator implements Comparator {
public int compare(Object firstObject, Object secondObject) {
String first = (String) firstObject;
String second = (String) secondObject;
return second.compareTo(first);
}
}

Now let us see how items are adding , displaying and removing  from the TreeSet.

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;
public class TreeSetDesc {
private Set set = null;
private Comparator comparator = null;
public TreeSetDesc() {
comparator = new SetComparator();
set = new TreeSet(comparator);
}
public void addItemsToSet() {
String[] listItems = {"dog", "cat", "cow", "elephant", "sheep"};
for (int i = 0; i < listItems.length; i++) {
set.add(listItems[i]);
}
}
public void displaySet() {
System.out.println("Displaying contents of set");
for (Object item : set) {
System.out.println("Item = " + item.toString());
}
}
public void removeItems() {
System.out.println("Removing contents of set");
set.remove("dog");
set.remove("cat");
set.remove("cow");
set.remove("elephant");
set.remove("sheep");
System.out.println("Contents removed ,now size of set = " + set.size());
}
public static void main(String[] args) {
TreeSetDesc sample = new TreeSetDesc();
sample.addItemsToSet();
sample.displaySet();
sample.removeItems();
}
}

It is important to note the TreeSet initialization here. In case 1, it was  set = new TreeSet() . In case 2 , we changed it to  set = new TreeSet(comparator) . So the Comparator instance is making the difference.While adding an item to our set instance , comparison takes place and items get arranged in specific way. Now let us verify our output.

Output

Displaying contents of set

Item = sheep

Item = elephant

Item = dog

Item = cow

Item = cat

Removing contents of set

Contents removed  ,now size of set = 0

See the difference between case1 and case2 . The compare() method of SetComparator plays the comparison role here. Please  note the return statement in compare() method. If we change the statement to

return first.compareTo(second)

you can see the difference.

Summary

If we are using objects of String , Integer,Double  etc and we are not using any Comparator instance while initializing Treeset , then the objects will be stored in ascending order.If we use Comparator instance , then we can change the order.By default,  classes like String , Integer ,Double etc are implementing Comparable interface.So the default compareTo() method in these classes  does the comparison to store in ascending order.

Storing objects of our own classes in Treeset

If we need   objects of our own classes to be stored in a TreeSet ,those classes should implement the Comparable interface or we should use a Comparator instance as argument while initializing the Treeset.Let us see an example.If we are not using a Comparator instance while initialization of TreeSet , then our class whose objects needs to be stored , should implement  Comparable interface .And the compareTo() method should do the comparaison.If we are passing a Comparator instance while initialization , then the comparison is doing in compare() method of Comparator.

a)Using Comparable

1)In ascending order

public class Employee implements Comparable {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String toString() {
return "Id = " + getId() + " Name = " + getName();
}
public int compareTo(Object object) {
Employee employee = (Employee) object;
int status = 0;
return getId() - employee.getId();
}
}

Now let us see how Employee objects are putting in a TreeSet and how they are displaying.

import java.util.Set;
import java.util.TreeSet;
public class Main {
private Set set = null;
public Main() {
set = new TreeSet();
}
public void addItemsToSet() {
Employee employee = new Employee(1, "BIJOY");
Employee employee1 = new Employee(2, "KARTHIK");
Employee employee2 = new Employee(3, "DEXTER");
Employee employee3 = new Employee(4, "JAYAN");
set.add(employee);
set.add(employee1);
set.add(employee2);
set.add(employee3);
}
public void displaySet() {
System.out.println("Displaying contents of set");
for (Object item : set) {
System.out.println(item.toString());
}
}
public static void main(String[] args) {
Main main = new Main();
main.addItemsToSet();
main.displaySet();
}
}

Now let us verify the output.

Output

Displaying contents of set

Id = 1 Name = BIJOY

Id = 2 Name = KARTHIK

Id = 3 Name = DEXTER

Id = 4 Name = JAYAN

2)In descending order

Now we are making the compareTo() method of Employee.java in such a way that it returns the reverse of the existing result . So the modified Employee.java becomes:

/**
* User: Bijoy
* Date: 1/3/13
* Time: 9:35 PM
*/
public class Employee implements Comparable {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String toString() {
return "Id = " + getId() + " Name = " + getName();
}
public int compareTo(Object object) {
Employee employee = (Employee) object;
int status = 0;
return employee.getId() - getId();
}
}

The only difference is in the compareTo()  method.Now compile and run the Main.java again.And see the output

Output

Displaying contents of set

Id = 4 Name = JAYAN

Id = 3 Name = DEXTER

Id = 2 Name = KARTHIK

Id = 1 Name = BIJOY

In our compareTo() method , we only compared the attribute id.So the objects were arranged in descending order of id.

b)Using Comparator instance

If we are using Comparator instance our class whose objects needs to be stored , need not implement Comparable. So the Employee.java can be modifies as:

public class Employee{
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String toString() {
return "Id = " + getId() + " ;Name = " + getName();
}
}

Now let us see the Main.java.Here , while creating the TreeSet instance we are giving Comparator instance as argument.

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;
public class Main {
private Set set = null;
public Main() {
set = new TreeSet(new Comparator() {
public int compare(Employee employee, Employee employee1) {
return employee.getId() - employee1.getId();
}
});
}
public void addItemsToSet() {
Employee employee = new Employee(1, "BIJOY");
Employee employee1 = new Employee(2, "KARTHIK");
Employee employee2 = new Employee(3, "DEXTER");
Employee employee3 = new Employee(4, "JAYAN");
set.add(employee);
set.add(employee1);
set.add(employee2);
set.add(employee3);
}
public void displaySet() {
System.out.println("Displaying contents of set");
for (Object item : set) {
System.out.println(item.toString());
}
}
public static void main(String[] args) {
Main main = new Main();
main.addItemsToSet();
main.displaySet();
}
}

This comparison sorts the Employee objects in ascending order.let us verify the output.

Output

Displaying contents of set

Id = 1 ;Name = BIJOY

Id = 2 ;Name = KARTHIK

Id = 3 ;Name = DEXTER

Id = 4 ;Name = JAYAN

Now  if we change the return statement in  compareTo() method  to

return employee1.getId() – employee.getId()

then the order is changing.You can verify the output.

In any case , if a comparison returns 0 , then the new member is not adding to the set. The existing structure remains the same.

See Related Discussions

Collections in Java

Comparable vs Comparator in Java

Hashset in Java