Introduction to TreeMap in Java
Introduction to TreeMap in Java
A TreeMap in Java is a sorted map implementation that uses a red-black tree as its underlying data structure. This means that the keys in a TreeMap are always kept in ascending order. TreeMaps are also self-balancing, which means that they can efficiently maintain their order even as new elements are added or removed.
TreeMaps are useful for a variety of applications, such as:
- Storing data in sorted order for efficient retrieval.
- Implementing priority queues and other data structures that require sorted keys.
- Creating caches and other data structures that need to be kept in order.
TreeMaps offer a number of advantages over other sorted map implementations, such as HashMaps. For example, TreeMaps have guaranteed log(n) time complexity for basic operations such as get, containsKey, and put. Additionally, TreeMaps provide a number of additional features, such as the ability to find the first, last, floor, and ceiling keys in the map.
To use a TreeMap, you first need to create a new instance of the class. You can optionally provide a Comparator to be used for sorting the keys in the map. If no Comparator is provided, the natural order of the keys will be used.
Once you have created a TreeMap, you can add and remove elements using the same methods as any other Map implementation. You can also retrieve elements from the map by key using the get() method.
TreeMaps also provide a number of additional methods for navigating the sorted order of the map. For example, you can use the firstKey() and lastKey() methods to find the smallest and largest keys in the map, respectively. You can also use the floorKey() and ceilingKey() methods to find the greatest key that is less than or equal to a given key, and the least key that is greater than or equal to a given key, respectively.
Overall, TreeMaps are a powerful and efficient data structure for storing data in sorted order. They are well-suited for a variety of applications, and they offer a number of advantages over other sorted map implementations.
Exercises
Code for declaring an TreeMap and inserting Key Value Pairs in the TreeMap.
The use of the following TreeMap Methods is demonstrated
- put
- size
- firstkey
- lastkey
- firstentry
- lastentry
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String> javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
System.out.println(javaclass.size());
System.out.println(javaclass.firstKey());
System.out.println(javaclass.lastKey());
System.out.println(javaclass.firstEntry());
System.out.println(javaclass.lastEntry());
}
}
Output
5
1
5
1=Ram
5=Mathew
Code for searching a key in the TreeMap
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String> javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
if(javaclass.containsKey(5))
{
System.out.println("Hey the key is available");
}
}
}
Output
Hey the key is available
Code for Searching a Value in a TreeMap
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String>>javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
if(javaclass.containsValue("Satish"))
{
System.out.println("Hey the Value is available");
}
}
}
output
Hey the Value is available Demo Code on the use of entryset method in TreeMap
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String> javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
System.out.println(javaclass.entrySet());
}
}
output
[1=Ram, 2=Satish, 3=Tom, 4=Chris, 5=Mathew]
Traversing a TreeMap and Printing all the Key Value Pairs
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String> javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
for(Map.Entry<Integer, String> element : javaclass.entrySet())
{
System.out.println(element.getKey()+" "+element.getValue());
}
}
}
output
1 Ram
2 Satish
3 Tom
4 Chris
5 Mathew Count the number of people whose names end with an m in a TreeMap.
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String> javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
int count=0;
for(Map.Entry<Integer, String> element : javaclass.entrySet())
{
if(element.getValue().endsWith("m"))
{
count++;
}
}
System.out.println("Total Number is "+count);
}
}
Output
Total Number is 2
Demo code for Keyset Method in TreeMap
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String> javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
System.out.println(javaclass.keySet());
}
}
output
[1, 2, 3, 4, 5]
Code demonstrating the use of DescendingMap Method in Java
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String> javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
System.out.println(javaclass.descendingMap());
}
}
output
{5=Mathew, 4=Chris, 3=Tom, 2=Satish, 1=Ram}
Code demonstrating the use of higherKey Method in TreeMap
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String> javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
System.out.println(javaclass.higherKey(2));
}
}
output
3
Code demonstrating the use of lowerKey Method in TreeMap
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String> javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
System.out.println(javaclass.lowerKey(3));
}
}
output
2
Code demonstrating the use of remove method in TreeMap
import java.util.Map;
import java.util.TreeMap;
public class demoClass{
public static void main(String args[]) {
TreeMap<Integer, String> javaclass = new TreeMap<Integer,String>();
javaclass.put(2, "Satish");
javaclass.put(1, "Ram");
javaclass.put(3, "Tom");
javaclass.put(5, "Mathew");
javaclass.put(4, "Chris");
javaclass.remove(2);
System.out.println(javaclass.keySet());
}
}
output
[1, 3, 4, 5] SubMap in TreeMap
A submap in a TreeMap is a dynamic view of a portion of the original map, defined by a range of keys. It allows you to work with a specific subset of the original map without creating a separate copy.
Key Points:
- Dynamic View: Any changes made to the submap are reflected in the original map and vice versa.
- Range Definition: You can specify a range of keys to define the submap.
- Efficiency: Operations on the submap are often more efficient than iterating over the entire original map.
How to Create a SubMap:
You can create a submap using the `subMap()` method of the TreeMap class. This method takes four arguments:
- fromKey: The lower bound of the submap (inclusive or exclusive).
- fromInclusive: Whether the lower bound is inclusive or exclusive.
- toKey: The upper bound of the submap (inclusive or exclusive).
- toInclusive: Whether the upper bound is inclusive or exclusive.
Here's an example:
public class bbsdemo {
public static void main(String[] args) throws IOException {
TreeMap students = new TreeMap();
students.put(1, "Satish");
students.put(2, "Ram");
students.put(3, "Tom");
students.put(4, "Mathew");
students.put(5, "Jeff");
SortedMap subMap = students.subMap(2, true, 4, true);
for (Map.Entry mapentry : subMap.entrySet()) {
System.out.println(mapentry.getKey() + " " + mapentry.getValue());
}
}
}
Output
2 Ram
3 Tom
4 Mathew
In this example, the submap will contain entries with keys 2, 3 and 4. Any changes made to the submap will also affect the original map.
Common Use Cases:
- Filtering Data: Extracting a specific subset of data based on key ranges.
- Iterating Over Specific Ranges: Iterating through a specific portion of the map.
- Performing Operations on Subsets: Applying operations like sorting, filtering, or mapping to specific key ranges.
By understanding and effectively using submaps, you can efficiently work with specific portions of your TreeMap data, improving performance and code readability.