Treeset in java

Today we are going to learn treeset in java.

  • TreeSet class underlying data structure is Balanced Tree.
  • TreeSet 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. RuntimeException 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 are 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


Methods supported by treeset

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 constructor

  • TreeSet t = new TreeSet();

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


  • TreeSet t = new TreeSet(Comparator comp);

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 col);

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 program on treeset,

import java.util.TreeSet;

public class TreesetExample 
{
   public static void main(String[] args) 
   {
      TreeSet<String> ts = new TreeSet<String>();
      // add() method is used to add elements in TreeSet 
      ts.add("Cheteshwar"); 
      ts.add("Ajinkya"); 
      ts.add("Bhuvaneshwar");
      // TreeSet do not allow duplicate elements 
      ts.add("Cheteshwar");
      // here TreeSet elements gets stored 
      // in default natural sorting order 
      System.out.println(ts);
   }
}

Output:

[Ajinkya, Bhuvaneshwar, Cheteshwar]


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.
import java.util.TreeSet;

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

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