Treeset with example code
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