TreeMap is a Red-Black tree based implementation of the Map interface that maintains its keys in sorted order. Let's explore its internal working and sorted key features in detail.

1. TreeMap Class Structure and Basics

Basic Class Declaration

import java.util.*; public class TreeMapBasics { public static void main(String[] args) { // Creating TreeMap with natural ordering TreeMap<Integer, String> treeMap = new TreeMap<>(); // Adding elements - keys are automatically sorted treeMap.put(3, "Three"); treeMap.put(1, "One"); treeMap.put(4, "Four"); treeMap.put(2, "Two"); treeMap.put(5, "Five"); System.out.println("TreeMap contents (automatically sorted by keys):"); System.out.println(treeMap); // Output: {1=One, 2=Two, 3=Three, 4=Four, 5=Five} // Iteration follows sorted order System.out.println("\nIteration in sorted order:"); for (Map.Entry<Integer, String> entry : treeMap.entrySet()) { System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue()); } } }

TreeMap with Custom Comparator

import java.util.*; public class TreeMapWithComparator { public static void main(String[] args) { // TreeMap with reverse order comparator TreeMap<Integer, String> reverseMap = new TreeMap<>(Collections.reverseOrder()); reverseMap.put(3, "Three"); reverseMap.put(1, "One"); reverseMap.put(4, "Four"); reverseMap.put(2, "Two"); System.out.println("TreeMap with reverse ordering:"); System.out.println(reverseMap); // Output: {4=Four, 3=Three, 2=Two, 1=One} // TreeMap with custom string length comparator TreeMap<String, Integer> lengthMap = new TreeMap<>( Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder()) ); lengthMap.put("Apple", 1); lengthMap.put("Banana", 2); lengthMap.put("Cat", 3); lengthMap.put("Dog", 4); lengthMap.put("Elephant", 5); System.out.println("\nTreeMap sorted by string length:"); System.out.println(lengthMap); // Output: {Cat=3, Dog=4, Apple=1, Banana=2, Elephant=5} } }

2. Internal Red-Black Tree Structure

Understanding the Tree Structure

import java.util.*; public class TreeMapInternalStructure { static class Employee implements Comparable<Employee> { private int id; private String name; private String department; public Employee(int id, String name, String department) { this.id = id; this.name = name; this.department = department; } @Override public int compareTo(Employee other) { return Integer.compare(this.id, other.id); } @Override public String toString() { return String.format("Employee{id=%d, name='%s', dept='%s'}", id, name, department); } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Employee employee = (Employee) o; return id == employee.id; } @Override public int hashCode() { return Objects.hash(id); } } public static void main(String[] args) { // TreeMap using Comparable (natural ordering) TreeMap<Employee, Double> employeeSalaries = new TreeMap<>(); Employee e1 = new Employee(103, "John", "Engineering"); Employee e2 = new Employee(101, "Alice", "Marketing"); Employee e3 = new Employee(105, "Bob", "Sales"); Employee e4 = new Employee(102, "Carol", "HR"); Employee e5 = new Employee(104, "David", "Engineering"); employeeSalaries.put(e1, 75000.0); employeeSalaries.put(e2, 65000.0); employeeSalaries.put(e3, 80000.0); employeeSalaries.put(e4, 60000.0); employeeSalaries.put(e5, 70000.0); System.out.println("Employees sorted by ID (natural ordering):"); for (Map.Entry<Employee, Double> entry : employeeSalaries.entrySet()) { System.out.println(entry.getKey() + " -> Salary: $" + entry.getValue()); } // TreeMap with custom comparator TreeMap<Employee, Double> deptSortedMap = new TreeMap<>( Comparator.comparing((Employee e) -> e.department) .thenComparing(e -> e.name) ); deptSortedMap.putAll(employeeSalaries); System.out.println("\nEmployees sorted by Department then Name:"); for (Map.Entry<Employee, Double> entry : deptSortedMap.entrySet()) { System.out.println(entry.getKey() + " -> Salary: $" + entry.getValue()); } } }

3. Navigation Methods for Sorted Keys

Key Navigation Methods

import java.util.*; public class TreeMapNavigation { public static void main(String[] args) { TreeMap<Integer, String> treeMap = new TreeMap<>(); // Populate TreeMap for (int i = 1; i <= 10; i++) { treeMap.put(i * 10, "Value-" + (i * 10)); } System.out.println("Original TreeMap: " + treeMap); // First and last keys System.out.println("\nFirst key: " + treeMap.firstKey()); System.out.println("Last key: " + treeMap.lastKey()); // Lower and higher keys System.out.println("\nNavigation around key 35:"); System.out.println("Lower key (strictly less): " + treeMap.lowerKey(35)); // 30 System.out.println("Floor key (less or equal): " + treeMap.floorKey(35)); // 30 System.out.println("Ceiling key (greater or equal): " + treeMap.ceilingKey(35)); // 40 System.out.println("Higher key (strictly greater): " + treeMap.higherKey(35)); // 40 // Head, tail, and subMap views System.out.println("\nHead map (keys < 40): " + treeMap.headMap(40)); System.out.println("Head map inclusive (keys <= 40): " + treeMap.headMap(40, true)); System.out.println("Tail map (keys >= 60): " + treeMap.tailMap(60)); System.out.println("Tail map exclusive (keys > 60): " + treeMap.tailMap(60, false)); System.out.println("Sub map (30 <= keys < 80): " + treeMap.subMap(30, 80)); System.out.println("Sub map inclusive (30 <= keys <= 80): " + treeMap.subMap(30, true, 80, true)); // Poll first and last entries System.out.println("\nPoll first entry: " + treeMap.pollFirstEntry()); System.out.println("Poll last entry: " + treeMap.pollLastEntry()); System.out.println("TreeMap after polling: " + treeMap); // Descending map view System.out.println("\nDescending map: " + treeMap.descendingMap()); System.out.println("Descending key set: " + treeMap.descendingKeySet()); } }

Practical Navigation Example

import java.util.*; public class TreeMapNavigationPractical { public static void main(String[] args) { // TreeMap representing product prices TreeMap<String, Double> productPrices = new TreeMap<>(); productPrices.put("Laptop", 999.99); productPrices.put("Mouse", 29.99); productPrices.put("Keyboard", 79.99); productPrices.put("Monitor", 299.99); productPrices.put("Headphones", 149.99); productPrices.put("Tablet", 499.99); productPrices.put("Smartphone", 699.99); System.out.println("All products sorted by name:"); productPrices.forEach((name, price) -> System.out.printf("%-12s: $%.2f%n", name, price)); // Find products in a specific range String fromProduct = "Keyboard"; String toProduct = "Smartphone"; System.out.println("\nProducts between '" + fromProduct + "' and '" + toProduct + "':"); SortedMap<String, Double> rangeProducts = productPrices.subMap(fromProduct, toProduct); rangeProducts.forEach((name, price) -> System.out.printf("%-12s: $%.2f%n", name, price)); // Find cheapest and most expensive products alphabetically System.out.println("\nFirst product alphabetically: " + productPrices.firstEntry()); System.out.println("Last product alphabetically: " + productPrices.lastEntry()); // Find products before and after a specific product String targetProduct = "Monitor"; System.out.println("\nProducts before '" + targetProduct + "': " + productPrices.headMap(targetProduct)); System.out.println("Products after '" + targetProduct + "': " + productPrices.tailMap(targetProduct, false)); // Navigation for price ranges (if we had price as key) demonstratePriceRangeNavigation(); } public static void demonstratePriceRangeNavigation() { System.out.println("\n=== Price Range Navigation ==="); // TreeMap with price as key TreeMap<Double, String> priceToProduct = new TreeMap<>(); priceToProduct.put(999.99, "Laptop"); priceToProduct.put(29.99, "Mouse"); priceToProduct.put(79.99, "Keyboard"); priceToProduct.put(299.99, "Monitor"); priceToProduct.put(149.99, "Headphones"); priceToProduct.put(499.99, "Tablet"); priceToProduct.put(699.99, "Smartphone"); // Find products in price range $100 - $500 System.out.println("Products between $100 and $500:"); SortedMap<Double, String> affordableProducts = priceToProduct.subMap(100.0, 500.0); affordableProducts.forEach((price, product) -> System.out.printf("$%-8.2f: %s%n", price, product)); // Find cheapest and most expensive products System.out.println("\nCheapest product: " + priceToProduct.firstEntry()); System.out.println("Most expensive product: " + priceToProduct.lastEntry()); // Find products below a certain price double budget = 200.0; System.out.println("\nProducts under $" + budget + ":"); SortedMap<Double, String> budgetProducts = priceToProduct.headMap(budget); budgetProducts.forEach((price, product) -> System.out.printf("$%-8.2f: %s%n", price, product)); } }

4. SortedMap and NavigableMap Interfaces

Implementing SortedMap Operations

import java.util.*; public class TreeMapSortedOperations { public static void main(String[] args) { TreeMap<Integer, String> sortedMap = new TreeMap<>(); // Add elements in random order sortedMap.put(50, "Fifty"); sortedMap.put(10, "Ten"); sortedMap.put(80, "Eighty"); sortedMap.put(30, "Thirty"); sortedMap.put(70, "Seventy"); sortedMap.put(20, "Twenty"); sortedMap.put(90, "Ninety"); sortedMap.put(40, "Forty"); sortedMap.put(60, "Sixty"); System.out.println("Complete sorted map: " + sortedMap); // SortedMap interface methods System.out.println("\n=== SortedMap Operations ==="); System.out.println("First key: " + sortedMap.firstKey()); System.out.println("Last key: " + sortedMap.lastKey()); Integer fromKey = 25; Integer toKey = 75; System.out.println("\nRange view from " + fromKey + " to " + toKey + ":"); SortedMap<Integer, String> subMap = sortedMap.subMap(fromKey, toKey); System.out.println(subMap); System.out.println("\nHead map (keys < " + toKey + "):"); SortedMap<Integer, String> headMap = sortedMap.headMap(toKey); System.out.println(headMap); System.out.println("\nTail map (keys >= " + fromKey + "):"); SortedMap<Integer, String> tailMap = sortedMap.tailMap(fromKey); System.out.println(tailMap); System.out.println("\nComparator used: " + sortedMap.comparator()); // NavigableMap interface methods System.out.println("\n=== NavigableMap Operations ==="); System.out.println("Lower entry than 25: " + sortedMap.lowerEntry(25)); System.out.println("Floor entry for 25: " + sortedMap.floorEntry(25)); System.out.println("Ceiling entry for 25: " + sortedMap.ceilingEntry(25)); System.out.println("Higher entry than 25: " + sortedMap.higherEntry(25)); System.out.println("\nDescending map: " + sortedMap.descendingMap()); System.out.println("Navigable key set: " + sortedMap.navigableKeySet()); // Polling operations System.out.println("\nPoll first entry: " + sortedMap.pollFirstEntry()); System.out.println("Poll last entry: " + sortedMap.pollLastEntry()); System.out.println("Map after polling: " + sortedMap); } }

5. Performance Characteristics

Time Complexity Analysis

import java.util.*; public class TreeMapPerformance { private static final int TEST_SIZE = 100000; public static void main(String[] args) { System.out.println("TreeMap Performance Analysis"); System.out.println("Test Size: " + TEST_SIZE + " elements"); System.out.println("====================================="); testPutPerformance(); testGetPerformance(); testNavigationPerformance(); testRemovePerformance(); testMemoryUsage(); } public static void testPutPerformance() { System.out.println("\n=== Put Operations ==="); TreeMap<Integer, String> treeMap = new TreeMap<>(); // Sequential puts long start = System.nanoTime(); for (int i = 0; i < TEST_SIZE; i++) { treeMap.put(i, "Value-" + i); } long end = System.nanoTime(); System.out.printf("Sequential put: %.2f ms%n", (end - start) / 1_000_000.0); // Random puts treeMap.clear(); Random random = new Random(); start = System.nanoTime(); for (int i = 0; i < TEST_SIZE; i++) { treeMap.put(random.nextInt(TEST_SIZE * 10), "Value-" + i); } end = System.nanoTime(); System.out.printf("Random put: %.2f ms%n", (end - start) / 1_000_000.0); // Compare with HashMap HashMap<Integer, String> hashMap = new HashMap<>(); start = System.nanoTime(); for (int i = 0; i < TEST_SIZE; i++) { hashMap.put(i, "Value-" + i); } end = System.nanoTime(); System.out.printf("HashMap sequential put: %.2f ms%n", (end - start) / 1_000_000.0); } public static void testGetPerformance() { System.out.println("\n=== Get Operations ==="); TreeMap<Integer, String> treeMap = new TreeMap<>(); for (int i = 0; i < TEST_SIZE; i++) { treeMap.put(i, "Value-" + i); } // Sequential gets long start = System.nanoTime(); for (int i = 0; i < TEST_SIZE; i++) { treeMap.get(i); } long end = System.nanoTime(); System.out.printf("Sequential get: %.2f ms%n", (end - start) / 1_000_000.0); // Random gets Random random = new Random(); start = System.nanoTime(); for (int i = 0; i < 10000; i++) { treeMap.get(random.nextInt(TEST_SIZE)); } end = System.nanoTime(); System.out.printf("Random get (10000 operations): %.2f ms%n", (end - start) / 1_000_000.0); // Compare with HashMap HashMap<Integer, String> hashMap = new HashMap<>(treeMap); start = System.nanoTime(); for (int i = 0; i < 10000; i++) { hashMap.get(random.nextInt(TEST_SIZE)); } end = System.nanoTime(); System.out.printf("HashMap random get (10000 operations): %.2f ms%n", (end - start) / 1_000_000.0); } public static void testNavigationPerformance() { System.out.println("\n=== Navigation Operations ==="); TreeMap<Integer, String> treeMap = new TreeMap<>(); for (int i = 0; i < TEST_SIZE; i++) { treeMap.put(i, "Value-" + i); } // First/last operations long start = System.nanoTime(); for (int i = 0; i < 10000; i++) { treeMap.firstKey(); treeMap.lastKey(); } long end = System.nanoTime(); System.out.printf("First/Last operations (10000 pairs): %.2f ms%n", (end - start) / 1_000_000.0); // Range queries start = System.nanoTime(); for (int i = 0; i < 1000; i++) { treeMap.subMap(i, i + 100); } end = System.nanoTime(); System.out.printf("Range queries (1000 operations): %.2f ms%n", (end - start) / 1_000_000.0); // Ceiling/floor operations Random random = new Random(); start = System.nanoTime(); for (int i = 0; i < 10000; i++) { treeMap.ceilingKey(random.nextInt(TEST_SIZE)); treeMap.floorKey(random.nextInt(TEST_SIZE)); } end = System.nanoTime(); System.out.printf("Ceiling/Floor operations (10000 pairs): %.2f ms%n", (end - start) / 1_000_000.0); } public static void testRemovePerformance() { System.out.println("\n=== Remove Operations ==="); TreeMap<Integer, String> treeMap = new TreeMap<>(); for (int i = 0; i < TEST_SIZE; i++) { treeMap.put(i, "Value-" + i); } // Remove from end long start = System.nanoTime(); for (int i = TEST_SIZE - 1; i >= TEST_SIZE - 10000; i--) { treeMap.remove(i); } long end = System.nanoTime(); System.out.printf("Remove from end (10000 operations): %.2f ms%n", (end - start) / 1_000_000.0); // Remove from beginning for (int i = 0; i < 10000; i++) { treeMap.put(i, "Value-" + i); } start = System.nanoTime(); for (int i = 0; i < 10000; i++) { treeMap.remove(i); } end = System.nanoTime(); System.out.printf("Remove from beginning (10000 operations): %.2f ms%n", (end - start) / 1_000_000.0); } public static void testMemoryUsage() { System.out.println("\n=== Memory Usage ==="); Runtime runtime = Runtime.getRuntime(); // Force garbage collection System.gc(); long memoryBefore = runtime.totalMemory() - runtime.freeMemory(); TreeMap<Integer, String> treeMap = new TreeMap<>(); for (int i = 0; i < TEST_SIZE; i++) { treeMap.put(i, "Value-" + i); } long memoryAfter = runtime.totalMemory() - runtime.freeMemory(); long memoryUsed = memoryAfter - memoryBefore; System.out.printf("Memory used by TreeMap with %d elements: %.2f MB%n", TEST_SIZE, memoryUsed / (1024.0 * 1024.0)); // Compare with HashMap System.gc(); memoryBefore = runtime.totalMemory() - runtime.freeMemory(); HashMap<Integer, String> hashMap = new HashMap<>(); for (int i = 0; i < TEST_SIZE; i++) { hashMap.put(i, "Value-" + i); } memoryAfter = runtime.totalMemory() - runtime.freeMemory(); long hashMapMemoryUsed = memoryAfter - memoryBefore; System.out.printf("Memory used by HashMap with %d elements: %.2f MB%n", TEST_SIZE, hashMapMemoryUsed / (1024.0 * 1024.0)); } }

6. Real-World Use Cases

Event Scheduling System

import java.util.*; public class EventScheduler { static class Event implements Comparable<Event> { private Date timestamp; private String name; private String description; public Event(Date timestamp, String name, String description) { this.timestamp = timestamp; this.name = name; this.description = description; } @Override public int compareTo(Event other) { return this.timestamp.compareTo(other.timestamp); } @Override public String toString() { SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); return String.format("Event{time=%s, name='%s', desc='%s'}", sdf.format(timestamp), name, description); } } public static void main(String[] args) throws Exception { SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); // Event scheduler using TreeMap TreeMap<Date, Event> eventSchedule = new TreeMap<>(); // Add events (not in chronological order) eventSchedule.put(sdf.parse("2024-03-20 10:00:00"), new Event(sdf.parse("2024-03-20 10:00:00"), "Meeting", "Team meeting")); eventSchedule.put(sdf.parse("2024-03-20 09:30:00"), new Event(sdf.parse("2024-03-20 09:30:00"), "Breakfast", "Client breakfast")); eventSchedule.put(sdf.parse("2024-03-20 14:00:00"), new Event(sdf.parse("2024-03-20 14:00:00"), "Presentation", "Product demo")); eventSchedule.put(sdf.parse("2024-03-20 11:30:00"), new Event(sdf.parse("2024-03-20 11:30:00"), "Lunch", "Lunch with team")); System.out.println("Scheduled events (automatically sorted by time):"); eventSchedule.forEach((time, event) -> System.out.println(sdf.format(time) + " - " + event.name)); // Find next event from current time Date currentTime = sdf.parse("2024-03-20 10:15:00"); Map.Entry<Date, Event> nextEvent = eventSchedule.ceilingEntry(currentTime); System.out.println("\nNext event after " + sdf.format(currentTime) + ": " + (nextEvent != null ? nextEvent.getValue() : "None")); // Find events for the next 2 hours Date endTime = new Date(currentTime.getTime() + 2 * 60 * 60 * 1000); SortedMap<Date, Event> upcomingEvents = eventSchedule.subMap(currentTime, endTime); System.out.println("\nEvents in next 2 hours:"); upcomingEvents.forEach((time, event) -> System.out.println(sdf.format(time) + " - " + event.name)); // Get today's schedule Date startOfDay = sdf.parse("2024-03-20 00:00:00"); Date endOfDay = sdf.parse("2024-03-20 23:59:59"); SortedMap<Date, Event> dailySchedule = eventSchedule.subMap(startOfDay, endOfDay); System.out.println("\nToday's schedule:"); dailySchedule.forEach((time, event) -> System.out.println(sdf.format(time) + " - " + event.name)); } }

Product Catalog with Categories

import java.util.*; public class ProductCatalog { static class Product implements Comparable<Product> { private String category; private String name; private double price; private int stock; public Product(String category, String name, double price, int stock) { this.category = category; this.name = name; this.price = price; this.stock = stock; } @Override public int compareTo(Product other) { int categoryCompare = this.category.compareTo(other.category); if (categoryCompare != 0) return categoryCompare; return this.name.compareTo(other.name); } @Override public String toString() { return String.format("Product{category='%s', name='%s', price=%.2f, stock=%d}", category, name, price, stock); } } public static void main(String[] args) { TreeMap<Product, Integer> productCatalog = new TreeMap<>(); // Add products (will be sorted by category then name) productCatalog.put(new Product("Electronics", "Laptop", 999.99, 10), 10); productCatalog.put(new Product("Books", "Java Programming", 49.99, 25), 25); productCatalog.put(new Product("Electronics", "Smartphone", 699.99, 15), 15); productCatalog.put(new Product("Clothing", "T-Shirt", 19.99, 50), 50); productCatalog.put(new Product("Books", "Python Guide", 39.99, 30), 30); productCatalog.put(new Product("Electronics", "Headphones", 149.99, 20), 20); System.out.println("Product Catalog (sorted by category then name):"); productCatalog.forEach((product, stock) -> System.out.println(product + " -> Stock: " + stock)); // Find all products in a category String targetCategory = "Electronics"; System.out.println("\nAll " + targetCategory + " products:"); productCatalog.keySet().stream() .filter(p -> p.category.equals(targetCategory)) .forEach(p -> System.out.println(p.name + " - $" + p.price)); // Price-based searching (using a different TreeMap) TreeMap<Double, Product> priceIndex = new TreeMap<>(); productCatalog.keySet().forEach(product -> priceIndex.put(product.price, product)); // Find products in price range double minPrice = 50.0; double maxPrice = 200.0; System.out.println("\nProducts between $" + minPrice + " and $" + maxPrice + ":"); priceIndex.subMap(minPrice, true, maxPrice, true) .forEach((price, product) -> System.out.printf("$%.2f: %s%n", price, product.name)); // Get cheapest and most expensive products System.out.println("\nCheapest product: " + priceIndex.firstEntry().getValue()); System.out.println("Most expensive product: " + priceIndex.lastEntry().getValue()); } }

7. Custom Comparator Examples

Advanced Comparator Usage

import java.util.*; public class TreeMapCustomComparators { static class Student { String name; double gpa; int age; public Student(String name, double gpa, int age) { this.name = name; this.gpa = gpa; this.age = age; } @Override public String toString() { return String.format("Student{name='%s', gpa=%.2f, age=%d}", name, gpa, age); } } public static void main(String[] args) { System.out.println("=== TreeMap with Custom Comparators ==="); // Comparator by GPA (descending) then name (ascending) Comparator<Student> byGpaThenName = Comparator .comparingDouble((Student s) -> s.gpa).reversed() .thenComparing(s -> s.name); TreeMap<Student, String> studentGrades = new TreeMap<>(byGpaThenName); studentGrades.put(new Student("Alice", 3.8, 20), "A"); studentGrades.put(new Student("Bob", 3.5, 21), "B+"); studentGrades.put(new Student("Charlie", 3.8, 22), "A"); studentGrades.put(new Student("Diana", 3.9, 20), "A"); studentGrades.put(new Student("Eve", 3.5, 19), "B+"); System.out.println("Students sorted by GPA (desc) then name (asc):"); studentGrades.forEach((student, grade) -> System.out.println(student + " -> Grade: " + grade)); // Case-insensitive string comparator TreeMap<String, Integer> caseInsensitiveMap = new TreeMap<>(String.CASE_INSENSITIVE_ORDER); caseInsensitiveMap.put("Apple", 1); caseInsensitiveMap.put("banana", 2); caseInsensitiveMap.put("BANANA", 3); // Will replace previous banana caseInsensitiveMap.put("Cherry", 4); System.out.println("\nCase-insensitive TreeMap:"); System.out.println(caseInsensitiveMap); System.out.println("Contains 'BANANA': " + caseInsensitiveMap.containsKey("banana")); // Multi-level comparator demonstrateMultiLevelComparator(); } public static void demonstrateMultiLevelComparator() { System.out.println("\n=== Multi-Level Comparator ==="); class Employee { String department; String role; String name; int salary; Employee(String department, String role, String name, int salary) { this.department = department; this.role = role; this.name = name; this.salary = salary; } @Override public String toString() { return String.format("Employee{dept='%s', role='%s', name='%s', salary=%d}", department, role, name, salary); } } // Sort by department, then role, then salary (desc), then name Comparator<Employee> complexComparator = Comparator .comparing((Employee e) -> e.department) .thenComparing(e -> e.role) .thenComparingInt((Employee e) -> e.salary).reversed() .thenComparing(e -> e.name); TreeMap<Employee, String> employeeMap = new TreeMap<>(complexComparator); employeeMap.put(new Employee("Engineering", "Developer", "John", 80000), "Senior"); employeeMap.put(new Employee("Engineering", "Manager", "Alice", 120000), "Lead"); employeeMap.put(new Employee("Sales", "Manager", "Bob", 90000), "Regional"); employeeMap.put(new Employee("Engineering", "Developer", "Carol", 75000), "Mid-level"); employeeMap.put(new Employee("Sales", "Representative", "David", 60000), "Junior"); employeeMap.put(new Employee("Engineering", "Developer", "Eve", 85000), "Senior"); System.out.println("Employees sorted by dept → role → salary(desc) → name:"); employeeMap.forEach((emp, level) -> System.out.println(emp + " -> Level: " + level)); } }

Summary

Key Features of TreeMap Sorted Keys:

1. Automatic Sorting: Keys are always maintained in sorted order
2. Red-Black Tree: Self-balancing binary search tree implementation
3. Custom Ordering: Supports natural ordering or custom comparators
4. Navigation Methods: Rich set of methods for key navigation
5. Range Operations: Efficient subMap, headMap, and tailMap operations

Time Complexity:

• put(): O(log n)
• get(): O(log n)
• remove(): O(log n)
• containsKey(): O(log n)
• firstKey()/lastKey(): O(log n)
• navigation operations: O(log n)

Use Cases:

1. Range queries: When you need to find entries within a key range
2. Sorted data: When you need data sorted by keys
3. Navigation: When you need ceiling, floor, higher, lower operations
4. Event scheduling: Time-based event management
5. Product catalogs: Categorized and sorted product listings

Best Practices:

1. Implement Comparable for custom objects used as keys
2. Use appropriate comparators for custom sorting logic
3. Consider memory overhead compared to HashMap
4. Use for range queries where sorting is beneficial
5. Avoid for simple key-value storage if sorting isn't needed

TreeMap provides powerful sorted key capabilities at the cost of slightly higher performance overhead compared to HashMap, making it ideal for use cases that require sorted data or range operations.