Classe Java TreeSet | W3Docs Learn Java

TreeSet<E> è l'implementazione di Set che mantiene i propri elementi ordinati. È supportato da un albero rosso-nero (lo stesso albero binario di ricerca bilanciato che sta alla base di TreeMap), quindi ogni operazione — add, remove, contains, first, last, query per intervallo — è O(log n). È più lenta dell'O(1) di HashSet, ma offre qualcosa che HashSet non può fornire: un iteratore ordinato, l'elemento più piccolo su richiesta e la capacità di chiedere "ogni tag tra a e m."

TreeSet implementa l'interfaccia più ricca NavigableSet<E> (che estende SortedSet<E>), quindi tutte le query per intervallo e di vicinanza sono sulla classe stessa, non sepolte negli helper di Collections. Se non hai ancora conosciuto il contratto base, leggi prima il capitolo sull'interfaccia Set — tutto ciò che vi è descritto (nessun duplicato, add restituisce false su una ripetizione) è ancora valido.

Due modi per definire l'ordine

Un TreeSet ha bisogno di un modo per confrontare gli elementi. Ce ne sono due:

Ordine naturale — il tipo di elemento implementa Comparable<E>. String, Integer, LocalDate, ogni wrapper, ogni enum, ogni record che scrivi che implementa Comparable. Il costruttore senza argomenti new TreeSet<>() usa questo approccio.
Un Comparator<E> che fornisci tu — passalo al costruttore. L'insieme usa il tuo comparatore per ogni confronto.

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]

Il secondo esempio è importante. TreeSet decide "uguali" in base a compareTo che restituisce 0, non in base a equals. Due stringhe che l'ordine naturale considera diverse ma che un comparatore considera uguali collasseranno in un unico elemento. Quasi sempre è quello che vuoi — ma è un'insidia se non te ne sei reso conto.

L'API `NavigableSet`

Un TreeSet espone operazioni che un semplice Set non può fare:

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

Queste sono le operazioni che giustificano il costo O(log n): un HashSet non può fare nessuna di esse senza prima ordinare l'intero insieme. Se ne hai bisogno anche solo una, TreeSet è la scelta giusta.

Nessun null

Un TreeSet non può contenere null perché dovrebbe confrontare null con gli altri elementi e compareTo(null) genera una NullPointerException. L'insieme lancia un'eccezione al primo inserimento. Se hai bisogno di un valore sentinella, usa un valore diverso del tipo di elemento — Integer.MIN_VALUE, una String vuota, o un marcatore dedicato in un enum.

Mutare gli elementi è vietato (la stessa trappola di HashSet)

TreeSet decide il posizionamento nell'albero al momento dell'inserimento chiamando compareTo (o il tuo Comparator). Se muti un elemento dopo l'inserimento in modo da modificarne l'ordinamento, gli invarianti dell'albero si rompono: contains cerca nel sottoalbero sbagliato, remove può fallire silenziosamente, l'iterazione può restituire lo stesso elemento due volte o saltare elementi completamente.

La regola, riformulata: inserisci elementi effettivamente immutabili in un TreeSet. Oppure, se il tuo elemento cambia, rimuovilo prima della modifica e reinseriscilo dopo.

Quando scegliere `TreeSet`

Flusso decisionale:

Hai bisogno di iterazione ordinata o query per intervallo → TreeSet. È l'unica scelta.
Hai bisogno di membership rapida e l'ordine non importa → HashSet. O(1) vince.
Hai bisogno di membership rapida e ordine di iterazione prevedibile → LinkedHashSet. Ordine di inserimento, non ordinato.
Il tipo di elemento è un enum → EnumSet. Più veloce di TreeSet e naturalmente ordinato.

Un pattern utile: esegui un calcolo intensivo basato su HashSet quando la velocità conta, poi new TreeSet<>(hashSet) una volta alla fine se hai bisogno di presentare il risultato in ordine. Costruisci veloce, presenta ordinato.

Un esempio pratico: classifica, comparatore e query per intervallo

Il programma seguente usa TreeSet per mantenere una classifica ordinata per punteggio (con un comparatore personalizzato), dimostra i metodi di navigazione e mostra come l'uguaglianza basata su compareTo differisce dall'uguaglianza basata su equals.

java— editable, runs on the server

import java.util.*;

public class TreeSetShowcase {
  public static void main(String[] args) {
    // --- Natural ordering ---
    TreeSet<Integer> nums = new TreeSet<>();
    for (int n : new int[] { 50, 10, 30, 40, 20 }) nums.add(n);
    System.out.println("sorted:        " + nums);
    System.out.println("first/last:    " + nums.first() + " / " + nums.last());
    System.out.println("floor(35):     " + nums.floor(35));
    System.out.println("ceiling(35):   " + nums.ceiling(35));
    System.out.println("subSet(20,40): " + nums.subSet(20, 40));
    System.out.println("descending:    " + nums.descendingSet());

// --- Custom comparator: leaderboard sorted by score, descending ---
    record Player(String name, int score) {}
    TreeSet<Player> board = new TreeSet<>(
        Comparator.<Player>comparingInt(Player::score).reversed()
            .thenComparing(Player::name)); // tie-break by name so equal scores stay distinct
    board.add(new Player("Alice", 90));
    board.add(new Player("Bob",   75));
    board.add(new Player("Carol", 90)); // same score, different name — kept
    board.add(new Player("Dave",  60));
    System.out.println("\nleaderboard:");
    for (Player p : board) System.out.println("  " + p);

// --- pollFirst / pollLast: removing the extremes ---
    System.out.println("\ntop scorer popped: " + board.pollFirst());
    System.out.println("after pop:         " + board);

// --- The compareTo-equality trap ---
    TreeSet<String> ci = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
    ci.add("Java");
    boolean added = ci.add("JAVA");   // comparator says equal → not added
    System.out.println("\ncase-insensitive add 'JAVA' to set containing 'Java': " + added);
    System.out.println("contents: " + ci);

// --- Null is rejected ---
    try { nums.add(null); }
    catch (NullPointerException e) {
      System.out.println("\nadd(null) → " + e.getClass().getSimpleName());
    }
  }
}

Cosa trarre dall'esecuzione:

I numeri interi sono tornati in ordine crescente senza alcun ordinamento esplicito. Quell'invariante ordinato viene mantenuto ad ogni add — il prezzo è O(log n) per inserimento.
La classifica ha usato un comparatore a due fasi: decrescente per punteggio, poi crescente per nome per mantenere distinti i giocatori a pari merito. Includi sempre un tie-breaker quando i punteggi possono ripetersi, altrimenti TreeSet li collasserà.
L'insieme case-insensitive ha rifiutato "JAVA" perché, secondo il comparatore, è uguale a "Java" — anche se "JAVA".equals("Java") è false. Uguaglianza del comparatore, non uguaglianza di equals.
null ha lanciato un'eccezione — non c'è modo sensato di confrontarlo con altri elementi.

Cosa c'è dopo

Set è concluso; l'altra metà del framework è Map, l'astrazione chiave-valore. Un Set può essere pensato come una Map in cui non ti importa del valore. Il capitolo sull'interfaccia Map è il prossimo, e la struttura parallela con Set sarà ovvia una volta iniziato. TreeSet è in realtà supportato da un TreeMap, quindi i metodi di navigazione della mappa ordinata che hai visto qui riappaiono lì con le chiavi al posto degli elementi.

Esercitazione

Pratica

Un `TreeSet` è costruito con `new TreeSet<>(String.CASE_INSENSITIVE_ORDER);`. Aggiungi `'Java'` e poi `'JAVA'`. Qual è la dimensione finale?

1 — il comparatore restituisce 0 per le due stringhe, quindi la seconda `add` è un no-op2 — `String.equals("Java", "JAVA")` è false, quindi sono elementi separati2 — ma solo perché `TreeSet` mantiene l'ordine di inserimento; l'uguaglianza è decisa da `equals`0 — passare un comparatore case-insensitive a `TreeSet` lancia un'eccezione alla costruzione