Internal Working of TreeMap in Java

Introduction

A TreeMap in Java is a part of the java.util package and is used to store key-value pairs in sorted order based on the natural ordering of keys or a custom comparator. Unlike HashMap, which provides constant-time performance (O(1)) for basic operations, TreeMap provides logarithmic time complexity (O(log n)) as it is implemented using a Red-Black Tree.

---

1. Data Structure Used

A TreeMap is implemented as a Red-Black Tree, a self-balancing binary search tree that ensures efficient performance for operations like insertion, deletion, and retrieval.

Implementation in Java:

static final class Entry<K,V> extends AbstractMap.SimpleEntry<K,V> {
    Entry<K,V> left, right, parent;
    boolean color;
}

Each node (Entry) in the TreeMap contains:

• Key and Value
• Pointers to left and right child nodes
• Pointer to parent node
• Color attribute (Red or Black) for Red-Black Tree balancing

---

2. How Elements are Stored

When a key-value pair is inserted into a TreeMap, the following steps occur:

1. Binary Search Tree Insertion:
   • The key is compared with existing keys to determine its position.
   • The tree is traversed left or right based on key comparison.
2. Red-Black Tree Balancing:
   • After insertion, the Red-Black Tree properties are maintained.
   • If a violation occurs (e.g., consecutive red nodes), rotations and color changes are performed to rebalance the tree.

Example:

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Banana", 2);
treeMap.put("Apple", 1);
treeMap.put("Cherry", 3);
System.out.println(treeMap); // Output: {Apple=1, Banana=2, Cherry=3} (sorted order)

---

3. Red-Black Tree and Its Role in TreeMap

A TreeMap is implemented as a Red-Black Tree, which ensures that the tree remains balanced.

Red-Black Tree Properties:

1. Every node is either red or black.
2. The root node is always black.
3. No two consecutive red nodes appear in a path.
4. Every path from the root to a leaf has the same number of black nodes.
5. Balancing operations (rotations and color flips) ensure O(log n) complexity.

Why Red-Black Tree?

• Balanced structure: Ensures that the height of the tree remains O(log n).
• Efficient retrieval: Searching is O(log n) instead of O(n) in an unbalanced tree.
• Predictable ordering: Since elements are always sorted, iteration is efficient.

---

4. Accessing Elements from TreeMap

Unlike HashMap, a TreeMap maintains elements in sorted order, allowing ordered traversal.

Retrieving a Value

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Apple", 1);
treeMap.put("Banana", 2);
System.out.println(treeMap.get("Apple")); // Output: 1

First and Last Entry

System.out.println(treeMap.firstEntry()); // Output: Apple=1
System.out.println(treeMap.lastEntry()); // Output: Banana=2

Submaps (Range Queries)

System.out.println(treeMap.subMap("Apple", "Cherry")); // Output: {Apple=1, Banana=2}

---

5. What Happens When a Duplicate Key is Added?

• If the same key is added again, TreeMap.put() replaces the old value with the new one.
• The tree remains balanced.

Example:

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Apple", 1);
treeMap.put("Apple", 2); // Replaces previous value
System.out.println(treeMap.get("Apple")); // Output: 2

---

6. Performance Comparison: TreeMap vs. HashMap

Operation	TreeMap (O(log n))	HashMap (O(1))
Insertion	Slower	Faster
Lookup	Slower	Faster
Deletion	Slower	Faster
Ordered?	Yes (sorted keys)	No
Iteration	Faster (sorted order)	Unordered

---

7. Key Takeaways

✔ TreeMap stores key-value pairs in sorted order.

✔ Uses a Red-Black Tree, ensuring O(log n) operations.

✔ Provides ordered traversal and range queries.

✔ Allows retrieving the first, last, and submaps easily.

✔ If a duplicate key is added, the old value is replaced.

✔ Slower than HashMap but useful when ordering is required.

Understanding the internal working of TreeMap helps in choosing the right data structure based on ordering requirements and performance constraints.