Clase Java TreeMap | W3Docs Learn Java

Qué es un TreeMap

TreeMap<K, V> es el Map que mantiene sus claves ordenadas. Internamente es un árbol rojo-negro — el mismo árbol binario de búsqueda autoequilibrado que respalda a TreeSet — y cada operación es O(log n): put, get, remove, la primera clave, la última clave, consultas de rango. La compensación por el costo logarítmico es la API de navegación de NavigableMap<K, V>: floor, ceiling, lower, higher, sub-map, head-map, tail-map y vistas en orden inverso. Ninguna de esas es posible sobre una tabla hash sin un ordenamiento completo previo.

Si alguna vez te encuentras haciendo new TreeMap<>(hashMap) al final de una función para "ordenar las entradas," esa es la señal de que TreeMap debería haber sido el tipo desde el principio.

Dos formas de definir el orden de las claves

Un TreeMap necesita comparar claves de alguna manera. Como con TreeSet:

Orden natural — el tipo de clave implementa Comparable<K>. Las cadenas de texto, envoltorios numéricos, fechas y tus propios tipos record que implementan Comparable son válidos.
Un Comparator<K> pasado al constructor — úsalo cuando el orden natural no existe o no coincide con lo que deseas. (Consulta Comparable vs Comparator para ver cómo difieren los dos.)

Map<String, Integer> byName    = new TreeMap<>();                        // case-sensitive natural
Map<String, Integer> byNameCi  = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
Map<String, Integer> reverse   = new TreeMap<>(Comparator.reverseOrder());

Como con TreeSet, la igualdad se basa en compareTo que devuelve 0, no en equals. Dos claves que el comparador considera iguales se colapsan en una sola entrada — el segundo put sobreescribe el primero. Con claves usando String.CASE_INSENSITIVE_ORDER, al insertar "Java" y luego "JAVA" quedarás con una sola entrada cuya clave es el "Java" original y cuyo valor es el del segundo put. Eso casi nunca es lo que quieres por accidente.

La API NavigableMap

La interfaz que implementa un TreeMap te proporciona muchas operaciones que un Map ordinario no ofrece:

TreeMap<Integer, String> t = new TreeMap<>();
t.put(10, "a"); t.put(20, "b"); t.put(30, "c"); t.put(40, "d");

t.firstKey();        // 10
t.lastKey();         // 40
t.firstEntry();      // 10=a
t.pollFirstEntry();  // 10=a, removes
t.lowerKey(30);      // 20 — strictly less
t.floorKey(30);      // 30 — ≤
t.higherKey(30);     // 40 — strictly greater
t.ceilingKey(30);    // 30 — ≥
t.headMap(30);       // {10=a, 20=b}  — keys strictly < 30
t.tailMap(30);       // {30=c, 40=d}  — keys ≥ 30
t.subMap(20, 40);    // {20=b, 30=c}  — [20, 40)
t.descendingMap();   // reverse-order view

Por eso existe TreeMap. "Encuentra el evento más cercano antes de las 9 a.m." es headMap(9am).lastEntry() — una búsqueda en tiempo logarítmico. La misma operación sobre un HashMap tendría que recorrer todas las claves.

Las vistas de sub-mapas son vivas

subMap, headMap y tailMap devuelven vistas del mapa original — no copias. Los cambios realizados a través de la vista se propagan de vuelta, y los cambios en el original que caen dentro del rango de la vista aparecen en la vista. Las vistas también imponen el rango: intentar insertar una clave fuera del rango a través de la vista lanza IllegalArgumentException. Así es como la iteración acotada por rango se mantiene segura incluso cuando se muta durante el recorrido.

TreeMap<Integer, String> t = new TreeMap<>();
t.put(10, "a"); t.put(20, "b"); t.put(30, "c");
NavigableMap<Integer, String> mid = t.subMap(15, true, 25, true);
mid.put(20, "updated");   // OK — 20 is in range
// mid.put(40, "x");       // would throw — 40 is out of range
System.out.println(t);     // {10=a, 20=updated, 30=c}

Null es rechazado (para claves)

No puedes tener una clave null en un TreeMap por la misma razón que TreeSet las rechaza: no hay una forma sensata de llamar a compareTo sobre null. El primer put(null, ...) lanza NullPointerException. Los valores null son válidos.

Cuándo elegir `TreeMap`

Flujo de decisión:

Necesitas iteración ordenada por clave o consultas de rango sobre claves → TreeMap. Es la única opción.
Necesitas búsqueda rápida y el orden no importa → HashMap. O(1) gana.
Necesitas búsqueda rápida y iteración en orden de inserción → LinkedHashMap.
El tipo de clave es un enum → EnumMap. Más rápido que TreeMap y con orden natural.

Los cuatro implementan el mismo contrato Map, así que cambiar entre ellos suele ser un cambio de constructor en una sola línea.

Un patrón útil: usa un HashMap para construir el mapa rápidamente, luego new TreeMap<>(hashMap) una sola vez para presentar una vista ordenada al final. Construir rápido, presentar ordenado.

Un ejemplo práctico: búsqueda en agenda, consultas de rango, clave con comparador

El programa a continuación usa un TreeMap para modelar una pequeña "agenda de eventos" indexada por minutos desde medianoche. Demuestra la API de navegación para "cuál es el próximo evento después de X" y "todo antes de Y," muestra la vista de sub-mapa en vivo, y revela la trampa de la igualdad por comparador con un mapa sin distinción de mayúsculas.

java— editable, runs on the server

import java.util.*;

public class TreeMapShowcase {
  public static void main(String[] args) {
    // --- A schedule keyed by minutes-since-midnight ---
    TreeMap<Integer, String> schedule = new TreeMap<>();
    schedule.put( 9 * 60,     "standup");
    schedule.put(10 * 60 + 30, "design review");
    schedule.put(13 * 60,     "lunch with team");
    schedule.put(16 * 60,     "demo");
    schedule.put(18 * 60,     "ship");
    System.out.println("schedule (sorted by key):");
    schedule.forEach((k, v) ->
        System.out.println("  " + (k / 60) + ":" + String.format("%02d", k % 60) + "  " + v));

int now = 11 * 60 + 0;
    System.out.println("\nat 11:00...");
    System.out.println("  next event:           " + schedule.ceilingEntry(now));
    System.out.println("  most recent past:     " + schedule.lowerEntry(now));

// --- Morning slice: live view ---
    NavigableMap<Integer, String> morning = schedule.headMap(12 * 60, false);
    System.out.println("\nmorning (key < 12:00):  " + morning);
    schedule.put(11 * 60 + 30, "coffee");      // falls in the morning range
    System.out.println("after adding coffee at 11:30:");
    System.out.println("  morning view:  " + morning);  // reflects the new entry

// --- pollFirstEntry: priority-queue-like draining ---
    System.out.println("\ndraining in time order:");
    while (!schedule.isEmpty()) {
      Map.Entry<Integer, String> next = schedule.pollFirstEntry();
      System.out.println("  " + (next.getKey() / 60) + ":"
          + String.format("%02d", next.getKey() % 60) + "  " + next.getValue());
    }

// --- The comparator-equality trap ---
    TreeMap<String, Integer> ci = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
    ci.put("Java", 1);
    ci.put("JAVA", 2);     // comparator says equal → overwrites value, keeps original key
    System.out.println("\ncase-insensitive: " + ci);
  }
}

Lo que extraer de la ejecución:

La agenda se imprime en orden cronológico sin ningún ordenamiento explícito. Al agregar "coffee" a las 11:30 se insertó en el lugar correcto automáticamente.
Consultamos a las 11:00. ceilingEntry(11*60) devuelve la siguiente entrada a partir de las 11:00, que es el almuerzo de las 13:00 (la revisión de diseño de las 10:30 es antes de las 11:00, por lo que no califica). lowerEntry(11*60) devuelve la entrada más reciente estrictamente antes de las 11:00, la revisión de diseño de las 10:30. Ambas son O(log n).
El sub-mapa morning es una vista en vivo — coffee apareció en él después de insertarlo en el mapa original. Si hubiéramos puesto "midnight snack" a las 23:00, la vista lo habría ignorado (fuera del rango).
pollFirstEntry drenó repetidamente el próximo evento. Eso es una cola de prioridad pobre cuando también quieres búsquedas por clave, lo que una PriorityQueue real no puede darte.
El mapa sin distinción de mayúsculas colapsó "Java" y "JAVA" en una sola entrada — con la clave original "Java" pero con el valor del segundo put 2. Igualdad por comparador, no por equals.

Qué sigue

Las cuatro implementaciones modernas de mapa — HashMap, LinkedHashMap, TreeMap y ConcurrentHashMap — son las que debes usar en código nuevo. Hay una más en el JDK que las precede a todas y que aún verás ocasionalmente en código antiguo: Hashtable. Vale la pena saber por qué existe, por qué casi siempre es la elección incorrecta hoy, y cómo reemplazarla.

Práctica

Un `TreeMap<Integer, String>` contiene las claves `10, 20, 30, 40`. ¿Qué devuelve `tree.floorKey(25)`?

`20` — la clave más grande que es menor o igual a 25`30` — la clave más pequeña que es mayor o igual a 25`25` — la clave se inserta con un valor null y se devuelve`null` — `floorKey` solo devuelve una clave cuando hay una coincidencia exacta en el mapa