Java TreeSet Introduction

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.

TreeSet Hierarchy:

Constructors of TreeSet

1. TreeSet t = new TreeSet();
   This will create an empty TreeSet object in which elements will get stored in default natural sorting order.
2. TreeSet t = new TreeSet(Comparator comp);
   This constructor is used when the external specification of sorting order of elements is needed.
3. TreeSet t = new TreeSet(Collection col); 
   This constructor is used when any conversion is needed from any Collection object to TreeSet object.
4. TreeSet t = new TreeSet(SortedSet s);
   This constructor is used to convert SortedSet object to TreeSet Object.

TreeSet implements the SortedSet interface. To create a TreeSet, use a constructor, as shown in Figure above.

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class TreeSetDemo {


    public static void main(String[] args) {
        // Create a hash set
        Set<String> set = new HashSet<>();

        // Add strings to the set
        set.add("London");
        set.add("Paris");
        set.add("New York");
        set.add("San Francisco");
        set.add("Beijing");
        set.add("New York");

        TreeSet<String> treeSet = new TreeSet<>(set);
        System.out.println("Sorted tree set: " + treeSet);

        // Use the methods in SortedSet interface
        System.out.println("first(): " + treeSet.first());
        System.out.println("last(): " + treeSet.last());
        System.out.println("headSet(\"New York\"): " +
                treeSet.headSet("New York"));
        System.out.println("tailSet(\"New York\"): " +
                treeSet.tailSet("New York"));

        // Use the methods in NavigableSet interface
        System.out.println("lower(\"P\"): " + treeSet.lower("P"));
        System.out.println("higher(\"P\"): " + treeSet.higher("P"));
        System.out.println("floor(\"P\"): " + treeSet.floor("P"));
        System.out.println("ceiling(\"P\"): " + treeSet.ceiling("P"));
        System.out.println("pollFirst(): " + treeSet.pollFirst());
        System.out.println("pollLast(): " + treeSet.pollLast());
        System.out.println("New tree set: " + treeSet);

    }
}

Two things must be kept in mind while creating and adding elements into a TreeSet:

• Firstly, insertion of null 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
• Secondly, if we are depending on default natural sorting order, compulsory the object should be homogeneous and comparable otherwise we will get RuntimeException: ClassCastException

// Java code to illustrate StringBuffer 
// class does not implements 
// Comparable interface. 
import java.util.*; 
class TreeSetDemo { 

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

    // 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")); 

    // We will get RunTimeException :ClassCastException 
    // As StringBuffer does not implements Comparable interface 
    System.out.println(ts); 
  } 
} 

output

Exception in thread "main" java.lang.ClassCastException: java.base/java.lang.StringBuffer cannot be cast to java.base/java.lang.Comparable
  at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
  at java.base/java.util.TreeMap.put(TreeMap.java:536)
  at java.base/java.util.TreeSet.add(TreeSet.java:255)
  at SetDemo.treeset.TreeSetDemo.main(TreeSetDemo.java:47)

Two ways to sort TreeSet

• Using compareTo() method in Comparable interface
• Using compare() method in Comparator interface

Using compareTo() method in Comparable interface

package SetDemo.treeset;

import java.util.TreeSet;

public class ComparableTreeSetDemo {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet();

        ts.add(new Person("aa", 20, "男"));
        ts.add(new Person("bb", 18, "女"));
        ts.add(new Person("cc", 19, "男"));
        ts.add(new Person("dd", 17, "女"));
        ts.add(new Person("dd", 17, "女"));
        ts.add(new Person("dd", 17, "女"));
        ts.add(new Person("dd", 16, "女"));


        System.out.println(ts);
        System.out.println(ts.size()); // 5

    }
}

class Person implements Comparable {
    private String name;
    private int age;
    private String gender;

    public Person() {

    }

    public Person(String name, int age, String gender) {

        this.name = name;
        this.age = age;
        this.gender = gender;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getGender() {
        return gender;
    }

    public void setGender(String gender) {
        this.gender = gender;
    }

    @Override
    public int hashCode() {
        return name.hashCode() + age * 37;
    }

    public boolean equals(Object obj) {
        if (!(obj instanceof Person)) {
            return false;
        }
        Person p = (Person) obj;
        return this.name.equals(p.name) && this.age == p.age;

    }

    public String toString() {
        return "Person [name=" + name + ", age=" + age + ", gender=" + gender
                + "]";
    }

    @Override
    public int compareTo(Object obj) {

        Person p = (Person) obj;
        if (this.age > p.age) {
            return 1;
        }
        if (this.age < p.age) {
            return -1;
        }
        return this.name.compareTo(p.name);
    }

}

output:

Person [name=dd, age=16, gender=女]
Person [name=dd, age=17, gender=女]
Person [name=bb, age=18, gender=女]
Person [name=cc, age=19, gender=男]
Person [name=aa, age=20, gender=男]

Using compare() method in Comparator interface

package SetDemo.treeset;

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetComparatorDemo {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet(new MyComparator());
        ts.add(new Book("think in java", 100));
        ts.add(new Book("java 核心技术", 75));
        ts.add(new Book("现代操作系统", 50));
        ts.add(new Book("java就业教程", 35));
        ts.add(new Book("think in java", 100));
        ts.add(new Book("ccc in java", 100));

        for (Object book : ts) {
            System.out.println(book);
        }
    }
}

class MyComparator implements Comparator {

    public int compare(Object o1, Object o2) {
        Book b1 = (Book) o1;
        Book b2 = (Book) o2;
        if (b1.getPrice() > b2.getPrice()) {
            return 1;
        }
        if (b1.getPrice() < b2.getPrice()) {
            return -1;
        }
        return b1.getName().compareTo(b2.getName());
    }

}

class Book {
    private String name;
    private double price;

    public Book() {

    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    public Book(String name, double price) {

        this.name = name;
        this.price = price;
    }

    @Override
    public String toString() {
        return "Book [name=" + name + ", price=" + price + "]";
    }

}

output:

Book [name=java就业教程, price=35.0]
Book [name=现代操作系统, price=50.0]
Book [name=java 核心技术, price=75.0]
Book [name=ccc in java, price=100.0]
Book [name=think in java, price=100.0]