TreeSet in java

Let’s learn treeset in java.

TreeSet in java

  • TreeSet underlying data structure is Balanced Tree.
  • TreeSet implementation in java: TreeSet implements NavigableSet interface by inheriting AbsractSet class.
  • In Treeset duplicate values are not allowed. Because TreeSet implements SortedSet interface.
  • Treeset does not allow to insert heterogeneous objects. Runtime exception ClassCastException is thrown, if we try to add heterogeneous objects.
  • Treeset will not allow null value.
  • Treeset objects are sorted and stored in ascending order. Insertion order is not preserved.
  • Ordering (natural ordering) of elements in TreeSet is maintained by Set whether or not Comparator is provided explicitly.
  • Treeset is excellent choice for storing large amounts of data. It has faster retrieval and access time.

How to sort treeset in java

Let’s learn how to sort treeset in java. Here’s how to sort TreeSet in descending order in java.

import java.util.TreeSet;
public class TreeSetExample 
{
   public static void main(String[] args) 
   {
      TreeSet<Object> number = new TreeSet<Object>(); 
      number.add(1); 
      number.add(24); 
      number.add(15); 
      number.add(6); 
      number.add(9); 
      number.add(2);
      // reverse order using descendingSet()
      TreeSet<Object> reverseOrder = (TreeSet<Object>)number.descendingSet();
      // printing set 
      System.out.println("Without using descendingSet() method: " + number); 
      System.out.println("Using descendingSet() method: " + reverseOrder);
   }
}


Output:

Without using descendingSet() method: [1, 2, 6, 9, 15, 24]
Using descendingSet() method: [24, 15, 9, 6, 2, 1]


Also read – treemap in java


Here’s treeset hierarchy.

treeset in java

Treeset methods

MethodDescription
boolean add(E e)adds the specified element to this set if it is not already present.
boolean addAll(Collection<? extends E> c)adds all of the elements in the specified collection to this set.
E ceiling(E e)returns least element in this set greater than or equal to the given element or null if there is no such element.
void clear()removes all the elements form this set.
Iterator<E> descendingIterator()returns an iterator over the elements in this set in descending order.
NavigableSet<E> descendingSet()returns a reverse order view of the elements contained in this set.
Object clone()returns a shallow copy of this TreeSet instance.
boolean contains(Object o)returns true if this set contains the specified element.
SortedSet<E> headSet(E toElement)returns a view of the portion of this set whose elements are strictly less than toElement.
NavigableSet<E> headSet(E toElement, boolean inclusive)returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement.
E first()returns the first (lowest) element currently in this set.
E floor(E e)returns the greatest element in this set less than or equal to the given element or null if there is no such element.
Comparator<? super E> comparator()returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.
E higher(E e)returns the least element in this set strictly greater than the given element or null if there is no such element.
boolean isEmpty()returns true if this set contains no elements.
Iterator<E> iterator()returns an iterator over the elements in this set in ascending order.
E last()returns the last (highest) element currently in this set.
E lower(E e)returns the greatest element in this set strictly less than the given element or null if there is no such element.
E pollFirst()retrieves and removes the first (lowest) element or returns null if this set is empty.
E pollLast()retrieves and removes the last (highest) element or returns null if this set is empty.
boolean remove(Object o)removes the specified element from this set if it is present.
int size()returns the number of elements in this set (its cardinality).
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)returns a view of the portion of this set whose elements range from fromElement to toElement.
SortedSet<E> subSet(E fromElement, E toElement)returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
SortedSet<E> tailSet(E fromElement)returns a view of the portion of this set whose elements are greater than or equal to fromElement.
NavigableSet<E> tailSet(E fromElement, boolean inclusive)returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement.

Treeset constructors

TreeSet t = new TreeSet();

This constructor creates an empty TreeSet object where elements will be inserted according to default natural sorting order.

TreeSet t = new TreeSet(Comparator c);

This constructor creates an empty treeset object where elements will be inserted according to customized sorting order described by Comparator object.

TreeSet t = new TreeSet(Collection c);

This constructor creates an empty treeset object where we can pass any Collection object and it will create an equivalent treeset object is created.

TreeSet t = new TreeSet(SortedSet s);

For given SortedSet object we can create an equivalent treeset object.


Here’s java treeset example.

import java.util.Iterator;
import java.util.TreeSet;
public class TreeSetExamples
{
   public static void main(String[] args)
   {
      TreeSet<String> ts = new TreeSet<String>();
      ts.add("red");
      ts.add("blue");
      ts.add("green");
      ts.add("red");
      Iterator<String> iterate = ts.iterator();
      while(iterate.hasNext())
      {
         System.out.println(iterate.next());
      }
   }
}


Output:

blue
green
red


NOTE:

  • Do not insert null value into TreeSet. Because it throws NullPointerException.
  • Elements entered in TreeSet should be homogeneous and comparable. If not RuntimeException:ClassCastException is thrown.
  • An object is comparable only if a class implements Comparable interface.

Now let’s see a class implementing specific comparator.

import java.util.Comparator;
import java.util.TreeSet;
class ComparatorDemo implements Comparator<String>
{
   public int compare(String str1, String str2) 
   { 
      String strFirst; 
      String strSecond; 
      strFirst = str1; 
      strSecond = str2; 
      return strSecond.compareTo(strFirst); 
   }
}
public class TreeSetComparableExample 
{
   public static void main(String[] args) 
   {
      TreeSet<String> ts = new TreeSet<String>(new ComparatorDemo());   
      ts.add("Grapefruit");
      ts.add("Eggfruit"); 
      ts.add("Apple"); 
      ts.add("Mango"); 
      ts.add("Papaya"); 
      ts.add("42"); 
      System.out.println("TreeSet before using comparator: " + ts);
      System.out.println("Sorted in descending order: "); 
      for(String str : ts)
      {
         System.out.print(str + ", ");
      }
   }
}


Output:

TreeSet before using comparator: [Papaya, Mango, Grapefruit, Eggfruit, Apple, 42]
Sorted in descending order: Papaya, Mango, Grapefruit, Eggfruit, Apple, 42,


treeset vs hashset or difference between hashset and treeset in java

Here’s hashset and treeset difference in java.

HashSetTreeSet
stores object in random order.sorted according to natural order. If not use compareTo() method.
uses equals() method for comparison.uses compareTo() method for ordering.
backed by hashmap.backed by Navigable TreeMap.
hashset is better and faster.a bit slower.
gives constant time performance.TreeSet guarantees log(n) time cost

treeset vs hashset example:

// hashset example
import java.util.HashSet;
public class HashSetExample
{
   public static void main(String[] args)
   {
      HashSet<String> hs = new HashSet<String>();
      hs.add("hello");
      hs.add("world");
      hs.add("core");
      hs.add("java");
      // duplicate elements are removed
      hs.add("hello");
      // printing HashSet elements
      System.out.println("HashSet elements: ");
      for(String str : hs)
      {
         System.out.println(str);
      }
   }
}


Output:

HashSet elements:
core
world
java
hello


// treeset example
import java.util.TreeSet;
public class TreeSetDemo
{
   public static void main(String[] args)
   {
      TreeSet<String> ts = new TreeSet<String>();
      ts.add("hello");
      ts.add("world");
      ts.add("core");
      ts.add("java");
      // duplicate elements are removed
      ts.add("hello");
      // printing TreeSet elements
      System.out.println("TreeSet elements: ");
      for(String str : ts)
      {
         System.out.println(str);
      }
   }
}


Output:

TreeSet elements:
core
hello
java
world


when to use treeset in java

Let’s learn when to use treeset in java.

  • use TreeSet when requirement is sorted unique elements. Since TreeSet elements are always in ascending order.
  • use TreeSet if there are two entries in nearby order. Because TreeSet has higher locality which places entries close to each other in data structure and in memory.
  • use TreeSet when you want to perform read/write operations frequently. Because treeset uses red-black tree algorithm.

Reference – Oracle help centre