> For the complete documentation index, see [llms.txt](https://www.pranaypourkar.co.in/the-programmers-guide/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.pranaypourkar.co.in/the-programmers-guide/java/java-basics/java-data-types/non-primitive-reference-types/collections/map/treemap.md). # TreeMap ## **About** `TreeMap` is a part of the Java Collections Framework under the `java.util` package. It implements the `NavigableMap`interface and extends `AbstractMap`. Internally, it uses a self-balancing **Red-Black Tree** to store key-value pairs, maintaining the natural order of keys or a custom order defined by a `Comparator`. `TreeMap` is particularly useful when ordered traversal or range queries are needed. ## **Features** 1. **Sorted Order**: Keys are sorted either by their natural order or a provided `Comparator`. 2. **NavigableMap Interface**: Supports navigation methods such as `lowerKey`, `higherKey`, `floorKey`, and `ceilingKey`. 3. **Thread-Safe Alternative**: `TreeMap` is not thread-safe; for concurrent access, use `Collections.synchronizedMap()` or a `ConcurrentSkipListMap`. 4. **Allows Null Values**: Values can be `null`, but keys cannot be `null` (throws `NullPointerException`). 5. **Efficient Range Operations**: Provides sub-map views using methods like `subMap`, `headMap`, and `tailMap` ## Internal Working ### **Red-Black Tree** 1. **Structure**: * A Red-Black Tree is a self-balancing binary search tree. * Each node contains a key, a value, references to left and right children, a parent pointer, and a color (either red or black). 2. **Properties of Red-Black Tree**: * **Property 1**: Every node is either red or black. * **Property 2**: The root is always black. * **Property 3**: Red nodes cannot have red children (no two consecutive red nodes). * **Property 4**: Every path from a node to its descendant leaves has the same number of black nodes (black-height). 3. **Tree Operations**: * **Insertion**: Adds a new node, initially red. If it violates any property, the tree is restructured using rotations and recoloring. * **Deletion**: Removes a node. If it disrupts balance, fixes are applied to maintain Red-Black Tree properties. * **Balancing**: Rotations (left and right) are used to maintain balance. 4. **Node Comparison**: * Keys are compared using their natural ordering (`Comparable`) or a custom `Comparator`. * The comparison determines where to place a new node and ensures sorted order. ### **How TreeMap Works** 1. **Storage**: * The map stores entries (`Map.Entry`) as nodes in a Red-Black Tree. * Each node contains `key`, `value`, `left`, `right`, `parent`, and `color`. 2. **Adding an Entry (`put()` method)**: * Starts at the root and traverses the tree based on the key's comparison result. * Places the entry in its correct position and then balances the tree. 3. **Removing an Entry (`remove()` method)**: * Locates the node by key and removes it. * If the node has two children, replaces it with its in-order successor and then fixes the tree balance. 4. **Searching (`get()` method)**: * Starts at the root and traverses left or right based on the key comparison until the key is found or the traversal ends. 5. **Iteration**: * In-order traversal of the Red-Black Tree ensures the keys are retrieved in sorted order. ## **Key Methods**
MethodDescription
put(K key, V value)Associates the specified value with the specified key, balancing the tree if necessary.
get(Object key)Retrieves the value associated with the specified key.
remove(Object key)Removes the mapping for the specified key.
firstKey()Returns the smallest key in the map.
lastKey()Returns the largest key in the map.
subMap(K fromKey, K toKey)Returns a view of the portion of the map whose keys range from fromKey to toKey.
headMap(K toKey)Returns a view of the portion of the map whose keys are less than toKey.
tailMap(K fromKey)Returns a view of the portion of the map whose keys are greater than or equal to fromKey.
ceilingKey(K key)Returns the smallest key greater than or equal to the given key.
floorKey(K key)Returns the largest key less than or equal to the given key.
## **Big-O for Operations** | **Operation** | **Average Case** | **Worst Case** | | ------------- | ---------------- | -------------- | | **Put** | O(log n) | O(log n) | | **Get** | O(log n) | O(log n) | | **Remove** | O(log n) | O(log n) | | **Iteration** | O(n) | O(n) | ## **Limitations** 1. **No Null Keys**: Unlike `HashMap`, `TreeMap` does not support `null` keys. 2. **Not Thread-Safe**: Needs external synchronization for concurrent access. 3. **Higher Overhead**: The tree structure incurs more memory overhead compared to hash-based maps. ## **Real-World Usage** 1. **Range Queries**: Efficient for applications requiring range-based queries, such as databases and scheduling systems. 2. **Sorted Data**: Ideal for scenarios where keys must remain sorted, like navigation menus or ranking systems. 3. **Custom Order**: Used when a custom order is required, such as case-insensitive string comparisons. ## **Examples** ### **1. Basic Operations** ```java import java.util.TreeMap; public class TreeMapExample { public static void main(String[] args) { TreeMap treeMap = new TreeMap<>(); // Adding elements treeMap.put(3, "Alice"); treeMap.put(1, "Bob"); treeMap.put(2, "Charlie"); System.out.println(treeMap); // Output: {1=Bob, 2=Charlie, 3=Alice} // Accessing elements System.out.println("Value for key 2: " + treeMap.get(2)); // Output: Value for key 2: Charlie // Removing an element treeMap.remove(1); System.out.println(treeMap); // Output: {2=Charlie, 3=Alice} } } ``` ### **2. Range Queries** ```java import java.util.TreeMap; public class RangeQueryExample { public static void main(String[] args) { TreeMap treeMap = new TreeMap<>(); treeMap.put(10, "Ten"); treeMap.put(20, "Twenty"); treeMap.put(30, "Thirty"); // Getting a sub-map System.out.println(treeMap.subMap(15, 25)); // Output: {20=Twenty} // Getting the ceiling and floor keys System.out.println(treeMap.ceilingKey(15)); // Output: 20 System.out.println(treeMap.floorKey(25)); // Output: 20 } } ``` ### **3. Custom Comparator** ```java import java.util.TreeMap; public class CustomOrderExample { public static void main(String[] args) { TreeMap treeMap = new TreeMap<>((s1, s2) -> s2.compareTo(s1)); // Adding elements in reverse order treeMap.put("Alice", 1); treeMap.put("Bob", 2); treeMap.put("Charlie", 3); System.out.println(treeMap); // Output: {Charlie=3, Bob=2, Alice=1} } } ``` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://www.pranaypourkar.co.in/the-programmers-guide/java/java-basics/java-data-types/non-primitive-reference-types/collections/map/treemap.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.