Java Tutorial/Collections/TreeSet

Check if a particular value exists in TreeSet

import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    TreeSet<String> tSet = new TreeSet<String>();
    tSet.add("1");
    tSet.add("2");
    tSet.add("3");
    tSet.add("4");
    tSet.add("5");
    boolean blnExists = tSet.contains("3");
    System.out.println("3 exists in TreeSet ? : " + blnExists);
  }
}

Copy all elements in TreeSet to an Object Array

import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    TreeSet<Integer> tSet = new TreeSet<Integer>();
    tSet.add(new Integer("1"));
    tSet.add(new Integer("2"));
    tSet.add(new Integer("3"));
    Object[] objArray = tSet.toArray();
    for (Object obj: objArray){
      System.out.println(obj);
    }
  }
}

Creating a TreeSet

The first two constructors create empty tree sets:

public TreeSet()
public TreeSet(Comparator comp)

[G, F, D, C, A]
java.util.Collections$ReverseComparator@192d342

Fetching Elements: the iterator() method: public Iterator iterator()

Since the elements of a tree set are ordered, the order of the elements returned will be the order.

import java.util.Arrays;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class MainClass {
  public static void main(String args[]) throws Exception {
    String elements[] = { "A", "C", "D", "G", "F" };
    Set set = new TreeSet(Arrays.asList(elements));
    Iterator iter = set.iterator();
    while (iter.hasNext()) {
      System.out.println(iter.next());
    }
  }
}

A
C
D
F
G

Get Head Set from Java TreeSet

import java.util.SortedSet;
import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    TreeSet<String> tSet = new TreeSet<String>();
    tSet.add("1");
    tSet.add("2");
    tSet.add("3");
    tSet.add("4");
    tSet.add("5");
    SortedSet sortedSet = tSet.headSet("3");
    System.out.println("Head Set Contains : " + sortedSet);
  }
}

Get lowest and highest value stored in TreeSet

import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    TreeSet<String> tSet = new TreeSet<String>();
    tSet.add("1");
    tSet.add("2");
    tSet.add("3");
    tSet.add("4");
    tSet.add("5");
    System.out.println("Lowest value Stored in Java TreeSet is : " + tSet.first());
    System.out.println("Highest value Stored in Java TreeSet is : " + tSet.last());
  }
}

Get Size of TreeSet

import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    TreeSet<Integer> tSet = new TreeSet<Integer>();
    System.out.println("Size of TreeSet : " + tSet.size());
    tSet.add(new Integer("1"));
    tSet.add(new Integer("2"));
    tSet.add(new Integer("3"));
    System.out.println(tSet.size());
    // remove one element from TreeSet using remove method
    tSet.remove(new Integer("1"));
    System.out.println("Size of TreeSet after removal : " + tSet.size());
  }
}

Get Sub Set from TreeSet

import java.util.TreeSet;
import java.util.SortedSet;
public class Main {
  public static void main(String[] args) {
    TreeSet<String> tSet = new TreeSet<String>();
    tSet.add("1");
    tSet.add("2");
    tSet.add("3");
    tSet.add("4");
    tSet.add("5");
    
    SortedSet sortedSet = tSet.subSet("2", "5");
    System.out.println("SortedSet Contains : " + sortedSet);
  }
}

Get Synchronized Set from TreeSet

import java.util.Collections;
import java.util.Set;
import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    TreeSet treeSet = new TreeSet();
    Set set = Collections.synchronizedSet(treeSet);
  }
}

Get Tail Set from TreeSet

import java.util.SortedSet;
import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    TreeSet<String> tSet = new TreeSet<String>();
    tSet.add("1");    
    tSet.add("2");
    tSet.add("3");
    tSet.add("5");
    tSet.add("4");
    SortedSet sortedSet = tSet.tailSet("2");
    System.out.println("Tail Set Contains : " + sortedSet);
  }
}

headset, tailset and subset

headSet: The fromElement will be in the subset, while the toElement will not: fromElement <= set view < toElement

If you want the toElement to be in the subset, you must pass in the next node of the tree, or a value that is just beyond the element.

If you are using string nodes, you can adding something to the end:

SortedSet headSet = set.headSet(toElement+"\0");

[C, D, F, G]
[A]
[A, C]
[D, F, G]
[C, D, F]
[C]
[]

While displaying elements in an easily sorted manner is nice, if you don"t need the behavior, the cost to add elements and search for them is not worth it.

Iterate through elements of TreeSet

import java.util.Iterator;
import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    TreeSet<Integer> tSet = new TreeSet<Integer>();
    tSet.add(new Integer("1"));
    tSet.add(new Integer("2"));
    tSet.add(new Integer("3"));
    Iterator itr = tSet.iterator();
    while (itr.hasNext()){
      System.out.println(itr.next());
    }
  }
}

Looping through a sorted set backwards

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.TreeSet;
public class MainClass {
  public static void main(String[] a) {
    String[] elements = new String[] { "A", "B", "C", "D" };
    TreeSet set = new TreeSet(Arrays.asList(elements));
    try {
      Object last = set.last();
      boolean first = true;
      while (true) {
        if (!first) {
          System.out.print(", ");
        }
        System.out.println(last);
        last = set.headSet(last).last();
      }
    } catch (NoSuchElementException e) {
      System.out.println();
    }
  }
}

D
C
B
A

Remove all elements from TreeSet

import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    TreeSet<Integer> tSet = new TreeSet<Integer>();
    tSet.add(new Integer("1"));
    tSet.add(new Integer("2"));
    tSet.add(new Integer("3"));
    System.out.println("TreeSet before removal : " + tSet);
    tSet.clear();
    System.out.println("TreeSet after removal : " + tSet);
    System.out.println("Is TreeSet empty ? " + tSet.isEmpty());
  }
}

Remove specified element from TreeSet

import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    TreeSet<Integer> tSet = new TreeSet<Integer>();
    tSet.add(new Integer("1"));
    tSet.add(new Integer("2"));
    tSet.add(new Integer("3"));
    System.out.println(tSet);
    System.out.println("Was 2 removed from TreeSet ? " + tSet.remove(new Integer("2")));
    System.out.println(tSet);
  }
}

Retrieving the Ends for a TreeSet

You can use the first() and last() methods of TreeSet to get the elements at the ends of the tree:

public Object first()
public Object last()

[A, C, D, F, G]
A
G

Sort items in a Set

import java.util.Set;
import java.util.TreeSet;
public class Main {
  public static void main(String[] args) {
    Set<String> set = new TreeSet<String>();
    set.add("Z");
    set.add("A");
    set.add("F");
    set.add("B");
    set.add("H");
    set.add("X");
    set.add("N");
    for (String item : set) {
      System.out.print(item + " ");
    }
  }
}

The second two constructors are copy constructors

public TreeSet(Collection col)
public TreeSet(SortedSet set)

[A, C, D, F, G]

The third method subSet() provides the end points: public SortedSet subSet(Object fromElement, Object toElement)

if you remove something from the subset, it"s gone.

if you try to add something to the subtree, it must "fit" within your view of the tree.

And if you add something to the original view, the subset will be altered, too.

import java.util.Arrays;
import java.util.TreeSet;
public class MainClass {
  public static void main(String args[]) throws Exception {
    String elements[] = { "A", "C", "D", "G", "F" };
    TreeSet set = new TreeSet(Arrays.asList(elements));
    System.out.println(set.subSet("C", "F"));
  }
}

[C, D]

To add a single element: the add() method: public boolean add(Object element)

The element to add must implement the Comparable interface or the TreeSet constructor must have been passed a Comparator.

If both of these are not true then a ClassCastException will be thrown.

import java.util.*;
import java.util.Collections;
import java.util.Set;
import java.util.TreeSet;
public class MainClass {
  public static void main(String args[]) throws Exception {
    String elements[] = { "A", "C", "D", "G", "F" };
    Set set = new TreeSet(Collections.reverseOrder());
    for (int i = 0, n = elements.length; i < n; i++) {
      set.add(elements[i]);
    }
    System.out.println(set);
  }
}

[G, F, D, C, A]

TreeSet Class

1. The other concrete Set implementation is the TreeSet.
2. A TreeSet keeps its elements ordered internally.
3. The tree is balanced, it"s a red-black tree.
4. Having a balanced tree guarantees a quick o(log n) search time at the cost of a more time-intensive insertion (and deletion).
5. Elements added to the tree must be orderable.

Red-black tree rules refresher:

1. Every node in the tree is either black or red.
2. The root is always black.
3. If a node is red, its children must be black.
4. Every path from the root to a leaf (or null child) must contain the same number of black nodes. (referenced from "Java Collections by John Zukowski Apress 2001")

TreeSet.descendingSet

import java.util.NavigableSet;
import java.util.TreeSet;
public class CityNavigator {
  static NavigableSet<String> citiesSet;
  public static void main(String[] args) {
    String[] cities = { "A", "B", "C", "D", "E", "F" };
    citiesSet = new TreeSet<String>();
    for (String city : cities)
      citiesSet.add(city);
    for (String city : citiesSet.descendingSet())
      System.out.println("  " + city);
  }
}

Viewing Subsets

The headSet(), tailSet(), and subSet() allow you to acquire the subset.

SortedSet headSet(Object toElement)
SortedSet tailSet(Object fromElement)
SortedSet subSet(Object fromElement, Object toElement)

Working with Subsets

Since a TreeSet is ordered, its subset is also ordered. The two that are simplest to explain are headset() and tailSet():

public SortedSet headSet(Object toElement)
public SortedSet tailSet(Object fromElement)

[A, C]
[A, C, D, F, G]