TreeSet

Java.util.TreeSet Example

In this example we will see how and when to use java.util.TreeSet. A TreeSet is a set implementation which provides total ordering on its elements. The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time.

A TreeSet is typically used when we want to keep the elements sorted all times. A TreeSet is a NavigableSet implementation based on a TreeMap. A TreeMap has Red-Black tree implemented which insures log(n) time cost for the basic operations (add, remove and contains).

Lets see how we can use TreeSet in different ways :

1. Sorting Order for Primitives (with Wrapper class)

TreeSet guarantees that the elements inserted remains sorted, lets try to insert some Integers and see the result.

JavaTreeSetExample.java

package com.jcg.example;

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

public class JavaTreeSetExample {

	public static void main(String[] args) {
		
		//Putting Integers in sorted order
		
		Set integerSet = new TreeSet();
		integerSet.add(new Integer(17));
		integerSet.add(new Integer(1));
		integerSet.add(new Integer(4));
		integerSet.add(new Integer(9));
		
		System.out.println(integerSet.toString());
		
	}
}

Output :

[1, 4, 9, 17]

2. Natural order of Custom classes using Comparable

Now lets see how we can ensure order of custom classes using Comparable. For this example we will use a User class and implement Comparable.

User.java

package com.jcg.example;

public class User implements Comparable {

	private String firstName;
	private String lastName;
	private int salary;

	public User(String firstName, String lastName, int salary) {
		super();
		this.firstName = firstName;
		this.lastName = lastName;
		this.salary = salary;
	}

	public String getFirstName() {
		return firstName;
	}

	public void setFirstName(String firstName) {
		this.firstName = firstName;
	}

	public String getLastName() {
		return lastName;
	}

	public void setLastName(String lastName) {
		this.lastName = lastName;
	}

	public int getSalary() {
		return salary;
	}

	public void setSalary(int salary) {
		this.salary = salary;
	}

	@Override
	public String toString() {
		return firstName + " " + lastName + " " + salary;
	}

	@Override
	public int compareTo(User o) {
		return this.firstName.compareTo(o.firstName);
	}
}

Here we have overridden compareTo method which sorts the users based on first name. Lets see how this will work :

JavaTreeSetExample.java

package com.jcg.example;

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

public class JavaTreeSetExample {

	public static void main(String[] args) {
		
		//Putting Custom Objects in Sorted Order
		Set userSet = new TreeSet();	
		populateUser(userSet);
		
		System.out.println("** Users based on first Name **");
		System.out.println(userSet.toString());
		
		//Iterating over TreeSet using for loop
		System.out.println("** Iterating using for loop **");
		for(User user : userSet){
			System.out.println(user.getFirstName());
		}
		
		
		//Iterating over TreeSet using Iterator
		System.out.println("** Iterating using Iterator **");
		Iterator iterator = userSet.iterator();
		while(iterator.hasNext()){
			System.out.println(iterator.next());
		}
		
	}

	private static void populateUser(Set userSet) {
		userSet.add(new User("Anirudh","Bhatnagar",100));
		userSet.add(new User("Jack","Daniel",150));
		userSet.add(new User("Kate","Xyz",120));
		userSet.add(new User("Bosco","Ceasor",140));
	}
}

Output:


** Users based on first Name **
[Anirudh Bhatnagar 100, Bosco Ceasor 140, Jack Daniel 150, Kate Xyz 120]
** Iterating using for loop **
Anirudh
Bosco
Jack
Kate
** Iterating using Iterator **
Anirudh Bhatnagar 100
Bosco Ceasor 140
Jack Daniel 150
Kate Xyz 120

So, In the above example we can see that the users are sorted based on the first name.
Also, we can see different ways of iterating over TreeSet in the same example above. (For loop and Iterator)

3. Sorting Order Using Comparator

Finally, we will see how we can use a Comparator with TreeSet to achieve ordering based on a criteria other than natural sorting. In our example we will create a comparator that sorts the TreeSet based on the salaries of users.

First, we will make a comparator :

UserSalaryComparator.java

package com.jcg.example;

import java.util.Comparator;

public class UserSalaryComparator implements Comparator {

	// This compares employees based on salaries
	@Override
	public int compare(User o1, User o2) {
		if (o1.getSalary() >= o2.getSalary()) {
			return 1;
		} else {
			return -1;
		}
	}

}

Next, We will pass this Comparator as an argument while creating the TreeSet to apply this Comparator.

JavaTreeSetExample.java

package com.jcg.example;

import java.util.Set;
import java.util.TreeSet;

public class JavaTreeSetExample {

	public static void main(String[] args) {
	
		Set userSetBasedOnSalary = new TreeSet(new UserSalaryComparator());
		populateUser(userSetBasedOnSalary);
		System.out.println("** Users based on salary **");
		System.out.println(userSetBasedOnSalary.toString());
		
	}

	private static void populateUser(Set userSet) {
		userSet.add(new User("Anirudh","Bhatnagar",100));
		userSet.add(new User("Jack","Daniel",150));
		userSet.add(new User("Kate","Xyz",120));
		userSet.add(new User("Bosco","Ceasor",140));
	}
}

Output :

** Users based on salary **
[Anirudh Bhatnagar 100, Kate Xyz 120, Bosco Ceasor 140, Jack Daniel 150]

So, here we see the output is sorted in increasing order of salaries of users.

Download the Eclipse project of this tutorial

In this example we saw how to use a TreeSet in different ways.

Download
You can download the full source code of this example here : JavaTreeSetExample.zip

Anirudh Bhatnagar

Anirudh is a Java programmer with extensive experience in building Java/J2EE applications. He has always been fascinated by the new technologies and emerging trends in software development. He has been involved in propagating these changes and new technologies in his projects. He is an avid blogger and agile enthusiast who believes in writing clean and well tested code.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Back to top button