TreeSet basics

The TreeSet class in Java is part of the java.util package and implements the NavigableSet interface, which is a subtype of the SortedSet interface. TreeSet provides a sorted set of elements that is backed by a TreeMap. The elements in a TreeSet are sorted according to their natural ordering or by a specified comparator.

Key Features of TreeSet

1. Sorted Order: Elements in a TreeSet are maintained in ascending order, either by their natural ordering or by a comparator provided at the time of set creation.
2. No Duplicates: TreeSet does not allow duplicate elements.
3. Navigable Operations: TreeSet provides methods to navigate through the set, like lower, floor, ceiling, and higher.
4. Performance: TreeSet operations such as add, remove, and contains have logarithmic time complexity, O(log n).

Creating a TreeSet

Here’s how to create a TreeSet in Java:

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

public class TreeSetExample {
    public static void main(String[] args) {
        Set<String> treeSet = new TreeSet<>();
    }
}

Basic Operations

Adding Elements

To add elements to a TreeSet, you can use the add method:

treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Orange");

Removing Elements

To remove elements from a TreeSet, you can use the remove method:

treeSet.remove("Banana");

Checking for Elements

To check if a TreeSet contains a specific element, use the contains method:

boolean containsApple = treeSet.contains("Apple");  // returns true
boolean containsBanana = treeSet.contains("Banana");  // returns false

Iterating Over Elements

To iterate over the elements in a TreeSet, you can use an iterator, enhanced for loop, or forEach method:

// Using iterator
Iterator<String> iterator = treeSet.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

// Using enhanced for loop
for (String fruit : treeSet) {
    System.out.println(fruit);
}

// Using forEach method (Java 8 and later)
treeSet.forEach(System.out::println);

Example Program

Here’s a complete example demonstrating various operations with TreeSet:

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

public class TreeSetExample {
    public static void main(String[] args) {
        Set<String> treeSet = new TreeSet<>();

        // Adding elements
        treeSet.add("Apple");
        treeSet.add("Banana");
        treeSet.add("Orange");
        treeSet.add("Apple");  // Duplicate, will not be added

        // Checking size
        System.out.println("Size of treeSet: " + treeSet.size());  // Output: 3

        // Removing an element
        treeSet.remove("Banana");

        // Checking if an element exists
        System.out.println("Contains Apple: " + treeSet.contains("Apple"));  // Output: true
        System.out.println("Contains Banana: " + treeSet.contains("Banana"));  // Output: false

        // Iterating over elements
        System.out.println("Elements in treeSet:");
        for (String fruit : treeSet) {
            System.out.println(fruit);
        }

        // Using forEach method (Java 8 and later)
        treeSet.forEach(System.out::println);
    }
}

Key Methods of TreeSet

1. add(E e): Adds the specified element to the set if it is not already present.
2. remove(Object o): Removes the specified element from the set if it is present.
3. contains(Object o): Returns true if the set contains the specified element.
4. size(): Returns the number of elements in the set.
5. isEmpty(): Returns true if the set contains no elements.
6. clear(): Removes all of the elements from the set.
7. iterator(): Returns an iterator over the elements in the set.
8. first(): Returns the first (lowest) element currently in the set.
9. last(): Returns the last (highest) element currently in the set.
10. comparator(): Returns the comparator used to order the elements in the set, or null if the set uses the natural ordering of its elements.

NavigableSet Methods

As TreeSet implements the NavigableSet interface, it provides additional methods to navigate through the set:

1. lower(E e): Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
2. floor(E e): Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
3. ceiling(E e): Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
4. higher(E e): Returns the least element in this set strictly greater than the given element, or null if there is no such element.
5. pollFirst(): Retrieves and removes the first (lowest) element, or returns null if the set is empty.
6. pollLast(): Retrieves and removes the last (highest) element, or returns null if the set is empty.

TreeSet vs. HashSet

• Order: TreeSet maintains elements in sorted order, while HashSet does not guarantee any specific order of elements.
• Performance: TreeSet operations have logarithmic time complexity, while HashSet operations have constant time complexity (O(1)) for basic operations, assuming a good hash function.
• Null Elements: TreeSet does not allow null elements if a custom comparator is used. HashSet allows null elements.

Performance Considerations

• Logarithmic Time Complexity: TreeSet operations such as add, remove, and contains have logarithmic time complexity (O(log n)).
• Memory Usage: TreeSet uses a TreeMap internally, which can consume more memory compared to a HashMap used by HashSet.

Conclusion

TreeSet is a powerful and flexible implementation of the NavigableSet interface, suitable for scenarios where a sorted set of elements is needed. Its ability to maintain order and provide navigable methods makes it an excellent choice for many applications. However, it’s important to consider the performance implications of using TreeSet compared to other set implementations like HashSet.