Java Tutorial/Collections/TreeSet

Check if a particular value exists in TreeSet

   <source lang="java">

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);
 }

}</source>

Copy all elements in TreeSet to an Object Array

   <source lang="java">

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);
   }
 }

}</source>

Creating a TreeSet

The first two constructors create empty tree sets:

   <source lang="java">

public TreeSet() public TreeSet(Comparator comp)</source>

[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.

   <source lang="java">

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());
   }
 }

}</source>

A
C
D
F
G

Get Head Set from Java TreeSet

   <source lang="java">

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);
 }

}</source>

Get lowest and highest value stored in TreeSet

   <source lang="java">

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());
 }

}</source>

Get Size of TreeSet

   <source lang="java">

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());
 }

}</source>

Get Sub Set from TreeSet

   <source lang="java">

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);
 }

}</source>

Get Synchronized Set from TreeSet

   <source lang="java">

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);
 }

}</source>

Get Tail Set from TreeSet

   <source lang="java">

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);
 }

}</source>

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:

   <source lang="java">

SortedSet headSet = set.headSet(toElement+"\0");</source>

[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

   <source lang="java">

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());
   }
 }

}</source>

Looping through a sorted set backwards

   <source lang="java">

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();
   }
 }

}</source>

D
C
B
A

Remove all elements from TreeSet

   <source lang="java">

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());
 }

}</source>

Remove specified element from TreeSet

   <source lang="java">

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);
 }

}</source>

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:

   <source lang="java">

public Object first() public Object last()</source>

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

Sort items in a Set

   <source lang="java">

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 + " ");
   }
 }

}</source>

The second two constructors are copy constructors

   <source lang="java">

public TreeSet(Collection col) public TreeSet(SortedSet set)</source>

[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.

   <source lang="java">

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

}</source>

[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.

   <source lang="java">

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);
 }

}</source>

[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

   <source lang="java">

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);
 }

}</source>

Viewing Subsets

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

   <source lang="java">

SortedSet headSet(Object toElement) SortedSet tailSet(Object fromElement) SortedSet subSet(Object fromElement, Object toElement)</source>

Working with Subsets

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

   <source lang="java">

public SortedSet headSet(Object toElement) public SortedSet tailSet(Object fromElement)</source>

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