TreeSet

  • The underlying data structure is Balanced Tree
  • Duplicates are not allowed
  • Insertion order is not preserved
  • Heterogeneous Objects are not allowed. (If done then class cast Exception)
  • Null insertion allowed, but only once
  • Implements Serializable and Clonable
  • All objects will be inserted in default sorting order or customized sorting order

  • An object inserted in treeset should implement comparable or comparator should be passed to TreeSet to sort the data
  • If we insert null in non empty tree set we get null pointer exception
  • If we are using CustomeComparator in TreeSet then Heterogeneous Objects are allowed
  • TreeSet always required an inserted object to implement Comparable Interface if no CustomeComparator is being used

Constructors :

  • TreeSet t = new TreeSet()
    • Empty tree set with DataInserted in default sorting order
  • TreeSet t = new TreeSet(Comparator c)
    • Empty tree set with DataInserted in Customized sorting order
  • TreeSet t = new TreeSet(Collection c)
    • Cross collection conversion using constructor
  • TreeSet t = new TreeSet(SortedSet s)
    • The sorting order of the passed collection is used

Example :

  • If we are dependent on the Default Natural Sorting Order then
    • the object should have implemented Comparable Interface
    • the objects should be homogeneous
  • If above rules are not followed we get class cast exception

Comparable Interface

  • Present in java.lang package
  • Contains only one method
    • public int compareTo(Object o);
    • Example obj1.compareTo(obj2)
      • If obj1 is greater than obj2, the return is positive
      • If obj1 is less than obj2, the return is negative
      • If obj1 is equal to obj2, the return is zero

Internal Working of Tree Set

  • t.add(“k”);
  • t.add(“z”);
    • obj1.compareTo(obj2)
    • “z”.compareTo(“k”);

Note : Comparable Interface meant for Default Natural Sorting Order and Comparator Interface is meant for Customized Sorting Order

Comparator Interface

  • present in java.util package
  • defines 2 methods
    • public int compare(Object obj1, Object obj2)
    • public boolean equals(Object obj)
  • Whenever we are implementing comparator interface we need not implement equals method since it is already present in Object class

WAP to insert Integer object into TreeSet where the sorting order is descending order

Note :

  • In Comparator 1st parameter is the new value and 2nd parameter is the root
  • Left size of tree is negative and right side of root is positive
  • The traversal happens in a tree in [ Left – Root – right ] Order
  • Reference – Youtube Durga

Example :

Tree Structure of the above code

Various Possible implementation of Compare Method

  • If -1 returned then go to left side of root
  • if 1 returned then go to right side of root
  • if 0 returned then it is considered as duplicate
  • compareTo method is the default comparator for Integer (Comparable Interface method)

WAP to insert string object into the tree set where all elements should be inserted according to reveser of alphabetical order.

WAP to insert StringBuffer object in Alphabetical order

WAP to insert String and StringBuffer objects into TreeSet where sorting order is increasing length order. If two objects having the same length then consider then alphabetical order

Comparable vs Comparator

ComparableComparator
Default Natural Sorting orderCustome Natural Sorting Order
Package java.langPackage java.util
Only one method compareTo()2 methods compare() and equals()
All Wrapper classes and String classes implements ComparableNo major classes implements comparator out of the box
For predefined comparable classes, default natural sorting order already available, if we are not satisfied with that Natural sorting then we can define our own sorting by using compartorFor predefined comparable classes like String Buffer, default Natural sorting order not available, we can define our own sorting by using comparator
Person who is implementing a custom class, we he response for defining the default natural sorting order by implementing Comparable methodPerson who is using the custom class who want to change the default natural sorting order can implement Comparator for sorting

Leave a Comment