Home java TreeSet in Java

Course Curriculum

TreeSet in Java
18 May

TreeSet in Java

|

java

|

TreeSet is one of the most important implementations of the SortedSet interface in Java that uses a Tree for storage. The ordering of the elements is maintained by a set using their natural ordering whether or not an explicit comparator is provided. This must be consistent with equals if it is to correctly implement the Set interface. It can also be ordered by a Comparator provided at set creation time, depending on which constructor is used. The TreeSet implements a NavigableSet interface by inheriting AbstractSet class.

Set-TreeSet-SortedSet-In-Java-Collection

In the above image, the navigable set extends the sorted set interface. Since a set doesn’t retain the insertion order, the navigable set interface provides the implementation to navigate through the Set. The class which implements the navigable set is a TreeSet which is an implementation of a self-balancing tree. Therefore, this interface provides us with a way to navigate through this tree.

Example: The following implementation demonstrates how to create and use a TreeSet.

// Java program to demonstrate TreeSet
import java.util.*;

class TreeSetExample {

public static void main(String[] args)
{
Set<String> ts1 = new TreeSet<>();

// Elements are added using add() method
ts1.add("A");
ts1.add("B");
ts1.add("C");

// Duplicates will not get insert
ts1.add("C");

// Elements get stored in default natural
// Sorting Order(Ascending)
System.out.println(ts1);
}
}
result:

[A, B, C]

Performing Various Operations on TreeSet
Let’s see how to perform a few frequently used operations on the TreeSet.

1. Adding Elements: In order to add an element to the TreeMap, we can use the add() method. However, the insertion order is not retained in the TreeSet. Internally, for every element, the values are compared and sorted in ascending order. We need to keep a note that duplicate elements are not allowed and all the duplicate elements are ignored. And also, Null values are not accepted by the TreeSet.

// Java code to demonstrate
// the working of TreeSet
import java.util.*;

class TreeSetDemo {

public static void main(String[] args)
{
Set<String> ts = new TreeSet<>();

// Elements are added using add() method
ts.add("Prutor");
ts.add("Ai");
ts.add("Prutor");

System.out.println(ts);
}
}
result:
[Ai, Prutor, Prutor]

2. Accessing the Elements: After adding the elements, if we wish to access the elements, we can use inbuilt methods like contains(), first(), last(), etc.

// Java code to demonstrate the workings of TreeSet
import java.util.*;
class TreeSetDemo {

public static void main(String[] args)
{
NavigableSet<String> ts = new TreeSet<>();

// Elements are added using add() method
ts.add("Prutor");
ts.add("Ai");
ts.add("Prutor");

System.out.println("Tree Set is " + ts);

String check = "Prutor";

// Check if the above string exists in
// the treeset or not
System.out.println("Contains " + check + " "
+ ts.contains(check));

// Print the first element in
// the TreeSet
System.out.println("First Value " + ts.first());

// Print the last element in
// the TreeSet
System.out.println("Last Value " + ts.last());

String val = "Prutor";

// Find the values just greater
// and smaller than the above string
System.out.println("Higher " + ts.higher(val));
System.out.println("Lower " + ts.lower(val));
}
}
result:
Tree Set is [Ai, Prutor, Prutor]
Contains Prutor true
First Value For
Last Value Prutor
Higher Prutor
Lower For

3. Removing the Values: The values can be removed from the TreeSet using the remove() method. There are various other methods that are used to remove the first value or the last value.

// Java code to demonstrate
// the working of TreeSet

import java.util.*;
class TreeSetDemo {

public static void main(String[] args)
{
NavigableSet<String> ts = new TreeSet<>();

// Elements are added using add() method
ts.add("Prutor");
ts.add("Ai");
ts.add("Prutor");
ts.add("A");
ts.add("B");
ts.add("Z");

System.out.println("Initial TreeSet " + ts);

// Removing the element b
ts.remove("B");

System.out.println("After removing element " + ts);

// Removing the first element
ts.pollFirst();

System.out.println("After removing first " + ts);

// Removing the last element
ts.pollLast();

System.out.println("After removing last " + ts);
}
}
result:
Initial TreeSet [A, B, Ai, Prutor, Prutor, Z]
After removing element [A, Ai, Prutor, Prutor, Z]
After removing first [Ai, Prutor, Prutor, Z]
After removing last [Ai, Prutor, Prutor]

4. Iterating through the TreeSet: There are various ways to iterate through the TreeSet. The most famous one is to use the enhanced for loop.

// Java code to demonstrate
// the working of TreeSet

import java.util.*;
class TreeSetDemo {

public static void main(String[] args)
{
Set<String> ts = new TreeSet<>();

// Elements are added using add() method
ts.add("Prutor");
ts.add("Ai");
ts.add("Prutor");
ts.add("A");
ts.add("B");
ts.add("Z");

// Iterating though the TreeSet
for (String value : ts)
System.out.print(value + ", ");
System.out.println();
}
}
result:
A, B, Ai, Prutor, Prutor, Z,

Features of a TreeSet:

  • TreeSet implements the SortedSet interface. So, duplicate values are not allowed.
  • Objects in a TreeSet are stored in a sorted and ascending order.
  • TreeSet does not preserve the insertion order of elements but elements are sorted by keys.
  • If we are depending on the default natural sorting order, the objects that are being inserted into the tree should be homogeneous and comparable. TreeSet does not allow the insertion of heterogeneous objects. It will throw a classCastException at Runtime if we try to add heterogeneous objects.
  • The TreeSet can only accept generic types which are comparable.
  • For example, the StringBuffer class implement the Comparable interface.

// Java code to illustrate the
// error caused when we try to
// insert heterogenous objects
import java.util.*;
class TreeSetDemo {

public static void main(String[] args)
{
Set<StringBuffer> ts = new TreeSet<>();

// Elements are added using add() method
ts.add(new StringBuffer("A"));
ts.add(new StringBuffer("Z"));
ts.add(new StringBuffer("L"));
ts.add(new StringBuffer("B"));
ts.add(new StringBuffer("O"));

// StringBuffer implements Comparable interface
System.out.println(ts);
}
}
Output
[A, B, L, O, Z]
1. Note:

An object is said to be comparable if and only if the corresponding class implements a Comparable interface.
String class and all the Wrapper classes already implement Comparable interface but StringBuffer class doesn’t implement Comparable interface. Hence, we get a ClassCastException in the above example.
For an empty tree-set, when trying to insert null as the first value, one will get NPE from JDK 7. From JDK 7 onwards, null is not at all accepted by TreeSet. However, up to JDK 6, null was accepted as the first value, but any insertion of more null values in the TreeSet resulted in NullPointerException. Hence, it was considered a bug and thus removed in JDK 7.
2. TreeSet serves as an excellent choice for storing large amounts of sorted information which are supposed to be accessed quickly because of its faster access and retrieval time.

3. The insertion of null values into a TreeSet throws NullPointerException because while insertion of null, it gets compared to the existing elements, and null cannot be compared to any value.

How does TreeSet work Internally?

  • TreeSet is basically an implementation of a self-balancing binary search tree like a Red-Black Tree. Therefore operations like add, remove, and search take O(log(N)) time. The reason is that in a self-balancing tree, it is made sure that the height of the tree is always O(log(N)) for all the operations. Therefore, this is considered as one of the most efficient data structure in order to store the huge sorted data and perform operations on it. However, operations like printing N elements in the sorted order takes O(N) time.
  • Synchronized TreeSet: The implementation of a TreeSet is not synchronized. This means that if multiple threads access a tree set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing some object that naturally encapsulates the set. If no such object exists, the set should be “wrapped” using the Collections.synchronizedSortedSet method. This is best done at the creation time, to prevent accidental unsynchronized access to the set. This can be done as:

TreeSet ts = new TreeSet();
Set syncSet = Collections.synchronziedSet(ts);

  • Constructors of TreeSet Class:
    In order to create a TreeSet, we need to create an object of the TreeSet class. The TreeSet class consists various constructors which allow the possible creation of the TreeSet. The following are the constructors available in this class:

1. TreeSet(): This constructor is used to build an empty TreeSet object in which elements will get stored in default natural sorting order. If we wish to create an empty TreeSet with the name ts, then, it can be created as:

TreeSet ts = new TreeSet();

2. TreeSet(Comparator): This constructor is used to build an empty TreeSet object in which elements will need an external specification of the sorting order. If we wish to create an empty TreeSet with the name ts with external sorting phenomenon, then, it can be created as:

TreeSet ts = new TreeSet(Comparator comp);

3. TreeSet(Collection): This constructor is used to build a TreeSet object containing all the elements from the given collection in which elements will get stored in default natural sorting order. In short, this constructor is used when any conversion is needed from any Collection object to TreeSet object. If we wish to create a TreeSet with the name ts, then, it can be created as:

TreeSet t = new TreeSet(Collection col);

4. TreeSet(SortedSet): This constructor is used to build a TreeSet object containing all the elements from the given sortedset in which elements will get stored in default natural sorting order. In short, this constructor is used to convert SortedSet object to the TreeSet Object. If we wish to create a TreeSet with the name ts, then, it can be created as:

TreeSet t = new TreeSet(SortedSet s);

Methods in TreeSet Class

  • TreeSet implements SortedSet so it has the availability of all methods in Collection, Set, and SortedSet interfaces. Following are the methods in the Treeset interface. In the table below, the “?” signifies that the method works with any type of object including user-defined objects.

Method Description

  • add(Object o) This method will add the specified element according to the same sorting order mentioned during the creation of the TreeSet. Duplicate entries will not get added.
  • addAll(Collection c) This method will add all elements of the specified Collection to the set. Elements in the Collection should be homogeneous otherwise ClassCastException will be thrown. Duplicate Entries of Collection will not be added to TreeSet.
  • ceiling?(E e) This method returns the least element in this set greater than or equal to the given element, or null if there is no such element.
  • clear() This method will remove all the elements.
  • clone() The method is used to return a shallow copy of the set, which is just a simple copied set.
  • Comparator comparator() This method will return the Comparator used to sort elements in TreeSet or it will return null if the default natural sorting order is used.
  • contains(Object o) This method will return true if a given element is present in TreeSet else it will return false.
  • descendingIterator?() This method returns an iterator over the elements in this set in descending order.
  • descendingSet?() This method returns a reverse order view of the elements contained in this set.
  • first() This method will return the first element in TreeSet if TreeSet is not null else it will throw NoSuchElementException.
  • floor?(E e) This method returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
  • headSet(Object toElement) This method will return elements of TreeSet which are less than the specified element.
  • higher?(E e) This method returns the least element in this set strictly greater than the given element, or null if there is no such element.
  • isEmpty() This method is used to return true if this set contains no elements or is empty and false for the opposite case.
  • Iterator iterator() Returns an iterator for iterating over the elements of the set.
  • last() This method will return the last element in TreeSet if TreeSet is not null else it will throw NoSuchElementException.
  • lower?(E e) This method returns the greatest element in this set strictly less than the given element, or null if there is no such element.
  • pollFirst?() This method retrieves and removes the first (lowest) element, or returns null if this set is empty.
  • pollLast?() This method retrieves and removes the last (highest) element, or returns null if this set is empty.
  • remove(Object o) This method is used to return a specific element from the set.
  • size() This method is used to return the size of the set or the number of elements present in the set.
  • spliterator?() This method creates a late-binding and fail-fast Spliterator over the elements in this set.
  • subSet(Object fromElement, Object toElement) This method will return elements ranging from fromElement to toElement. fromElement is inclusive and toElement is exclusive.
  • tailSet(Object fromElement) This method will return elements of TreeSet which are greater than or equal to the specified element.
(Next Lesson) How to start learning Java