TreeSet in Java
Edoardo Midali
Il TreeSet in Java è una implementazione della interfaccia Set che mantiene gli elementi in ordine naturale o secondo un comparatore personalizzato. Basato su una struttura dati ad albero rosso-nero, TreeSet offre operazioni di ricerca, inserimento e rimozione con complessità temporale O(log n), rendendolo ideale per scenari che richiedono elementi ordinati e operazioni efficienti.
Caratteristiche Principali del TreeSet
Il TreeSet presenta diverse caratteristiche distintive:
- Elementi Ordinati: Mantiene automaticamente gli elementi in ordine crescente
- Nessun Duplicato: Non consente elementi duplicati
- Implementazione SortedSet: Estende NavigableSet e SortedSet
- Prestazioni O(log n): Operazioni di base con complessità logaritmica
- Thread-Unsafe: Non è sincronizzato per l’accesso concorrente
Sintassi e Creazione
import java.util.TreeSet;
import java.util.Comparator;
// Creazione con ordinamento naturale
TreeSet<Integer> numeri = new TreeSet<>();
// Creazione con comparatore personalizzato
TreeSet<String> parole = new TreeSet<>(Comparator.reverseOrder());
// Creazione da un'altra collezione
TreeSet<Integer> nuoviNumeri = new TreeSet<>(Arrays.asList(5, 2, 8, 1));
Operazioni Fondamentali
Inserimento e Rimozione
TreeSet<String> nomi = new TreeSet<>();
// Aggiunta elementi
nomi.add("Alice");
nomi.add("Bob");
nomi.add("Charlie");
nomi.add("Alice"); // Duplicato - non verrà aggiunto
System.out.println(nomi); // [Alice, Bob, Charlie] - ordinati alfabeticamente
// Rimozione elementi
nomi.remove("Bob");
System.out.println(nomi); // [Alice, Charlie]
Ricerca e Controllo
TreeSet<Integer> numeri = new TreeSet<>(Arrays.asList(10, 5, 15, 8, 12));
// Controllo esistenza
boolean contiene = numeri.contains(10); // true
boolean vuoto = numeri.isEmpty(); // false
int dimensione = numeri.size(); // 5
// Primo e ultimo elemento
Integer primo = numeri.first(); // 5
Integer ultimo = numeri.last(); // 15
Metodi di Navigazione
TreeSet offre metodi avanzati per la navigazione degli elementi:
Metodi Lower e Higher
TreeSet<Integer> numeri = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));
// Elemento immediatamente inferiore
Integer lower = numeri.lower(30); // 20
Integer floor = numeri.floor(25); // 20 (minore o uguale)
// Elemento immediatamente superiore
Integer higher = numeri.higher(30); // 40
Integer ceiling = numeri.ceiling(35); // 40 (maggiore o uguale)
Sottoinsiemi
TreeSet<Integer> numeri = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9, 11, 13));
// Sottoinsiemi
SortedSet<Integer> headSet = numeri.headSet(7); // [1, 3, 5]
SortedSet<Integer> tailSet = numeri.tailSet(7); // [7, 9, 11, 13]
SortedSet<Integer> subSet = numeri.subSet(3, 9); // [3, 5, 7]
// Versioni inclusive/esclusive
NavigableSet<Integer> subSetInclusivo = numeri.subSet(3, true, 9, true); // [3, 5, 7, 9]
Iterazione e Ordinamento
Iterazione Standard
TreeSet<String> città = new TreeSet<>(Arrays.asList("Roma", "Milano", "Napoli", "Torino"));
// Iterazione in ordine crescente
for (String città : città) {
System.out.println(città);
}
// Iterazione con Iterator
Iterator<String> it = città.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
Iterazione in Ordine Decrescente
TreeSet<Integer> numeri = new TreeSet<>(Arrays.asList(1, 5, 3, 9, 7));
// Iterazione in ordine decrescente
NavigableSet<Integer> reversed = numeri.descendingSet();
for (Integer num : reversed) {
System.out.println(num); // 9, 7, 5, 3, 1
}
// Iterator decrescente
Iterator<Integer> descIt = numeri.descendingIterator();
while (descIt.hasNext()) {
System.out.println(descIt.next());
}
Comparatori Personalizzati
Ordinamento Personalizzato
// Comparatore per lunghezza stringa
TreeSet<String> parolePerLunghezza = new TreeSet<>(
Comparator.comparing(String::length).thenComparing(String::compareTo)
);
parolePerLunghezza.addAll(Arrays.asList("casa", "automobile", "libro", "pc"));
System.out.println(parolePerLunghezza); // [pc, casa, libro, automobile]
// Comparatore per oggetti personalizzati
class Persona {
String nome;
int età;
Persona(String nome, int età) {
this.nome = nome;
this.età = età;
}
@Override
public String toString() {
return nome + "(" + età + ")";
}
}
TreeSet<Persona> persone = new TreeSet<>(
Comparator.comparing((Persona p) -> p.età).thenComparing(p -> p.nome)
);
persone.add(new Persona("Alice", 25));
persone.add(new Persona("Bob", 30));
persone.add(new Persona("Charlie", 25));
Esempi Pratici
Sistema di Gestione Punteggi
public class GestorePunteggi {
private TreeSet<Integer> punteggi;
public GestorePunteggi() {
this.punteggi = new TreeSet<>(Collections.reverseOrder());
}
public void aggiungiPunteggio(int punteggio) {
punteggi.add(punteggio);
}
public int getMigliorPunteggio() {
return punteggi.isEmpty() ? 0 : punteggi.first();
}
public int getPeggiorPunteggio() {
return punteggi.isEmpty() ? 0 : punteggi.last();
}
public Set<Integer> getTop3() {
return punteggi.stream().limit(3).collect(Collectors.toSet());
}
public int getPunteggiSuperatiDa(int soglia) {
return punteggi.headSet(soglia).size();
}
}
Calendario Eventi
public class CalendarioEventi {
private TreeSet<LocalDateTime> eventi;
public CalendarioEventi() {
this.eventi = new TreeSet<>();
}
public void aggiungiEvento(LocalDateTime dataOra) {
eventi.add(dataOra);
}
public LocalDateTime prossimoEvento() {
LocalDateTime adesso = LocalDateTime.now();
return eventi.ceiling(adesso);
}
public Set<LocalDateTime> eventiOggi() {
LocalDateTime inizioGiorno = LocalDate.now().atStartOfDay();
LocalDateTime fineGiorno = inizioGiorno.plusDays(1);
return eventi.subSet(inizioGiorno, fineGiorno);
}
public void rimuoviEventiPassati() {
LocalDateTime adesso = LocalDateTime.now();
eventi.removeIf(evento -> evento.isBefore(adesso));
}
}
Confronto con Altre Collezioni
TreeSet vs HashSet
// Performance comparison
Set<Integer> hashSet = new HashSet<>();
Set<Integer> treeSet = new TreeSet<>();
// HashSet: O(1) per operazioni base, nessun ordinamento
// TreeSet: O(log n) per operazioni base, mantiene ordinamento
// Uso consigliato:
// HashSet: quando serve solo unicità degli elementi
// TreeSet: quando serve unicità + ordinamento
TreeSet vs ArrayList Ordinato
// ArrayList ordinato manualmente
List<Integer> lista = new ArrayList<>();
// Richiede Collections.sort() dopo ogni inserimento
// TreeSet mantiene automaticamente l'ordinamento
TreeSet<Integer> treeSet = new TreeSet<>();
// Ordinamento automatico ma senza duplicati
Operazioni Avanzate
Operazioni di Insieme
TreeSet<Integer> set1 = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9));
TreeSet<Integer> set2 = new TreeSet<>(Arrays.asList(2, 4, 6, 7, 8));
// Unione
TreeSet<Integer> unione = new TreeSet<>(set1);
unione.addAll(set2);
System.out.println("Unione: " + unione); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
// Intersezione
TreeSet<Integer> intersezione = new TreeSet<>(set1);
intersezione.retainAll(set2);
System.out.println("Intersezione: " + intersezione); // [7]
// Differenza
TreeSet<Integer> differenza = new TreeSet<>(set1);
differenza.removeAll(set2);
System.out.println("Differenza: " + differenza); // [1, 3, 5, 9]
Polling degli Elementi
TreeSet<Integer> numeri = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));
// Rimuovi e restituisci il primo elemento
Integer primo = numeri.pollFirst(); // 10
System.out.println(numeri); // [20, 30, 40, 50]
// Rimuovi e restituisci l'ultimo elemento
Integer ultimo = numeri.pollLast(); // 50
System.out.println(numeri); // [20, 30, 40]
Best Practices
Implementazione Corretta di Comparable
public class Prodotto implements Comparable<Prodotto> {
private String nome;
private double prezzo;
public Prodotto(String nome, double prezzo) {
this.nome = nome;
this.prezzo = prezzo;
}
@Override
public int compareTo(Prodotto altro) {
// Prima per prezzo, poi per nome
int risultato = Double.compare(this.prezzo, altro.prezzo);
return risultato != 0 ? risultato : this.nome.compareTo(altro.nome);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Prodotto prodotto = (Prodotto) obj;
return Double.compare(prodotto.prezzo, prezzo) == 0 &&
Objects.equals(nome, prodotto.nome);
}
@Override
public int hashCode() {
return Objects.hash(nome, prezzo);
}
}
Thread Safety
// TreeSet non è thread-safe
TreeSet<Integer> nonSafe = new TreeSet<>();
// Versione sincronizzata
Set<Integer> safe = Collections.synchronizedSortedSet(new TreeSet<>());
// Uso con ConcurrentSkipListSet per scenari concorrenti
NavigableSet<Integer> concurrent = new ConcurrentSkipListSet<>();
Considerazioni sulle Performance
TreeSet offre prestazioni eccellenti per la maggior parte delle operazioni:
- Inserimento: O(log n)
- Ricerca: O(log n)
- Rimozione: O(log n)
- Iterazione: O(n)
È ideale quando serve mantenere elementi ordinati con operazioni efficienti, ma HashSet è preferibile quando l’ordinamento non è necessario.
Conclusione
TreeSet è una collezione potente e versatile che combina l’unicità degli elementi tipica dei Set con l’ordinamento automatico. La sua implementazione basata su albero rosso-nero garantisce prestazioni eccellenti per la maggior parte delle operazioni, rendendolo ideale per applicazioni che richiedono dati ordinati e ricerche efficienti. La ricca API di navigazione e i metodi per sottoinsiemi lo rendono particolarmente utile per algoritmi che operano su range di valori ordinati.