Deep Dive into Java TreeMap: Structure, Red‑Black Tree, and Core Operations

1. TreeMap Overview

TreeMap stores key‑value pairs using a red‑black tree, implements NavigableMap and SortedMap , and supports cloning and serialization. By default it orders entries according to the natural ordering of keys.

2. Red‑Black Tree Review

The red‑black tree guarantees balanced height through five rules: each node is red or black, the root is black, leaves are black nulls, red nodes cannot have red children, and every path from a node to its descendant leaves contains the same number of black nodes.

Balancing operations include recoloring, left rotation, and right rotation.

3. TreeMap Construction

The class defines several key fields:

private final Comparator
comparator;
private transient Entry
root;
private transient int size = 0;
private transient int modCount = 0;

The inner static class Entry<K,V> stores key, value, left/right child references, parent reference, and node color, and implements Map.Entry<K,V> with standard methods such as getKey , getValue , setValue , equals , hashCode , and toString .

4. put Method

The put method inserts a new entry or updates an existing one. It first searches for the correct position using either a custom Comparator or the key's natural ordering, creates a new Entry , links it as a left or right child, and then calls fixAfterInsertion to restore red‑black properties.

public V put(K key, V value) {
    // search logic omitted for brevity
    Entry
e = new Entry<>(key, value, parent);
    if (cmp < 0) parent.left = e; else parent.right = e;
    fixAfterInsertion(e);
    size++; modCount++; return null;
}

5. get Method

The get method performs a binary search from the root, using either the supplied comparator or the key's compareTo method, and returns the associated value or null if the key is absent.

public V get(Object key) {
    Entry
p = getEntry(key);
    return (p == null) ? null : p.value;
}

6. remove Method

The remove method locates the entry, stores its value, and delegates the structural deletion to deleteEntry , which handles four cases (removing the root, leaf nodes, nodes with one child, and nodes with two children) and then invokes fixAfterDeletion to rebalance the tree.

public V remove(Object key) {
    Entry
p = getEntry(key);
    if (p == null) return null;
    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

7. Traversal

TreeMap can be traversed via map.values() , map.keySet() , map.entrySet() , or map.forEach .

8. Summary

The article provides a comprehensive explanation of TreeMap's characteristics, its red‑black tree foundation, automatic sorting logic, and detailed source‑code walkthroughs of the core methods, helping readers understand both the API usage and the underlying self‑balancing mechanisms.