Java TreeSet

TreeSet<E> es la implementación de Set que mantiene sus elementos ordenados. Está respaldada por un árbol rojo-negro (el mismo árbol de búsqueda binaria balanceado que respalda a TreeMap internamente), por lo que cada operación — add, remove, contains, first, last, consultas de rango — es O(log n). Eso es más lento que el O(1) de HashSet, pero se obtiene algo que HashSet no puede ofrecer: un iterador ordenado, el elemento más pequeño a demanda, y la posibilidad de preguntar "todas las etiquetas entre a y m".

TreeSet implementa la interfaz más rica NavigableSet<E> (que extiende SortedSet<E>), por lo que todas las consultas de rango y de vecinos están en la propia clase, no escondidas en los helpers de Collections. Si aún no conoces el contrato base, lee primero el capítulo de la interfaz Set — todo lo que se explica allí (sin duplicados, add devuelve false en una repetición) sigue siendo válido.

Dos formas de definir el orden

Un TreeSet necesita alguna forma de comparar elementos. Hay dos:

1. Orden natural — el tipo de elemento implementa Comparable<E>. String, Integer, LocalDate, todos los wrappers, todos los enums, cualquier record que escribas que implemente Comparable. El constructor sin argumentos new TreeSet<>() utiliza este orden.
2. Un Comparator<E> que tú proporcionas — pásalo al constructor. El conjunto usa tu comparador para cada comparación.

Set<String> caseInsensitive = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.add("Banana");
caseInsensitive.add("apple");
caseInsensitive.add("BANANA");   // equals "Banana" by this comparator → not added
System.out.println(caseInsensitive); // [apple, Banana]

El segundo ejemplo es importante. TreeSet decide "igual" por compareTo que devuelve 0, no por equals. Dos cadenas que el orden natural dice que son diferentes pero que un comparador dice que son iguales colapsarán en un único elemento. Eso es casi siempre lo que se quiere — pero es un caso límite si no te habías dado cuenta.

La API NavigableSet

Un TreeSet expone operaciones que un Set simple no puede:

TreeSet<Integer> t = new TreeSet<>(List.of(10, 20, 30, 40, 50));
t.first();          // 10  — smallest
t.last();           // 50  — largest
t.lower(30);        // 20  — strictly less than 30
t.floor(30);        // 30  — ≤ 30
t.higher(30);       // 40  — strictly greater than 30
t.ceiling(30);      // 30  — ≥ 30
t.pollFirst();      // 10, removes
t.pollLast();       // 50, removes
t.headSet(30);      // {10, 20}        — strictly less than 30
t.tailSet(30);      // {30, 40, 50}    — ≥ 30
t.subSet(20, 40);   // {20, 30}        — [20, 40)
t.descendingSet();  // a reverse-order view

Estas son las operaciones que justifican el costo O(log n): un HashSet no puede realizar ninguna de ellas sin ordenar todo el conjunto primero. Si necesitas alguna de ellas, TreeSet es la elección correcta.

Sin nulls

Un TreeSet no puede contener null porque necesitaría comparar null con los demás elementos y compareTo(null) lanza una NullPointerException. El conjunto lanza la excepción en la primera inserción. Si necesitas un centinela, usa un valor diferente del tipo del elemento — Integer.MIN_VALUE, un String vacío, o un marcador dedicado en un enum.

Mutar elementos está prohibido (la misma trampa que HashSet)

TreeSet decide la ubicación en el árbol en el momento de la inserción llamando a compareTo (o a tu Comparator). Si mutas un elemento después de la inserción de forma que cambie el orden, las invariantes del árbol se rompen: contains busca en el subárbol equivocado, remove puede fallar silenciosamente, la iteración puede devolver el mismo elemento dos veces u omitir elementos por completo.

La regla, reformulada: pon elementos efectivamente inmutables en un TreeSet. O, si tu elemento cambia, elimínalo antes del cambio y vuelve a agregarlo después.

Cuándo elegir TreeSet

Flujo de decisión:

• Necesitas iteración ordenada o consultas de rango → TreeSet. La única opción.
• Necesitas verificación de pertenencia rápida y el orden no importa → HashSet. O(1) gana.
• Necesitas verificación de pertenencia rápida y orden de iteración predecible → LinkedHashSet. Orden de inserción, no ordenado.
• El tipo de elemento es un enum → EnumSet. Más rápido que TreeSet y naturalmente ordenado.

Un patrón útil: realiza un cómputo intensivo basado en HashSet cuando la velocidad importa, y luego new TreeSet<>(hashSet) una sola vez al final si necesitas presentar el resultado en orden. Construye rápido, presenta ordenado.

Un ejemplo práctico: tabla de clasificación, comparador y consultas de rango

El programa a continuación usa TreeSet para mantener una tabla de clasificación ordenada por puntuación (con un comparador personalizado), demuestra los métodos de navegación y muestra cómo la igualdad basada en compareTo difiere de la igualdad basada en equals.

Lo que se puede aprender de la ejecución:

• Los enteros se devolvieron en orden ascendente sin ninguna ordenación explícita. Esa invariante de ordenación se mantiene en cada add — el precio es O(log n) por inserción.
• La tabla de clasificación usó un comparador de dos etapas: descendente por puntuación, y luego ascendente por nombre para mantener distintos a los jugadores empatados. Incluye siempre un desempate cuando las puntuaciones pueden repetirse o TreeSet las colapsará.
• El conjunto sin distinción de mayúsculas rechazó "JAVA" porque, según el comparador, es igual a "Java" — aunque "JAVA".equals("Java") sea false. Igualdad por comparador, no igualdad por equals.
• null lanzó una excepción — no hay forma razonable de compararlo con otros elementos.

Qué sigue

Set está terminado; la otra mitad del framework es Map, la abstracción clave-valor. Un Set puede pensarse como un Map donde no te importa el valor. El siguiente capítulo es el de la interfaz Map, y la estructura paralela con Set será obvia en cuanto empecemos. TreeSet está de hecho respaldado por un TreeMap, por lo que los métodos de navegación del mapa ordenado que viste aquí reaparecen allí con claves en lugar de elementos.

Práctica