TreeSet
Simply put, the TreeSet is a sorted collection that extends the AbstractSet class and implements the NavigableSet interface. Here’s a quick summary of the most important aspects of this implementation:
- It stores unique elements
- It doesn’t preserve the insertion order of the elements
- It sorts the elements in ascending order
- It’s not thread-safe In this implementation, objects are sorted and stored in ascending order according to their natural order. The TreeSet uses a self-balancing binary search tree, more specifically a Red-Black tree.
Simply put, being a self-balancing binary search tree, each node of the binary tree comprises of an extra bit, which is used to identify the color of the node which is either red or black. During subsequent insertions and deletions, these “color” bits helps in ensuring that the tree remains more or less balanced.
So, let’s create an instance of a TreeSet:
Set<String> treeSet = new TreeSet<>();
Optionally, we can construct a TreeSet with a constructor that lets us define the order in which the elements get sorted by using a Comparable or Comparator:
Set<String> treeSet = new TreeSet<>(Comparator.comparing(String::length));
ublic class TreeSet<E>
extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
private transient NavigableMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public TreeSet() {
this(new TreeMap<E,Object>());
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
}
When compared to a HashSet the performance of a TreeSet is on the lower side. Operations like add, remove and search take O(log n) time while operations like printing n elements in sorted order require O(n) time.
A TreeSet should be our primary choice if we want to keep our entries sorted as a TreeSet may be accessed and traversed in either ascending or descending order, and the performance of ascending operations and views is likely to be faster than that of descending ones.
The Principle of Locality – is a term for the phenomenon in which the same values, or related storage locations, are frequently accessed, depending on the memory access pattern.
When we say locality:
Similar data is often accessed by an application with similar frequency If two entries are nearby given an ordering, a TreeSet places them near each other in the data structure, and hence in memory A TreeSet being a data-structure with greater locality we can, therefore, conclude in accordance to the Principle of Locality, that we should give preference to a TreeSet if we’re short on memory and if we want to access elements that are relatively close to each other according to their natural ordering.
In case data needs to be read from the hard drive (which has greater latency than data read from the cache or memory) then prefer TreeSet as it has greater locality.
"Natural" ordering is the ordering implied by the implementation of Comparable interface by the objects in the TreeSet . Essentially RBTree must be able to tell which object is smaller than other object , and there are two ways to supply that logic to the RB Tree implementation :
- We need to implement the Comparable interface in the class(es) used as objects in TreeSet.
- Supply an implementation of the Comparator would do comparing outside the class itself.
- According to Oracle docs , clone() method returns the shallow copy of the TreeSet instance. In shallow copy , Both objects A and B shared the same memory location .
- SortedSet is an interface while TreeSet is the class implementing it. As we know, in java, we can not create the objects of the interface. The class implementing the interface must fulfill the contract of interface, i.e , concrete class must implement all the methods present in the interface. TreeSet is such an implementation.
- Its Mandatory to implement comparable else will get compilation error
java.lang.ClassCastException: <class> cannot be cast to java.lang.Comparable - If You use Comparator preference is being given to Comparator.
Refrences http://javahungry.blogspot.com/2015/10/how-treeset-works-internally-in-java-interview-questions.html https://www.journaldev.com/16182/java-treeset http://www.baeldung.com/java-tree-set