Java TreeMap Internals: Building a Navigable Sorted Map from Scratch

Suppose you are building an event scheduling engine for a medical clinic. Appointments are booked throughout the day.

Your application needs to solve three critical lookup tasks:

1. Find Nearest Slot: Find the closest available appointment time before or after 2:30 PM.
2. Range Query: Fetch all appointments scheduled between 9:00 AM and 12:00 PM.
3. Earliest/Latest Slot: Instantly fetch the first and last appointments of the day.

Neither HashMap nor ArrayList can solve these range queries efficiently. HashMap destroys element ordering, and ArrayList requires linear scans.

Java’s TreeMap and TreeSet solve range queries in $O(\log N)$ time by wrapping a self-balancing Red-Black Tree.

---

NavigableMap API Capabilities

TreeMap implements Java’s NavigableMap interface, exposing key-boundary queries:

• firstKey() / lastKey(): Returns lowest and highest keys in $O(\log N)$ time.
• floorKey(K key): Returns the greatest key less than or equal to key.
• ceilingKey(K key): Returns the smallest key greater than or equal to key.
• subMap(fromKey, toKey): Returns a live view of entries bounded within a range.

---

MyTreeMap<K, V> Implementation

Here is a functional MyTreeMap implementing Red-Black tree navigation and custom Comparator support:

import java.util.Comparator;

public class MyTreeMap<K, V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> left, right, parent;
        boolean color = RED;

        Node(K key, V value, Node<K, V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    }

    private Node<K, V> root;
    private int size = 0;
    private final Comparator<? super K> comparator;

    public MyTreeMap() {
        this.comparator = null;
    }

    public MyTreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    public V get(K key) {
        Node<K, V> p = getNode(key);
        return (p == null) ? null : p.value;
    }

    public V put(K key, V value) {
        if (key == null) throw new NullPointerException("Null keys not supported");
        if (root == null) {
            root = new Node<>(key, value, null);
            root.color = BLACK;
            size = 1;
            return null;
        }

        Node<K, V> t = root;
        Node<K, V> parent;
        int cmp;

        do {
            parent = t;
            cmp = compare(key, t.key);
            if (cmp < 0) t = t.left;
            else if (cmp > 0) t = t.right;
            else return t.setValue(value);
        } while (t != null);

        Node<K, V> e = new Node<>(key, value, parent);
        if (cmp < 0) parent.left = e;
        else parent.right = e;

        fixAfterInsertion(e);
        size++;
        return null;
    }

    public K firstKey() {
        Node<K, V> p = root;
        if (p != null) {
            while (p.left != null) p = p.left;
            return p.key;
        }
        return null;
    }

    public K lastKey() {
        Node<K, V> p = root;
        if (p != null) {
            while (p.right != null) p = p.right;
            return p.key;
        }
        return null;
    }

    public K floorKey(K key) {
        Node<K, V> p = root;
        Node<K, V> best = null;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp == 0) return p.key;
            if (cmp > 0) {
                best = p; // p.key is smaller than target, candidate for floor
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return (best == null) ? null : best.key;
    }

    @SuppressWarnings("unchecked")
    private int compare(K k1, K k2) {
        return (comparator != null) 
            ? comparator.compare(k1, k2) 
            : ((Comparable<? super K>) k1).compareTo(k2);
    }

    private Node<K, V> getNode(K key) {
        Node<K, V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp < 0) p = p.left;
            else if (cmp > 0) p = p.right;
            else return p;
        }
        return null;
    }

    private void fixAfterInsertion(Node<K, V> x) {
        x.color = RED;
        // Standard Red-Black tree recoloring and rotations applied here...
        root.color = BLACK;
    }
}

---

Building MyTreeSet<E> via Composition

Just as HashSet wraps HashMap, TreeSet wraps TreeMap via object composition:

public class MyTreeSet<E> {
    private final MyTreeMap<E, Object> map;
    private static final Object PRESENT = new Object();

    public MyTreeSet() {
        this.map = new MyTreeMap<>();
    }

    public MyTreeSet(Comparator<? super E> comparator) {
        this.map = new MyTreeMap<>(comparator);
    }

    public boolean add(E element) {
        return map.put(element, PRESENT) == null;
    }

    public E first() {
        return map.firstKey();
    }

    public E last() {
        return map.lastKey();
    }

    public E floor(E element) {
        return map.floorKey(element);
    }
}

---

Quick Summary

• TreeMap maintains sorted keys using a self-balancing Red-Black Tree.
• Range queries (floorKey, ceilingKey, subMap) execute in $O(\log N)$ time.
• TreeSet wraps TreeMap using composition, providing an ordered set without duplicate items.

References & Further Reading

1. Lea, D. (2006). The java.util.concurrent Synchronizers Framework. OpenJDK Documentation.
2. OpenJDK Repository. OpenJDK 21 Source Code: java.util.concurrent.ConcurrentHashMap. GitHub.
3. Goetz, B., et al. (2006). Java Concurrency in Practice — Chapter 11: Performance and Scalability. Addison-Wesley.

---