TreeMap in Java (Red-Black Tree Concept Introduction)

In Java, collections play a very important role in storing and managing data efficiently. One such powerful collection is TreeMap. It is part of the java.util package and is widely used when we need to store data in sorted key-value pairs.

What makes TreeMap special is that it is internally based on a Red-Black Tree, a self-balancing binary search tree.

we will understand what TreeMap is, how it works, and learn the basic concept of Red-Black Tree in a simple way.

---

What is TreeMap in Java?

A TreeMap is a class in Java that stores data in the form of key-value pairs in a sorted order based on keys.

👉 In simple words:
TreeMap = A map that automatically sorts keys.

---

Syntax:

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

---

Example:

import java.util.*;public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();        map.put(3, "Apple");
        map.put(1, "Banana");
        map.put(2, "Mango");        System.out.println(map);
    }
}

Output:

{1=Banana, 2=Mango, 3=Apple}

Here, keys are automatically sorted.

---

Features of TreeMap

• Stores data in sorted order of keys
• Does not allow null keys
• Allows multiple null values
• Implements NavigableMap interface
• Uses Red-Black Tree internally

---

What is a Red-Black Tree?

A Red-Black Tree is a type of self-balancing binary search tree used to maintain sorted data efficiently.

It is a smart tree that keeps itself balanced so operations remain fast.

---

Why TreeMap Uses Red-Black Tree?

If a normal binary search tree becomes unbalanced, operations become slow (like linked list performance).

Red-Black Tree solves this problem by ensuring:

• Balanced structure
• Fast insertion
• Fast deletion
• Fast searching

So, TreeMap uses Red-Black Tree to maintain O(log n) time complexity for operations.

---

Properties of Red-Black Tree

A Red-Black Tree follows some important rules:

1. Each node is either Red or Black

Every node has a color property.

---

2. Root is always Black

The top node of the tree must be black.

---

3. No two Red nodes together

A red node cannot have a red parent or red child.

---

4. Equal Black Height

Every path from root to leaf has the same number of black nodes.

---

5. Leaf nodes are Black (NULL nodes)

All empty nodes are considered black.

---

How TreeMap Works Internally

When you insert elements into TreeMap:

1. The key is placed like in a Binary Search Tree
2. The tree checks balance rules
3. If imbalance occurs, it performs rotations and recoloring
4. Tree remains balanced

This ensures efficient performance even with large data.

---

TreeMap Operations Complexity

Operation	Time Complexity
Insert	O(log n)
Delete	O(log n)
Search	O(log n)

This is better than unbalanced trees.

---

Example: TreeMap Operations

import java.util.*;public class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>();        map.put("Orange", 3);
        map.put("Apple", 1);
        map.put("Banana", 2);        System.out.println("Original Map: " + map);        System.out.println("First Key: " + map.firstKey());
        System.out.println("Last Key: " + map.lastKey());
    }
}

---

Advantages of TreeMap

• Automatically sorted data
• Efficient searching and insertion
• No duplicate keys allowed
• Useful for range-based operations

---

Disadvantages of TreeMap

• Slower than HashMap for simple operations
• Does not allow null keys
• More memory usage due to tree structure

---

TreeMap vs HashMap

Feature	TreeMap	HashMap
Order	Sorted	Unordered
Structure	Red-Black Tree	Hash Table
Speed	O(log n)	O(1) average
Null Key	Not allowed	Allowed

---

Real-Life Use of TreeMap

TreeMap is used in:

• Leaderboards (sorted scores)
• Dictionary applications
• Event scheduling systems
• Banking transaction sorting
• Analytics dashboards

---

TreeMap is a powerful Java collection that stores data in sorted order using a Red-Black Tree internally. This self-balancing structure ensures efficient performance even with large datasets.

Understanding TreeMap helps in mastering advanced Java collections and data structures. It is widely used in real-world applications where sorting and fast searching are important.

By learning TreeMap and Red-Black Tree concepts, you take an important step toward becoming a strong Java programmer.

For More Information and Updates, Connect With Us

• Name Sumit singh
• Phone Number: +91-9264477176
• Email ID: emancipationedutech@gmail.com
• Our Platforms:
• Digilearn Cloud
• Live Emancipation
• Follow Us on Social Media:
• Instagram – Emancipation
• Facebook – Emancipation

Stay connected and keep learning with Emancipation!