Treeset with example code

 avatar
unknown
plain_text
a month ago
2.4 kB
2
Indexable
Conclusion with example code
Use a TreeSet when:

You need to dynamically maintain a sorted order of elements.
You need efficient range-based or closest-value queries.

log(n) tc for add(),remove(),celing(),floor(),lower(),higher()

When Not to Use TreeSet
Small Input Size:

The overhead of maintaining a TreeSet is unnecessary for small arrays. Simpler solutions may work better.

Constant Time Requirements:
If you need O(1) operations like accessing the maximum or minimum element, a TreeSet is less optimal compared to a data structure like a Heap.
When Memory is a Concern:

A TreeSet has a higher memory overhead due to the internal structure of the red-black tree.

Use Case in Problems
These functions are useful in problems where:

You need to find the closest elements to a given value.
Efficient range queries are required, such as finding bounds or intervals dynamically.

For example, in a prefix sum problem:

floor() and ceiling() can help find bounds.
higher() and lower() can help find strictly greater or smaller values.


import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        // Create a TreeSet of integers
        TreeSet<Integer> treeSet = new TreeSet<>();

        // Add elements to the TreeSet
        treeSet.add(10);
        treeSet.add(20);
        treeSet.add(30);
        treeSet.add(40);
        treeSet.add(50);

        System.out.println("TreeSet: " + treeSet);

        // Example of ceiling(): Smallest element >= given value
        System.out.println("ceiling(25): " + treeSet.ceiling(25)); // Output: 30
        System.out.println("ceiling(20): " + treeSet.ceiling(20)); // Output: 20

        // Example of floor(): Largest element <= given value
        System.out.println("floor(25): " + treeSet.floor(25)); // Output: 20
        System.out.println("floor(20): " + treeSet.floor(20)); // Output: 20

        // Example of higher(): Smallest element > given value
        System.out.println("higher(25): " + treeSet.higher(25)); // Output: 30
        System.out.println("higher(20): " + treeSet.higher(20)); // Output: 30

        // Example of lower(): Largest element < given value
        System.out.println("lower(25): " + treeSet.lower(25)); // Output: 20
        System.out.println("lower(30): " + treeSet.lower(30)); // Output: 20
    }
}



Leave a Comment