Java TreeMap Data Structure

Introduction

The TreeMap class in Java is a part of the Java Collection Interface and implements the Map interface. It stores the key-value pairs in a sorted order unlike other Map implementations. In this lab, you will learn how to use the TreeMap class effectively in your Java programs.

Skills Graph

Creating a TreeMap

• Open your text editor and create a new file called TreeMapDemo.java in the ~/project directory.
• Import the required packages:

import java.util.Map;
import java.util.TreeMap;

• Create a TreeMap object:

Map<Integer, String> map = new TreeMap<>();

Adding Elements to the TreeMap

• Use the put() method to add elements to the TreeMap:

map.put(1, "John");
map.put(2, "Mary");
map.put(3, "Peter");

Add these code inside the main method.

Printing the TreeMap

• Use a for-each loop to iterate through the TreeMap:

for(Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}

Using Custom Sorting

• Create a new class called Employee:

class Employee implements Comparable<Employee> {
    private int id;
    private String name;

    public Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    @Override
    public int compareTo(Employee e) {
        return this.id - e.getId();
    }
}

• Add some Employees to the TreeMap:

Map<Employee, String> employeeMap = new TreeMap<>();
employeeMap.put(new Employee(3, "John"), "IT");
employeeMap.put(new Employee(2, "Mary"), "HR");
employeeMap.put(new Employee(1, "Peter"), "Finance");

• Now when you iterate through the TreeMap, it will be sorted based on the employee ID:

for(Map.Entry<Employee, String> entry : employeeMap.entrySet()) {
    System.out.println(entry.getKey().getId() + " "
                       + entry.getKey().getName() + " "
                       + entry.getValue());
}

Using Comparators for Sorting

• Define a custom Comparator in your TreeMapDemo class:

class DescendingOrder implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}

• Create a new TreeMap object with the custom Comparator:

Map<Integer, String> treeMap = new TreeMap<>(new DescendingOrder());
treeMap.put(1, "John");
treeMap.put(4, "Mary");
treeMap.put(2, "Peter");

• Now when you iterate through the TreeMap, it will be sorted in descending order:

for(Map.Entry<Integer, String> entry : treeMap.entrySet()) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}

Accessing Map Elements

• Use the get() method to access a specific element:

String name = map.get(1);
System.out.println("Name is " + name);

Removing Map Elements

• Use the remove() method to remove a specific element:

String removedName = map.remove(2);
System.out.println("Removed: " + removedName);

Retrieving Map Size

• Use the size() method to get the number of elements in the TreeMap:

int size = map.size();
System.out.println(size);

Retrieving First and Last Elements

• Use the firstKey() and lastKey() methods to retrieve the first and last elements in the TreeMap:

int firstKey = map.firstKey();
int lastKey = map.lastKey();

Retrieving a Range of Elements

• Use the subMap() method to retrieve a range of elements:

Map<Integer, String> rangeMap = map.subMap(1, 3);
for(Map.Entry<Integer, String> entry : rangeMap.entrySet()) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}

Compile and Run the Program

• Open your terminal and navigate to the ~/project directory.
• Compile the TreeMapDemo.java file using the javac command:

javac TreeMapDemo.java

• Run the program using the java command:

java TreeMapDemo

Summary

In this lab, you learned about the TreeMap class in Java and how to use it effectively in your programs. You learned how to create a TreeMap, add and remove elements, and retrieve elements based on specific criteria. You also learned how to customize the sorting order using Comparators. The TreeMap class provides a lot of flexibility and control over the sorting and storage of key-value pairs.