Treeset in java

Let’s learn treeset in java.

Treeset in java

  • TreeSet class underlying data structure is Balanced Tree.
  • TreeSet java implements NavigableSet interface by inheriting AbsractSet class.
  • In Treeset class duplicate values are not allowed.
  • TreeSet class implements SortedSet interface.
  • Treeset class do not allow heterogeneous objects. Runtime exception ClassCastException is thrown, if there is any heterogeneous objects.
  • Treeset class allows only one null value.
  • Treeset class 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 class is best choice to store large amounts of data. It has faster retrieval and access time.
  • Operations like add, remove and search take O(log n) time and for sorting elements it takes O(n) time.

Here’s treeset hierarchy,

treeset in java

Treeset methods

MethodDescription
void add(Object o)method will add specified element according to some sorting order in TreeSet. Duplicate entries will not get added.
boolean addAll( Collection C)this method adds all the elements in the specified collection to this set. Elements in Collection should be homogeneous otherwise ClassCastException will be thrown. Duplicate Entries of Collection will not be added to TreeSet.
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.
Object clone( )returns a shallow copy of this treeset instance, which is just a simple copied set.
Object first()method will return first element in TreeSet If TreeSet is not null, else it will throw NoSuchElementException.
boolean contains( Object o )returns true if this set contains the specified element in TreeSet else it will return false.
Object last()method will return last element in TreeSet if TreeSet is not null, else it will throw NoSuchElementException.
SortedSet headSet(Object toElement)method will return elements of TreeSet which are less than the specified element.
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 comparator()method will return Comparator used to sort elements in TreeSet or it will return null if default natural sorting order is used.
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 or is empty and false for the opposite case.
Iterator 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 size of the set or the number of elements present in the set.
NavigableSet 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 subSet( Object fromElement, Object toElement )returns elements ranging from fromElement to toElement. fromElement is inclusive and toElement is exclusive.
SortedSet tailSet( Object fromElement )returns elements of TreeSet which are greater than or equal to the specified element.
NavigableSet 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 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.TreeSet;

public class TreeSetExample 
{
   public static void main(String[] args) 
   {
      TreeSet ts = new TreeSet();
      ts.add("Ajinkya");
      ts.add("ajay");
      ts.add("Bhuvaneshwar");
      ts.add("Zaheer");
      ts.add("Lance");
      // do not allow heterogeneous objects
      // ts.add(new Integer(99));
      // here NullPointerException is thrown
      // ts.add(null);
      System.out.println(ts);
   }
}



Output:

[Ajinkya, Bhuvaneshwar, Lance, Zaheer, ajay]


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.

ClassCastException in TreeSet

ClassCastException occurs when there is no default natural sorting order in TreeSet class, having heterogeneous objects and uncomparable with other objects.

Let’s demonstrate ClassCastException,

import java.util.TreeSet;

public class TreeSetDemo 
{
   public static void main(String[] args) 
   {
      TreeSet ts = new TreeSet();
      ts.add(new StringBuffer("Ajay")); 
      ts.add(new StringBuffer("Zaheer")); 
      ts.add(new StringBuffer("Laxman")); 
      ts.add(new StringBuffer("Bhuvaneshwar")); 
      ts.add(new StringBuffer("Ojha"));
      System.out.println(ts); // RunTimeException :ClassCastException 
      // StringBuffer does not implement Comparable interface
   }
}



Output:

Exception in thread “main” java.lang.ClassCastException: java.lang.StringBuffer cannot be cast to java.lang.Comparable
at java.util.TreeMap.compare(Unknown Source)
at java.util.TreeMap.put(Unknown Source)
at java.util.TreeSet.add(Unknown Source)
at TreeSetDemo.main(TreeSetDemo.java:8)


Also read – treemap in java

Reference – Oracle help centre